On the p-connectedness of graphs -: a survey

被引：14
作者：
Babel, L
Olariu, S [1 ]
机构：
[1] Old Dominion Univ, Dept Comp Sci, Norfolk, VA 23529 USA
[2] Tech Univ Munich, Zentrum Math, D-80290 Munich, Germany
来源：
DISCRETE APPLIED MATHEMATICS | 1999年 / 95卷 / 1-3期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/S0166-218X(99)00062-1
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A graph is said to be p-connected if for every partition of its vertices into mio non-empty, disjoint, sets some chordless path with three edges contains vertices from both sets in the partition. As it turns out, p-connectedness generalizes the usual connectedness of graphs and leads, in a natural way, to a unique tree representation for arbitrary graphs. This paper reviews old and new results, both structural and algorithmic, about p-connectedness along with applications to various graph decompositions. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：11 / 33
页数：23
相关论文
共 53 条
[1]  
Aho A.V., 1974, The Design and Analysis of Computer Algorithms
[2]   Tree-like P4-connected graphs [J].
Babel, L .
DISCRETE MATHEMATICS, 1998, 191 (1-3) :13-23
[3]   On the structure of graphs with few P4s [J].
Babel, L ;
Olariu, S .
DISCRETE APPLIED MATHEMATICS, 1998, 84 (1-3) :1-13
[4]   Triangulating graphs with few P4's [J].
Babel, L .
DISCRETE APPLIED MATHEMATICS, 1998, 89 (1-3) :45-57
[5]  
BABEL L, 1997, THESIS U MUNCHEN
[6]  
BABEL L, 1997, M9711 TU MUNCH ZENTR
[7]  
BABEL L, IN PRESS DISCRETE AP
[8]  
BABEL S, 1997, LECT NOTES COMPUTER, V1335, P25
[9]  
BABEL S, 1996, LECT NOTES COMPUTER, V1197, P17
[10]  
Baumann S., 1996, M9615 TU MUNCH ZENTR
123456