✦ LIBER ✦

Essential independent sets and Hamiltonian cycles

✍ Scribed by Chen, Guantao; Egawa, Yoshimi; Liu, Xin; Saito, Akira

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 355 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199602)21:2<242::aid-jgt15>3.0.co;2-l

No coin nor oath required. For personal study only.

✦ Synopsis

An independent set S of a graph G is said to be essential if S has a pair of vertices distance t w o apart in G. We prove that if every essential independent set S of order k 2 2 in a k-connected graph of order p satisfies max{deg u : u E S} I p, then G is hamiltonian. This generalizes the result of Fan (J. Combinatorial Theory B 37 (19841,(221)(222)(223)(224)(225)(226)(227). If w e consider the essential independent sets of order k + 1 instead of k in the assumption of the above statement, w e can no longer assure the existence a hamiltonian cycle. However, we can still give a lower bound to the length of a longest cycle.

📜 SIMILAR VOLUMES

Independent dominating sets and hamilton

Independent dominating sets and hamiltonian cycles

✍ Penny Haxell; Ben Seamone; Jacques Verstraete 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

## Abstract A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no __r__‐regular uniquely hamiltonian graphs when __r__ > 22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233–244, 20

Independent Dominating Sets and a Second

Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs

✍ Carsten Thomassen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 241 KB

In 1975, John Sheehan conjectured that every Hamiltonian 4-regular graph has a second Hamiltonian cycle. Combined with earlier results this would imply that every Hamiltonian r-regular graph (r 3) has a second Hamiltonian cycle. We shall verify this for r 300.

Maximal Sets of 2-Factors and Hamiltonia

Maximal Sets of 2-Factors and Hamiltonian Cycles

✍ D.G. Hoffman; C.A. Rodger; A. Rosa 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 279 KB

Maximal independent sets in graphs with

Maximal independent sets in graphs with at most r cycles

✍ Goh Chee Ying; Koh Khee Meng; Bruce E. Sagan; Vincent R. Vatter 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

## Abstract We find the maximum number of maximal independent sets in two families of graphs. The first family consists of all graphs with __n__ vertices and at most __r__ cycles. The second family is all graphs of the first family which are connected and satisfy __n__ ≥ 3__r__. © 2006 Wiley Period

Maximal and maximum independent sets in

Maximal and maximum independent sets in graphs with at most r cycles

✍ Bruce E. Sagan; Vincent R. Vatter 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB 👁 2 views

## Abstract Let __m__(__G__) denote the number of maximal independent sets of vertices in a graph __G__ and let __c__(__n__,__r__) be the maximum value of __m__(__G__) over all connected graphs with __n__ vertices and at most __r__ cycles. A theorem of Griggs, Grinstead, and Guichard gives a formul

Hamiltonian paths and cycles in hypertou

Hamiltonian paths and cycles in hypertournaments

✍ Gutin, Gregory; Yeo, Anders 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V | = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertour