✦ LIBER ✦

Determining the hamilton-connectedness of certain vertex-transitive graphs

✍ Scribed by Ming Jiang; Frank Ruskey

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 731 KB
Volume: 133
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90023-x

No coin nor oath required. For personal study only.

✦ Synopsis

Faber and Moore have proposed a class of vertex-transitive digraphs as a model of directed inconnection networks. These networks have attractive degree versus diameter properties. We show that these digraphs are Hamiltonian and provide necessary and sufficient conditions for the existence of a Hamilton path between any two vertices. Particular cases of these digraphs are the right rotation Cayley digraphs Cay(X,: S,) where X, is the set of right rotations (1 2...i-l i) for i=2,3 ,..., n. Another class of vertex-transitive graphs that have been proposed as models of inconnection networks are the arrangement graphs introduced by Day and Tripathi. They have the same vertex set as the Faber-Moore digraphs. We prove that arrangement graphs are Hamilton-connected.

📜 SIMILAR VOLUMES

The maximum genus of vertex-transitive g

The maximum genus of vertex-transitive graphs

✍ Martin Škoviera; Roman Nedela 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 911 KB

The maximum genus of all vertex-transitive graphs is computed. It is proved that a k-valent vertex-transitive graph of girth g is upper-embeddable whenever k 3 4 or g 2 4. Non-upper-embeddable vertex-transitive graphs are characterized. A particular attention is paid to Cayley graphs. Groups for wh

On the Edge Connectivity, Hamiltonicity,

On the Edge Connectivity, Hamiltonicity, and Toughness of Vertex-Transitive Graphs

✍ Jan van den Heuvel; Bill Jackson 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let G be a connected k-regular vertex-transitive graph on n vertices. For S V(G) let d(S) denote the number of edges between S and V(G)"S. We extend results of Mader and Tindell by showing that if d(S)< 2 9 (k+1) 2 for some S V(G) with 1 3 (k+1) |S| 1 2 n, then G has a factor F such that GÂE(F ) is

On Hamiltonicity of Vertex-Transitive Gr

On Hamiltonicity of Vertex-Transitive Graphs and Digraphs of Orderp4

✍ Yu Qing Chen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 352 KB

The main result of this paper is that vertex-transitive graphs and digraphs of order p 4 are Hamiltonian, where p is a prime number. 1998 Academic Press 1. INTRODUCTION Witte [7] proved that Cayley digraphs of finite p-groups are Hamiltonian. In [2], Marus$ ic$ showed that all vertex-transitive digr

On stability of Hamilton-connectedness u

On stability of Hamilton-connectedness under the 2-closure in claw-free graphs

✍ Zdeněk Ryjáček; Petr Vrána 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 1 views

We show that, in a claw-free graph, Hamilton-connectedness is preserved under the operation of local completion performed at a vertex with 2-connected neighborhood. This result proves a conjecture by Bollobás et al.