P-COMPONENTS AND THE HOMOGENEOUS DECOMPOSITION OF GRAPHS

被引：49
作者：
JAMISON, B [1 ]
OLARIU, S [1 ]
机构：
[1] OLD DOMINION UNIV,DEPT COMP SCI,NORFOLK,VA 23529
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 1995年 / 8卷 / 03期
关键词：
GRAPH DECOMPOSITION; P-CONNECTEDNESS; GRAPH ALGORITHMS; STRUCTURAL GRAPH THEORY;
D O I：
10.1137/S0895480191196812
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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.
引用
收藏
页码：448 / 463
页数：16
相关论文
共 50 条
  • [41] Decomposition of hypercube graphs into paths and cycles having k edges
    Saranya, D.
    Jeevadoss, S.
    Nalini, V.
    Chitra, V.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2025,
  • [42] On computing the 2-vertex-connected components of directed graphs
    Jaberi, Raed
    DISCRETE APPLIED MATHEMATICS, 2016, 204 : 164 - 172
  • [43] Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs
    Kammer, Frank
    Kratsch, Dieter
    Laudahn, Moritz
    ALGORITHMICA, 2019, 81 (03) : 1180 - 1204
  • [44] Fast Connected Components Computation in Large Graphs by Vertex Pruning
    Lulli, Alessandro
    Carlini, Emanuele
    Dazzi, Patrizio
    Lucchese, Claudio
    Ricci, Laura
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2017, 28 (03) : 760 - 773
  • [45] Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs
    Frank Kammer
    Dieter Kratsch
    Moritz Laudahn
    Algorithmica, 2019, 81 : 1180 - 1204
  • [46] Decomposing certain equipartite graphs into sunlet graphs of length 2p
    Akwu, Abolape D.
    Ajayi, Deborah Olayide A.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2016, 13 (03) : 267 - 271
  • [47] Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
    Nicolai, F
    Szymczak, T
    NETWORKS, 2001, 37 (03) : 117 - 128
  • [48] Hamiltonicity of simplicial-connected graphs:: an algorithm based on clique decomposition
    Vallee, Thierry
    Bretto, Alain
    PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY: NEW GENERATIONS, 2008, : 904 - +
  • [49] A note on decomposition of complete equipartite graphs into gregarious 6-cycles
    Cho, Jung Rae
    BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2007, 44 (04) : 709 - 719
  • [50] DECOMPOSITION OF TENSOR PRODUCT OF COMPLETE GRAPHS INTO CYCLES AND STARS WITH FOUR EDGES
    Ezhilarasi, A. P.
    Ilayaraja, M.
    Muthusamy, A.
    TWMS JOURNAL OF APPLIED AND ENGINEERING MATHEMATICS, 2023, 13 (02): : 626 - 634
12345