P-COMPONENTS AND THE HOMOGENEOUS DECOMPOSITION OF GRAPHS

Authors
JAMISON B OLARIU S
Citation
B. Jamison et S. Olariu, P-COMPONENTS AND THE HOMOGENEOUS DECOMPOSITION OF GRAPHS, SIAM journal on discrete mathematics, 8(3), 1995, pp. 448-463
Citations number
15
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
8
Issue
3
Year of publication
1995
Pages
448 - 463
Database
ISI
SICI code
0895-4801(1995)8:3<448:PATHDO>2.0.ZU;2-U
Abstract
In this paper we introduce and investigate the notion of p-connectedne ss. As it turns out, this concepts leads naturally to a unique tree re presentation for arbitrary graphs: the leaves of this tree are the p-c onnected components along with weak vertices, that is, vertices of the graph that belong to no p-connected component. We then show how to re fine this decomposition to obtain a new decomposition that extends the well-known modular decomposition.