P-COMPONENTS AND THE HOMOGENEOUS DECOMPOSITION OF GRAPHS

作     者：JAMISON, B OLARIU, S 

作者机构：OLD DOMINION UNIVDEPT COMP SCINORFOLKVA 23529 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1995年第8卷第3期

页      面：448-463页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：GRAPH DECOMPOSITION P-CONNECTEDNESS GRAPH ALGORITHMS STRUCTURAL GRAPH THEORY 

摘      要：In this paper we introduce and investigate the notion of p-connectedness. As it turns out, this concepts leads naturally to a unique tree representation for arbitrary graphs: the leaves of this tree are the p-connected components along with weak vertices, that is, vertices of the graph that belong to no p-connected component. We then show how to refine this decomposition to obtain a new decomposition that extends the well-known modular decomposition.