5-Shredders in 5-connected graphs

被引：2

作者：

Egawa, Yoshimi ^{[1
]}

Okadome, Yumiko ^{[1
]}

Takatou, Masanori ^{[1
]}

机构：

[1] Tokyo Univ Sci, Dept Math Informat Sci, Shinjuku Ku, Tokyo 1628601, Japan

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 06期

关键词：

Graph Connectivity; Shredder; Upper bound;

D O I：

10.1016/j.disc.2008.02.028

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 G is a 5-connected graph with |V(G)| >= 135, then the number of shredders of cardinality 5 of G is less than or equal to (2|V(G)| - 10)/3. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：1565 / 1574

页数：10

共 8 条

[1] Cheriyan J., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P37, DOI 10.1145/237814.237826
[2] EGAWA Y, J GRAPH THE IN PRESS
[3] Jordán T, 1999, J GRAPH THEOR, V31, P195
[4] On shredders and vertex connectivity augmentation
Liberman, Gilad
Nutov, Zeev
[J]. JOURNAL OF DISCRETE ALGORITHMS, 2007, 5 (01) : 91 - 101
[5] Nutov Z, 2007, ARS COMBINATORIA, V83, P213
[6] TAKATOU M, 2008, AKCE INT J IN PRESS, V5
[7] Takatou M, 2005, AKCE INT J GRAPHS CO, V2, P25
[8] Tsugaki M., 2003, SUT J MATH, V39, P211

← 1 →