𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Zhi-Hong Chen; Hong-Jian Lai; Xiangwen Li; Deying Li; Jinzhong Mao

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
111 KB
Volume
42
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any $|S|\le 23$, G has an Eulerian subgraph H such that $S\subseteq V(H)$. As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003

📜 SIMILAR VOLUMES

Spanning even subgraphs of 3-edge-connec
Spanning even subgraphs of 3-edge-connected graphs
✍ Bill Jackson; Kiyoshi Yoshimoto 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

## Abstract By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connec

Contractible Subgraphs in 3-Connected Gr
Contractible Subgraphs in 3-Connected Graphs
✍ Matthias Kriesell 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 154 KB

A subgraph H of a 3-connected finite graph G is called contractible if H is connected and G&V(H) is 2-connected. This work is concerned with a conjecture of McCuaig and Ota which states that for any given k there exists an f (k) such that any 3-connected graph on at least f (k) vertices possesses a

3-Connected line graphs of triangular gr
3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian
✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

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

Some 3-connected 4-edge-critical non-Ham
Some 3-connected 4-edge-critical non-Hamiltonian graphs
✍ Yang Yuansheng; Zhao Chengye; Lin Xiaohui; Jiang Yongsong; Hao Xin 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 79 KB 👁 1 views

## Abstract Let γ(__G__) be the domination number of graph __G__, thus a graph __G__ is __k__‐edge‐critical if γ (__G__) = k, and for every nonadjacent pair of vertices __u__ and υ, γ(__G__ + __u__υ) = k−1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjectu

Contractible subgraphs in k-connected gr
Contractible subgraphs in k-connected graphs
✍ Zemin Jin; Xingxing Yu; Xiaoyan Zhang 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB

## Abstract For a graph __G__ we define a graph __T__(__G__) whose vertices are the triangles in __G__ and two vertices of __T__(__G__) are adjacent if their corresponding triangles in __G__ share an edge. Kawarabayashi showed that if __G__ is a __k__‐connected graph and __T__(__G__) contains no ed

Hamiltonian cycles in 3-connected claw-f
Hamiltonian cycles in 3-connected claw-free graphs
✍ MingChu Li 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 437 KB 👁 2 views

## Abstract In this paper, we show that every 3‐connected claw‐free graph on n vertices with δ ≥ (__n__ + 5)/5 is hamiltonian. © 1993 John Wiley & Sons, Inc.