𝔖 Bobbio Scriptorium
✦   LIBER   ✦

3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian

✍ Scribed by H. J. Broersma; H. J. Veldman

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
368 KB
Volume
11
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is k-triangular if each edge is in at least k triangles. Triangular is a synonym for l-triangular. It is shown that the line graph of a triangular graph of order at least 4 is panconnected if and only if it is 3-connected. Furthermore, the line graph of a k-triangular graph is k-harniltonian if and only if it is ( k + 2)-connected ( k L 1). These results generalize work of Clark and Wormald and of Lesniak-Foster. Related results are due to Oberly and Sumner and to Kanetkar and Rao.

1. PRELIMINARIES

We use [ l ] for basic terminology and notation, and consider simple graphs only. Let'G be a graph. We will often identify a trail in G with the subgraph induced by its edges. Hence a subgraph T of G is a trail if and only if T is connected and at most two vertices of T have odd degree in T . An edge e of G is dominated by the trail T if e is incident with at least one vertex of T; E ( T ) denotes the set of edges of G dominated by T and we write b(T) for (E(T)I. A dominuting trail or D-trail of G is a trail that dominates all edges of G , while a spanning trail or S-trail contains all vertices of G . A circuit is a nontrivial

📜 SIMILAR VOLUMES

Connected, locally 2-connected, K1,3-fre
Connected, locally 2-connected, K1,3-free graphs are panconnected
✍ S. V. Kanetkar; P. R. Rao 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 1 views

## Abstract A graph __G__ is locally __n__‐connected, __n__ ≥ 1, if the subgraph induced by the neighborhood of each vertex is __n__‐connected. We prove that every connected, locally 2‐connected graph containing no induced subgraph isomorphic to __K__~1,3~ is panconnected.

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

Claw-free 3-connected P11-free graphs ar
Claw-free 3-connected P11-free graphs are hamiltonian
✍ Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

## Abstract We show that every 3‐connected claw‐free graph which contains no induced copy of __P__~11~ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of __P__~12~ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph T

A necessary and sufficient condition for
A necessary and sufficient condition for connected, locally k-connected k1,3-free graphs to be k-hamiltonian
✍ Zhou Huai-Lu 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 2 views

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K,,-free graph is k-hamiltonian if and only if it is (k + 2)-connected ( k L 1). We use [ 11 for basic terminology and notation, and consider simple graphs only. Let G be a graph. By V(G) and E(G) we denote,

Covering contractible edges in 3-connect
Covering contractible edges in 3-connected graphs. I: Covers of size three are cutsets
✍ Akira Saito 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 397 KB 👁 1 views

## Abstract An edge of a 3‐connected graph is said to be __contractible__ if its contraction results in a 3‐connected graph. In this paper, a covering of contractible edges is studied. We give an alternative proof to the result of Ota and Saito (__Scientia__ (A) 2 (1988) 101–105) that the set of co