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 条
  • [21] DECOMPOSITION OF COMPLETE GRAPHS INTO SMALL GENERALIZED PRISMS
    Cichacz, Sylwia
    Froncek, Dalibor
    Meszka, Mariusz
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2013, 10 (03) : 285 - 293
  • [22] Decomposition dimension of Cartesian product of some graphs
    Reji, T.
    Ruby, R.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (04)
  • [23] Decomposition of complete bipartite graphs into paths and cycles
    Jeevadoss, S.
    Muthusamy, A.
    DISCRETE MATHEMATICS, 2014, 331 : 98 - 108
  • [24] Decomposition of geometric graphs into star-forests
    Pach, Jano
    Saghafian, Morteza
    Schnider, Patrick
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2025, 129
  • [25] Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs
    Thomas Bellitto
    Tereza Klimošová
    Martin Merker
    Marcin Witkowski
    Yelena Yuditsky
    Graphs and Combinatorics, 2021, 37 : 2595 - 2599
  • [26] Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
    Bian, Zhengbing
    Gu, Qian-Ping
    Marzban, Marjan
    Tamaki, Hisao
    Yoshitake, Yumi
    PROCEEDINGS OF THE TENTH WORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENTS AND THE FIFTH WORKSHOP ON ANALYTIC ALGORITHMICS AND COMBINATORICS, 2008, : 152 - +
  • [27] Colorful edge decomposition of graphs: Some polynomial cases
    Dehghan, Ali
    Sadeghi, Mohammad-Reza
    DISCRETE APPLIED MATHEMATICS, 2017, 231 : 155 - 165
  • [28] Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree
    Kim, Seog-Jin
    Kostochka, Alexandr V.
    West, Douglas B.
    Wu, Hehui
    Zhu, Xuding
    JOURNAL OF GRAPH THEORY, 2013, 74 (04) : 369 - 391
  • [29] Decomposition of Product Graphs into Paths and Cycles of Length Four
    S. Jeevadoss
    A. Muthusamy
    Graphs and Combinatorics, 2016, 32 : 199 - 223
  • [30] Decomposition of product graphs into paths and stars on five vertices
    Ilayaraja, M.
    Sowndhariya, K.
    Muthusamy, A.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 777 - 783
12345