✦ LIBER ✦

A census of maximum uniquely hamiltonian graphs

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

Publisher: John Wiley and Sons
Year: 1981
Tongue: English
Weight: 261 KB
Volume: 5
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190050313

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Extremal maximal uniquely hamiltonian gr

Extremal maximal uniquely hamiltonian graphs

✍ Curtiss A. Barefoot; R. C. Entringer 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 352 KB

## 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.

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.

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‐

On the hamiltonian path graph of a graph

✍ George R. T. Hendry 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 1 views

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and u are adjacent if and only if F contains a hamiltonian u -u path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian grap

A class of Hamiltonian regular graphs

✍ Paul Erdös; Arthur M. Hobbs 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 317 KB

## Abstract In this paper, we show that __n__ ⩾ 4 and if __G__ is a 2‐connected graph with 2__n__ or 2__n__−1 vertices which is regular of degree __n__−2, then __G__ is Hamiltonian if and only if __G__ is not the Petersen graph.

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