✦ LIBER ✦

Cycle-minors and subdivisions of wheels

✍ Scribed by Galen E. Turner III

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 130 KB
Volume: 62
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20393

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we prove two results. The first is an extension of a result of Dirac which says that any set of n vertices of an n‐connected graph lies in a cycle. We prove that if V′ is a set of at most 2__n__ vertices in an n‐connected graph G, then G has, as a minor, a cycle using all of the vertices of V′. The second result says that if G is an n+1‐connected graph with maximum vertex degree Δ then G contains a subgraph that is a subdivision of W~2__n__~ if and only if Δ≥2__n__. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 100–108, 2009

📜 SIMILAR VOLUMES

Embedding of cycles and wheels into arbi

Embedding of cycles and wheels into arbitrary trees

✍ Indra Rajasingh; Albert William; Jasintha Quadras; Paul Manuel 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

A Longest Cycle Version of Tutte's Wheel

A Longest Cycle Version of Tutte's Wheels Theorem

✍ Talmage James Reid; Haidong Wu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 316 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birthday An edge e of a minimally 3-connected graph G is non-essential if and only if the graph obtained by contracting e from G is both 3-connected and simple. Suppose that G is not a wheel. Tutte's Wheels Theorem states that

Cycle and circle tests of balance in gai

Cycle and circle tests of balance in gain graphs: Forbidden minors and their groups

✍ Konstantin Rybnikov; Thomas Zaslavsky 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB

## Abstract We examine two criteria for balance of a gain graph, one based on binary cycles and one on circles. The graphs for which each criterion is valid depend on the set of allowed gain groups. The binary cycle test is invalid, except for forests, if any possible gain group has an element of o

Duality and Minors of Secondary Polyhedr

Duality and Minors of Secondary Polyhedra

✍ L.J. Billera; I.M. Gelfand; B. Sturmfels 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 419 KB

Subdivisions and the chromatic index of

Subdivisions and the chromatic index of r-graphs

✍ K. Kilakos; F. B. Shepherd 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 625 KB

Let T2 be the graph obtained from the Petersen graph by first deleting a vertex and then contracting an edge incident to a vertex of degree two. We give a simple characterization of the graphs that contain no subdivision of T2. This characterization is used to show that if every planar r-graph is r-

Excluding Induced Subdivisions of the Bu

Excluding Induced Subdivisions of the Bull and Related Graphs

✍ Maria Chudnovsky; Irena Penev; Alex Scott; Nicolas Trotignon 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

## Abstract For any graph __H__, let Forb\*(__H__) be the class of graphs with no induced subdivision of __H__. It was conjectured in [J Graph Theory, 24 (1997), 297–311] that, for every graph __H__, there is a function __f__~__H__~: ℕ→ℝ such that for every graph __G__∈Forb\*(__H__), χ(__G__)≤__f__