✦ LIBER ✦

Square Hamiltonian cycles in graphs with maximal 4-cliques

✍ Scribed by H.A. Kierstead; Juan Quintana

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 615 KB
Volume: 178
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)81819-5

No coin nor oath required. For personal study only.

✦ Synopsis

The square of a graph is obtained by adding additional edges joining all pairs of vertices with distance two in the original graph. P6sa conjectured that if G is a simple graph on n vertices with minimum degree 2n/3, then G contains the square of a hamiltonian cycle. We show that P6sa's conjecture holds for graphs that in addition contain a maximal 4-clique.

📜 SIMILAR VOLUMES

Maximal cliques in the Paley graph of sq

Maximal cliques in the Paley graph of square order

✍ R.D. Baker; G.L. Ebert; J. Hemmeter; A. Woldar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 424 KB

Determining the clique number of the Paley graph of order q, 4 E I (mod 4) a prime power, is a difficult problem. However, the work of Blokhuis implies that in the Paley graph of order q2, where q is any odd prime power, the clique number is in fact q. In this paper we construct maximal cliques of s

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

On ‘maximal’ Hamiltonian cycles in the s

On ‘maximal’ Hamiltonian cycles in the square of a block

✍ Günter Schaar 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 241 KB

A linear algorithm for finding Hamiltoni

A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs

✍ Takao Asano; Shunji Kikuchi; Nobuji Saito 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 901 KB

On the number of hamiltonian cycles in a

On the number of hamiltonian cycles in a maximal planar graph

✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro

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