RECURSIVELY ARBITRARILY VERTEX-DECOMPOSABLE GRAPHS

被引：10

作者：

Baudon, Olivier ^{[1
,2
]}

Gilbert, Frediric ^{[1
,2
]}

Wozniak, Mariusz ^{[3
]}

机构：

[1] Univ Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France

[2] CNRS, UMR 5800, LaBRI, F-33400 Talence, France

[3] AGH Univ Sci & Technol, Fac Appl Math, PL-30059 Krakow, Poland

来源：

OPUSCULA MATHEMATICA | 2012年 / 32卷 / 04期

关键词：

arbitrary vertex decomposable (AVD) graph; recursively AVD graphs;

D O I：

10.7494/OpMath.2012.32.4.689

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A graph G = (V , E) is arbitrarily vertex decomposable if for any sequence T of positive integers adding up to vertical bar V vertical bar, there is a sequence of vertex-disjoint subsets of V whose orders are given by T, and which induce connected graphs. The main aim of this paper is to study the recursive version of this problem. We present a solution for trees, suns, and partially for a class of 2-connected graphs called balloons.

引用

页码：689 / 706

页数：18

共 12 条

[1] A degree bound on decomposable trees [J].

Barth, D ;

Fournier, H .

DISCRETE MATHEMATICS, 2006, 306 (05) :469-477

[2] Decomposable trees: a polynomial algorithm for tripodes [J].

Barth, D ;

Baudon, O ;

Puech, J .

DISCRETE APPLIED MATHEMATICS, 2002, 119 (03) :205-216

[3] On the shape of decomposable trees [J].

Barth, Dominique ;

Fournier, Herve ;

Ravaux, Romain .

DISCRETE MATHEMATICS, 2009, 309 (12) :3882-3887

[4] RECURSIVELY ARBITRARILY VERTEX-DECOMPOSABLE SUNS [J].

Baudon, Olivier ;

Gilbert, Frederic ;

Wozniak, Mariusz .

OPUSCULA MATHEMATICA, 2011, 31 (04) :533-547

[5]

DIESTEL R, 2005, GRAPH THEORY

[6]

Gould R., 1981, THEORY APPL GRAPHS, P297

[7]

Hornak M., 2003, OPUSCULA MATH, V23, P49

[8] On-line arbitrarily vertex decomposable trees [J].

Hornak, Mirko ;

Tuza, Zsolt ;

Wozniak, Mariusz .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (11) :1420-1429

[9] On-line arbitrarily vertex decomposable suns [J].

Kalinowski, Rafal ;

Pilsniak, Monika ;

Wozniak, Mariusz ;

Ziolo, Irmina A. .

DISCRETE MATHEMATICS, 2009, 309 (22) :6328-6336

[10] Arbitrarily vertex decomposable suns with few rays [J].

Kalinowski, Rafal ;

Pilsniak, Monika ;

Wozniak, Mariusz ;

Ziolo, Irmina .

DISCRETE MATHEMATICS, 2009, 309 (11) :3726-3732

← 1 2 →