✦ LIBER ✦

Connectivity keeping paths in k-connected graphs

✍ Scribed by W. Mader

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 that every finite, k‐connected graph G of minimum degree at least ⌊3__k__/2⌋+m−1 for a positive integer m contains a path P of length m−1 such that G−V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.

📜 SIMILAR VOLUMES

Connectivity keeping trees in k-connecte

Connectivity keeping trees in k-connected graphs

✍ W. Mader 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

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.

Induced paths in 5-connected graphs

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB 👁 2 views

We show that between any two vertices of a 5-connected graph there exists an induced path whose vertices can be removed such that the remaining graph is 2-connected.

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

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

Subdivisions of large complete bipartite

Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs

✍ Thomas Böhme; Bojan Mohar; Riste Škrekovski; Michael Stiebitz 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

## Abstract It is proved that for every positive integers __k__, __r__ and __s__ there exists an integer __n__ = __n__(__k__,__r__,__s__) such that every __k__‐connected graph of order at least __n__ contains either an induced path of length __s__ or a subdivision of the complete bipartite graph __