✦ LIBER ✦

Eulerian subgraphs containing given vertices and hamiltonian line graphs

✍ Scribed by Hong-Jian Lai

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

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph and let DffG) be the set of vertices of degree 1 in G. Veldman (1994) proves the following conjecture from Benhocine et al. (1986) that if G-DI(G) is a 2-edge-connected simple graph with n vertices and if for every edge xy C E(G), d(x)+d(y) > (2n)/5 -2, then for n large, L(G), the line graph of G, is hamiltonian. We shall show the following improvement of this theorem: if G -D~(G) is a 2-edge-connected simple graph with n vertices and if for every edge xy E E(G), max{d(x),d(y)} >>,n/5 -1, then for n large, L(G) is hamiltonian with the exception of a class of well characterized graphs. Our result implies Veldman's theorem.

📜 SIMILAR VOLUMES

Eulerian subgraphs in 3-edge-connected g

Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs

✍ Zhi-Hong Chen; Hong-Jian Lai; Xiangwen Li; Deying Li; Jinzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

## Abstract In this paper, we show that if __G__ is a 3‐edge‐connected graph with $S \subseteq V(G)$ and $|S| \le 12$, then either __G__ has an Eulerian subgraph __H__ such that $S \subseteq V(H)$, or __G__ can be contracted to the Petersen graph in such a way that the preimage of each vertex of th

A result on Hamiltonian line graphs invo

A result on Hamiltonian line graphs involving restrictions on induced subgraphs

✍ H. J. Veldman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G. Thereby a number of known results on hamiltonian line graphs are improved, including the earliest results in terms of vertex degrees. O