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 条
  • [1] A new self-stabilizing algorithm for maximal p-star decomposition of general graphs
    Neggazi, Brahim
    Haddad, Mohammed
    Kheddouci, Hamamache
    INFORMATION PROCESSING LETTERS, 2015, 115 (11) : 892 - 898
  • [2] Graph decomposition approaches for terminology graphs
    Biha, Mohamed Didi
    Kaba, Bangaly
    Meurs, Marie-Jean
    SanJuan, Eric
    MICAI 2007: ADVANCES IN ARTIFICIAL INTELLIGENCE, 2007, 4827 : 883 - +
  • [3] DECOMPOSITION OF COMPLETE GRAPHS INTO SMALL GRAPHS
    Froncek, Dalibor
    OPUSCULA MATHEMATICA, 2010, 30 (03) : 277 - 280
  • [4] Decomposition of complete equipartite graphs into paths and cycles of length 2p
    Ezhilarasi, A. Pauline
    Muthusamy, A.
    DISCRETE MATHEMATICS, 2023, 346 (01)
  • [5] Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs
    Kolotoglu, Emre
    JOURNAL OF COMBINATORIAL DESIGNS, 2013, 21 (11) : 524 - 530
  • [6] A Self-stabilizing Algorithm for Maximal p-Star Decomposition of General Graphs
    Neggazi, Brahim
    Turau, Volker
    Haddad, Mohammed
    Kheddouci, Hamamache
    STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2013, 2013, 8255 : 74 - 85
  • [7] Homogeneous sets in graphs and a chromatic multisymmetric function
    Crew, Logan
    Haithcock, Evan
    Reynes, Josephine
    Spirkl, Sophie
    ADVANCES IN APPLIED MATHEMATICS, 2024, 158
  • [8] Edge decomposition of complete tripartite graphs
    Edwards, K
    DISCRETE MATHEMATICS, 2003, 272 (2-3) : 269 - 275
  • [9] DECOMPOSITION OF COMPLETE GRAPHS INTO TRIANGLES AND CLAWS
    Fu, Chin-Mei
    Lin, Yuan-Lung
    Lo, Shu-Wen
    Hsu, Yu-Fong
    TAIWANESE JOURNAL OF MATHEMATICS, 2014, 18 (05): : 1563 - 1581
  • [10] Decomposition of Complete Graphs into Arbitrary Trees
    G. Sethuraman
    V. Murugan
    Graphs and Combinatorics, 2021, 37 : 1191 - 1203
12345