✦ LIBER ✦

A characterization of weakly four-connected graphs

✍ Scribed by Tibor Jordán

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 106 KB
Volume: 52
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20157

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph G = (V, E) is called weakly four‐connected if G is 4‐edge‐connected and G − x is 2‐edge‐connected for all x ∈ V. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using these results we prove that every minimally weakly four‐connected graph on at least four vertices contains at least three ‘splittable’ vertices of degree four, which gives rise to an inductive construction of weakly four‐connected graphs. Our results can also be applied in the problem of finding 2‐connected orientations of graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 217–229, 2006

📜 SIMILAR VOLUMES

On Four-Connecting a Triconnected Graph

✍ Tsan-sheng Hsu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 328 KB

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical Ž Ž . . database security. We present an O n и ␣ m, n q m -time a

Characterization of maximum critically 2

Characterization of maximum critically 2-connected graphs

✍ R. C. Entringer 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

## Abstract A graph __G__ is critically 2‐connected if __G__ is 2‐connected but, for any point __p__ of __G, G — p__ is not 2‐connected. Critically 2‐connected graphs on __n__ points that have the maximum number of lines are characterized and shown to be unique for __n__ ⩾ 3, __n__ ≠ 11.

A Short Proof of Guenin's Characterizati

A Short Proof of Guenin's Characterization of Weakly Bipartite Graphs

✍ Alexander Schrijver 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 79 KB

We give a proof of Guenin's theorem characterizing weakly bipartite graphs by not having an odd-K 5 minor. The proof curtails the technical and case-checking parts of Guenin's original proof.

Long paths through four vertices in a 2-

Long paths through four vertices in a 2-connected graph

✍ Barovich, Mark V. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 2 views

Let G be a 2-connected graph, let u and v be distinct vertices in V (G), and let X be a set of at most four vertices lying on a common (u

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_

The rainbow connectivity of a graph

✍ Gary Chartrand; Garry L. Johns; Kathleen A. McKeon; Ping Zhang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB