✦ LIBER ✦

Hamiltonian cycles and paths in vertex-transitive graphs with abelian and nilpotent groups

✍ Scribed by Marc J. Lipman

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 378 KB
Volume: 54
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90058-5

No coin nor oath required. For personal study only.

✦ Synopsis

In 1968, L. Lovfisz conjectured that every connected, vertex-transitive graph had a Hamiltonian path. In this paper the following results are proved: (1) If a connected graph has a transitive nilpotent group acting on it, then the graph has a Hamiltonian path; (2) a connected, vertex-transitive graph with a prime power number of vertices has a Hamiltonian path.

📜 SIMILAR VOLUMES

Long cycles in vertex-transitive graphs

✍ László Babai 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

## Abstract We prove that every connected vertex‐transitive graph on __n__ ≥ 4 vertices has a cycle longer than (3__n__)^1/2^. The correct order of magnitude of the longest cycle seems to be a very hard question.

Vertex heaviest paths and cycles in quas

Vertex heaviest paths and cycles in quasi-transitive digraphs

✍ Jørgen Bang-Jensen; Gregory Gutin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 381 KB

A digraph D is called a quasi-transitive digraph (QTD) if for any triple x,y,z of distinct vertices of D such that (x,y) and (y,z) are arcs of D there is at least one at': from x to z or from z to x. Solving a conjecture by Bangdensen and Huang (1995), Gutin (1995) described polynomial algorithms fo

Hamiltonian cycles and paths in Cayley g

Hamiltonian cycles and paths in Cayley graphs and digraphs — A survey

✍ Stephen J. Curran; Joseph A. Gallian 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 927 KB

Cayley graphs arise naturally in computer science, in the study of word-hyperbolic groups and automatic groups, in change-ringing, in creating Escher-like repeating patterns in the hyperbolic plane, and in combinatorial designs. Moreover, Babai has shown that all graphs can be realized as an induced

Hamilton cycle and Hamilton path extenda

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

✍ Štefko MiklaviČ; Primož Šparl 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

## Abstract In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is __n__‐__HC‐extendable__ if it contains a path of length __n__ and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is __weakly n__‐__HP‐

Cycles and paths in graphs with large mi

Cycles and paths in graphs with large minimal degree

✍ V. Nikiforov; R. H. Schelp 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

## Abstract Let __G__ be a simple graph of order __n__ and minimal degree > cn (0 < c < 1/2). We prove that (1) There exist __n__~0~ = __n__~0~(__c__) and __k__ = __k__(__c__) such that if __n__ > __n__~0~ and __G__ contains a cycle __C__~__t__~ for some __t__ > 2__k__, then __G__ contains a cycle

Hamiltonian circuits and paths in subset

Hamiltonian circuits and paths in subset graphs with circular adjacency

✍ T.C. Enns 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 751 KB

Consider the subset graph G(n, k) whose vertex set C(n, k) is the set of all n-tuples of 'O's' and 'l's' with exactly k 'I's'. Let an edge exist between two vertices a and b in G(n,k) if and only if a can be transformed into b by the interchange of two adjacent coordinate values, with the first and