✦ LIBER ✦

Connectivity keeping trees in k-connected graphs

✍ Scribed by W. Mader

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 86 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20585

No coin nor oath required. For personal study only.

✦ Synopsis

We show that one can choose the minimum degree of a k-connected graph G large enough (independent of the vertex number of G) such that G contains a copy T of a prescribed tree with the property that G -V (T ) remains k-connected.

📜 SIMILAR VOLUMES

Connectivity keeping paths in k-connecte

Connectivity keeping paths in k-connected graphs

✍ W. Mader 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 1 views

## Abstract A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph __G__ of minimum degree at least ⌊3__k__/2⌋ contains a vertex __x__ such that __G__−__x__ is still __k__‐connected. We generalize this result by proving t

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.

k-shredders in k-connected graphs

✍ Yoshimi Egawa 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract For a graph __G__, a subset __S__ of __V__(__G__) is called a shredder if __G__ − __S__ consists of three or more components. We show that if __k__ ≥ 4 and __G__ is a __k__‐connected graph, then the number of shredders of cardinality __k__ of __G__ is less than 2|__V__(__G__)|/3 (we sho

Rainbow trees in graphs and generalized

Rainbow trees in graphs and generalized connectivity

✍ Gary Chartrand; Futaba Okamoto; Ping Zhang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 145 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

Nonseparating cycles in K-Connected grap

Nonseparating cycles in K-Connected graphs

✍ Carsten Thomassen 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 1 views

## Abstract We show that every __k__‐connected graph with no 3‐cycle contains an edge whose contraction results in a __k__‐connected graph and use this to prove that every (__k__ + 3)‐connected graph contains a cycle whose deletion results in a __k__‐connected graph. This settles a problem of L. Lo