𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A local structure theorem on 5-connected graphs

✍ Scribed by Kiyoshi Ando

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
281 KB
Volume
60
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K~4~^−^‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2__n__/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009

📜 SIMILAR VOLUMES

Local connectivity of a random graph
Local connectivity of a random graph
✍ P. Erdös; E. M. Palmer; R. W. Robinson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract A graph is locally connected if for each vertex ν of degree __≧2__, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order __n_

An 11-vertex theorem for 3-connected cub
An 11-vertex theorem for 3-connected cubic graphs
✍ R. E. L. Aldred; BauSheng; D. A. Holton; Gordon F. Royle 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 451 KB 👁 1 views

In this paper w e determine the circumstances under which a set of 11 vertices in a 3-connected cubic graph lies on a cycle. In addition, w e consider the number of such cycles that exist and characterize those graphs in which a set of 9 vertices lies in exactly two cycles.

On local connectivity of graphs with giv
On local connectivity of graphs with given clique number
✍ Andreas Holtkamp; Lutz Volkmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB

## Abstract For a vertex __v__ of a graph __G__, we denote by __d__(__v__) the __degree__ of __v__. The __local connectivity__ κ(__u, v__) of two vertices __u__ and __v__ in a graph __G__ is the maximum number of internally disjoint __u__ –__v__ paths in __G__, and the __connectivity__ of __G__ is

On the Structure of 3-connected Matroids
On the Structure of 3-connected Matroids and Graphs
✍ James Oxley; Haidong Wu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 249 KB

An element e of a 3-connected matroid M is essential if neither the deletion M\e nor the contraction M/e is 3-connected. Tutte's Wheels and Whirls Theorem proves that the only 3-connected matroids in which every element is essential are the wheels and whirls. In this paper, we consider those 3-conne

A Short Proof of a Theorem Concerning De
A Short Proof of a Theorem Concerning Degree Sums and Connectivity on Hamiltonian Graphs
✍ Bing Wei 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 74 KB

proved that if G is a 2-connected graph with n vertices such that d(u)+d(v)+d(w) n+} holds for any triple of independent vertices u, v, and w, then G is hamiltonian, where } is the vertex connectivity of G. In this note, we will give a short proof of the above result.