✦ LIBER ✦

Extremal maximal uniquely hamiltonian graphs

✍ Scribed by Curtiss A. Barefoot; R. C. Entringer

Publisher: John Wiley and Sons
Year: 1980
Tongue: English
Weight: 352 KB
Volume: 4
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190040110

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a graph of order n with exactly one Hamiltonian cycle and suppose that G is maximal with respect to this property. We determine the minimum number of edges G can have.

📜 SIMILAR VOLUMES

A census of maximum uniquely hamiltonian

A census of maximum uniquely hamiltonian graphs

✍ Curtiss A. Barefoot; R. C. Entringer 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

## Abstract We show that there are 2^[n/2]‐4^ largest graphs of order __n__ ≥ 7 having exactly one hamiltonian cycle. a recursive procedure for constructing these graphs is described.

Vertices of Small Degree in Uniquely Ham

Vertices of Small Degree in Uniquely Hamiltonian Graphs

✍ J.A. Bondy; Bill Jackson 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 206 KB

Let G be a uniquely hamiltonian graph on n vertices. We show that G has a vertex of degree at most c log 2 8n+3, where c=(2&log 2 3) &1 r2.41. We show further that G has at least two vertices of degree less than four if it is planar and at least four vertices of degree two if it is bipartite.

Graphs with unique maximal clumpings

✍ Andreas Blass 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 322 KB

## Abstract A partition of the vertices of a graph is called a clumping if, for vertices in distinct partition classes, adjacency depends only on the partition classes, not on the specific vertices. We give a simple necessary and sufficient condition for a finite graph to have a unique maximal clum

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

Cubic graphs with three Hamiltonian cycl

Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable

✍ Andrew Thomason 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 1 views

## Abstract The generalized Petersen graph __P__(6__k__ + 3, 2) has exactly 3 Hamiltonian cycles for __k__ ≥ 0, but for __k__ ≥ 2 is not uniquely edge colorable. This disproves a conjecture of Greenwell and Kronk [1].

Hamiltonian weights and unique 3-edge-co

Hamiltonian weights and unique 3-edge-colorings of cubic graphs

✍ Cun-Quan Zhang 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 402 KB

## Abstract A (1,2)‐eulerian weight __w__ of a grph is hamiltonian if every faithful cover of __w__ is a set of two Hamilton circuits. Let __G__ be a 3‐connected cubic graph containing no subdivition of the Petersen graph. We prove that if __G__ admits a hamiltonian weight then __G__ is uniquely 3‐