𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Jan van den Heuvel; Bill Jackson

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
191 KB
Volume
77
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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 vertex-transitive and each component of F is an isomorphic vertex-transitive graph on at least 2 3 (k+1) vertices. We show that this result is in some sense best possible and use it to show that if k 4 and G has an edge cut of size less than 1 5 (8k&12) which separates G into two components each containing at least two vertices, then G is hamiltonian. We also obtain as a corollary a result on the toughness of vertextransitive graphs.

📜 SIMILAR VOLUMES

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 the hamiltonicity of line graphs of l
On the hamiltonicity of line graphs of locally finite, 6-edge-connected graphs
✍ Richard C. Brewster; Daryl Funk 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a

The edge-transitive but not vertex-trans
The edge-transitive but not vertex-transitive cubic graph on 112 vertices
✍ Marston Conder; Aleksander Malnič; Dragan Marušič; Tomaž Pisanski; Primož Potočn 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB 👁 1 views

## Abstract A detailed description is given of a recently discovered edge‐transitive but not vertex‐transitive trivalent graph on 112 vertices, which turns out to be the third smallest example of such a semisymmetric cubic graph. This graph has been called the __Ljubljana graph__ by the first autho

An infinite series of regular edge- but
An infinite series of regular edge- but not vertex-transitive graphs
✍ Felix Lazebnik; Raymond Viglione 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB 👁 1 views

## Abstract Let __n__ be an integer and __q__ be a prime power. Then for any 3 ≤ __n__ ≤ __q__−1, or __n__=2 and __q__ odd, we construct a connected __q__‐regular edge‐but not vertex‐transitive graph of order 2__q__^__n__+1^. This graph is defined via a system of equations over the finite field of

Vertex-transitive graphs that remain con
Vertex-transitive graphs that remain connected after failure of a vertex and its neighbors
✍ Y. O. Hamidoune; A. Lladó; S. C. López 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB

A d-regular graph is said to be superconnected if any disconnecting subset with cardinality at most d is formed by the neighbors of some vertex. A superconnected graph that remains connected after the failure of a vertex and its neighbors will be called vosperian. Let be a vertex-transitive graph of

On the Vertex-Distinguishing Proper Edge
On the Vertex-Distinguishing Proper Edge-Colorings of Graphs
✍ Cristina Bazgan; Amel Harkat-Benhamdine; Hao Li; Mariusz Woźniak 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 189 KB

We prove the conjecture of Burris and Schelp: a coloring of the edges of a graph of order n such that a vertex is not incident with two edges of the same color and any two vertices are incident with different sets of colors is possible using at most n+1 colors. 1999 Academic Press ## 1. Introducti