𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian paths in vertex-symmetric graphs of order 4p

✍ Scribed by Dragan Marušič; T.D. Parsons

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
562 KB
Volume
43
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that every connected vertex-symmetric graph of order 4p (p a prime) has a Hamiltonian path.

1. Il#aoductjon

L. Lovasz has conjectured that every connected vertex-symmetric graph (cvsg) has a Hamiltonian path. This conjecture has been verified for graphs of order p, 2p, 3p, p2, and p3 (in which case the graph has a Hamiltonian cycle, unless it is the Petersen graph), and Sp-where we always let p denote a prime. (See [3, p. 249, problem 201, and [ 1, 5, 61.) Using the method of [6], and some group theoretic results of [S], we shall prove that every cvsg of order 4p has a Hamiltonian path. For the sake of brevity, we shall refer to the notations, lemmas, and p:opositions of our earlier paper [6], without restating them here.

2. Main result

Theorem 1. Every cvsg of order 4p has a Hamiltonian path.

📜 SIMILAR VOLUMES

Tetravalent vertex-transitive graphs of
Tetravalent vertex-transitive graphs of order 4p
✍ Jin-Xin Zhou 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

A graph is __vertex‐transitive__ if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a __Cayley graph__ if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs

Hamiltonian cycles and paths in vertex-t
Hamiltonian cycles and paths in vertex-transitive graphs with abelian and nilpotent groups
✍ Marc J. Lipman 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 378 KB

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 grap

Powers of Hamiltonian paths in interval
Powers of Hamiltonian paths in interval graphs
✍ Isaak, Garth 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB 👁 3 views

We give a simple proof that the obvious necessary conditions for a graph to contain the k th power of a Hamiltonian path are sufficient for the class of interval graphs. The proof is based on showing that a greedy algorithm tests for the existence of Hamiltonian path powers in interval graphs. We wi