✦ LIBER ✦

Hamiltonicity and forbidden subgraphs in 4-connected graphs

✍ Scribed by Florian Pfender

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 121 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20080

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let T be the line graph of the unique tree F on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., T is a chain of three triangles. We show that every 4‐connected {T, K~1,3~}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 262–272, 2005

📜 SIMILAR VOLUMES

Pancyclicity of 3-connected graphs: Pair

Pancyclicity of 3-connected graphs: Pairs of forbidden subgraphs

✍ Ronald J. Gould; Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB

## Abstract We characterize all pairs of connected graphs {__X__, __Y__} such that each 3‐connected {__X__, __Y__}‐free graph is pancyclic. In particular, we show that if each of the graphs in such a pair {__X__, __Y__} has at least four vertices, then one of them is the claw __K__~1,3~, while the

Forbidden subgraphs and graph decomposit

Forbidden subgraphs and graph decomposition

✍ Donald K. Wagner 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB

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

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

Hamiltonicity of regular 2-connected gra

Hamiltonicity of regular 2-connected graphs

✍ Broersma, H. J.; van den Heuvel, J.; Jackson, B.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 832 KB

Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n 5 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to q k if G is 3-connected and k 2 63. We improve both results by showing that G is hamiltonian if n 5 gk -7 and G does not belong to a res

Forbidden subgraphs and hamiitonian prop

Forbidden subgraphs and hamiitonian properties in the square of a connected graph

✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 331 KB 👁 1 views

Various Hamiltonian-like properties are investigated in the squares of connected graphs free of some set of forbidden subgraphs. The star K,+ the subdivision graph of &, and the subdivision graph of K1,3 minus an endvertex play central roles. In particular, we show that connected graphs free of the