✦ LIBER ✦

Vertices of Small Degree in Uniquely Hamiltonian Graphs

✍ Scribed by J.A. Bondy; Bill Jackson

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 206 KB
Volume: 74
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1845

No coin nor oath required. For personal study only.

✦ Synopsis

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.

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

On minimum degree in Hamiltonian path gr

On minimum degree in Hamiltonian path graphs

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

Vertices of given degree in a random gra

Vertices of given degree in a random graph

✍ Béla Bollobás 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 349 KB 👁 1 views

Labelled graphs with vertices of degree

Labelled graphs with vertices of degree at least three

✍ I. P. Goulden; D. M. Jackson 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 463 KB 👁 1 views

The generating function for labelled graphs in which each vertex has degree at least three is obtained by the Principle of Inclusion and Exclusion. Asymptotic and explicit values for the coefficients are calculated in the connected case. The results are extended to bipartite graphs.

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‐

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