✦ LIBER ✦

k-shredders in k-connected graphs

✍ Scribed by Yoshimi Egawa

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 184 KB
Volume: 59
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20336

No coin nor oath required. For personal study only.

✦ Synopsis

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 show a better bound for k = 4). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 239–259, 2008

📜 SIMILAR VOLUMES

Minimally (k, k)-edge-connected graphs

✍ Kamal Hennayake; Hong-Jian Lai; Deying Li; Jingzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB 👁 1 views

## Abstract For an integer __l__ > 1, the __l__‐edge‐connectivity of a connected graph with at least __l__ vertices is the smallest number of edges whose removal results in a graph with __l__ components. A connected graph __G__ is (__k__, __l__)‐edge‐connected if the __l__‐edge‐connectivity of __G_

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

Minimal k-arc connected graphs

✍ D. R. Fulkerson; L. S. Shapley 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB

Fast Algorithms for k-Shredders and k-No

Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation

✍ Joseph Cheriyan; Ramakrishna Thurimella 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 321 KB

A k-separator k-shredder of a k-node connected undirected graph is a set of k Ž . nodes whose removal results in two or more three or more connected components. Let n denote the number of nodes. Solving an open question, we show that the problem of counting the number of k-separators is ࠻P-complete.

Cycles passing through k + 1 vertices in

Cycles passing through k + 1 vertices in k-connected graphs

✍ Jun Fujisawa; Tomoki Yamashita 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 1 views

## Abstract In this article, we prove the following theorem. Let __k__ ≥ 3 be an integer, __G__ be a __k__‐connected graph with minimum degree __d__ and __X__ be a set of __k__ + 1 vertices on a cycle. Then __G__ has a cycle of length at least min {2d,|V(G)|} passing through __X__. This result give