✦ LIBER ✦

Independent dominating sets and hamiltonian cycles

✍ Scribed by Penny Haxell; Ben Seamone; Jacques Verstraete

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 168 KB
Volume: 54
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20205

No coin nor oath required. For personal study only.

✦ Synopsis

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, 2007

📜 SIMILAR VOLUMES

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.

Essential independent sets and Hamiltoni

Essential independent sets and Hamiltonian cycles

✍ Chen, Guantao; Egawa, Yoshimi; Liu, Xin; Saito, Akira 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

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

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

Uniqueness of maximal dominating cycles

Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs

✍ Herbert Fleischner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB 👁 2 views

## Abstract We construct 3‐regular (cubic) graphs __G__ that have a dominating cycle __C__ such that no other cycle __C__~1~ of __G__ satisfies __V(C)__ ⊆ __V__(__C__~1~). By a similar construction we obtain loopless 4‐regular graphs having precisely one hamiltonian cycle. The basis for these const

Independent perfect domination sets in C

Independent perfect domination sets in Cayley graphs

✍ Jaeun Lee 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 1 views

## Abstract In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube __Q~n~__ has an independent perfect domination set if and only if __Q~n~__ i

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