✦ LIBER ✦

Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs

✍ Scribed by Carsten Thomassen

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 241 KB
Volume: 72
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1794

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 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

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

Signed Domination in Regular Graphs and

Signed Domination in Regular Graphs and Set-Systems

✍ Zoltán Füredi; Dhruv Mubayi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Suppose G is a graph on n vertices with minimum degree r. Using standard random methods it is shown that there exists a two-coloring of the vertices of G with colors, +1 and &1, such that all closed neighborhoods contain more 1's than &1's, and all together the number of 1's does not exceed the numb

The Complexity of Finding a Second Hamil

The Complexity of Finding a Second Hamiltonian Cycle in Cubic Graphs

✍ Adam Krawczyk 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 120 KB

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 cycles and paths with a pres

Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets

✍ Rostislav Caha; V. Koubek 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

## Abstract This paper studies techniques of finding hamiltonian paths and cycles in hypercubes and dense sets of hypercubes. This problem is, in general, easily solvable but here the problem was modified by the requirement that a set of edges has to be used in such path or cycle. The main result o