✦ LIBER ✦

On Four-Connecting a Triconnected Graph

✍ Scribed by Tsan-sheng Hsu

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 328 KB
Volume: 35
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1077

No coin nor oath required. For personal study only.

✦ Synopsis

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 algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, Ž . and ␣ m, n is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.

In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of Ž . edges needed to k-connect a k y 1 -connected graph. For k s 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.

📜 SIMILAR VOLUMES

Generating Internally Four-Connected Gra

Generating Internally Four-Connected Graphs

✍ Thor Johnson; Robin Thomas 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 257 KB

A graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges. A graph G is internally 4-connected if it is simple, 3-connected, has at least five vertices, and if for every partition (A, B) of the edgeset of G, either |A| [ 3 or |B| [ 3 or at least fo

A characterization of weakly four-connec

A characterization of weakly four-connected graphs

✍ Tibor Jordán 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

## 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 thes

On n-connected graphs

✍ Branko Grünbaum 📂 Article 📅 1969 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB

The main aim of the present note is the proof of a variant of the MENGER-WHITNEY theorem on n-connected graphs (Theorem 1 below). While the result itself is well known (being, for example, a special case of the theorem of MENGER mentioned in Remark I), two of its aspects deserve attention. First, it

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

On connectivities of tree graphs

✍ Guizhen Liu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 289 KB

Let T(G) be the tree graph of a graph G with cycle rank r. Then K ( T ( G ) ) 3 m ( G ) -r, where K(T(G)) and m(G) denote the connectivity of T ( G ) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m ( G ) -r is best possible.

On Hamiltonian-connected regular graphs

✍ Ioan Tomescu 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

In this paper it is shown that any rn-regular graph of order 2rn (rn 3 3), not isomorphic to K, , , , or of order 2rn + 1 (rn even, rn 3 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains at least rn Hamiltonian