Vertex-disjoint paths in Cayley color graphs

被引：0
|
作者：
Kulasinghe, P [1 ]
Bettayeb, S
机构：
[1] Louisiana State Univ, Dept Elect & Comp Engn, Baton Rouge, LA 70803 USA
[2] Southern Univ, Dept Comp Sci, Baton Rouge, LA 70813 USA
来源：
COMPUTERS AND ARTIFICIAL INTELLIGENCE | 1997年 / 16卷 / 06期
关键词：
Cayley color graph; Cayley graph; cost subgraph; interconnection network; strong connectivity; vertex symmetry;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
In this paper, we study the strong connectivity of Cayley color graphs when a certain number of vertices are removed. We prove that there are \Delta\ vertex-disjoint paths from every vertex to every other vertex in a Cayley color graph associated with a finite group Gamma and a non redundant generating set Delta for Gamma. We also extend this result to a certain class of Cayley graphs.
引用
收藏
页码：583 / 597
页数：15
相关论文
共 50 条
  • [1] On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups
    Lai, Cheng-Nan
    THEORETICAL COMPUTER SCIENCE, 2015, 571 : 10 - 20
  • [2] On the Existence of All Shortest Vertex-Disjoint Paths in Cayley Graphs of Abelian Groups
    Lai, Cheng-Nan
    INTELLIGENT SYSTEMS AND APPLICATIONS (ICS 2014), 2015, 274 : 92 - 103
  • [3] Vertex-disjoint paths joining adjacent vertices in faulty hypercubes
    Cheng, Dongqin
    THEORETICAL COMPUTER SCIENCE, 2019, 795 : 219 - 224
  • [4] Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs
    Chen, Xie-Bin
    INFORMATION PROCESSING LETTERS, 2010, 110 (06) : 203 - 205
  • [5] Vertex-Transitive Haar Graphs That Are Not Cayley Graphs
    Conder, Marston D. E.
    Estelyi, Istvan
    Pisanski, Tomaz
    DISCRETE GEOMETRY AND SYMMETRY: DEDICATED TO KAROLY BEZDEK AND EGON SCHULTE ON THE OCCASION OF THEIR 60TH BIRTHDAYS, 2018, 234 : 61 - 70
  • [6] Cyclic Vertex Connectivity of Trivalent Cayley Graphs
    Ke, Jenn-Yang
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2018, E101D (07): : 1828 - 1834
  • [7] On Small Separations in Cayley and Vertex Transitive Graphs
    Giannoudovardi, Martha
    JOURNAL OF GRAPH THEORY, 2016, 83 (01) : 92 - 104
  • [8] A Kind Of Conditional Vertex Connectivity Of Cayley Graphs Generated By Wheel Graphs
    Luo, Zuwen
    Xu, Liqiong
    COMPUTER JOURNAL, 2020, 63 (09) : 1372 - 1384
  • [9] Large Cayley Graphs and Vertex-Transitive Non-Cayley Graphs of Given Degree and Diameter
    Macbeth, Heather
    Siagiova, Jana
    Siran, Jozef
    Vetrik, Tomas
    JOURNAL OF GRAPH THEORY, 2010, 64 (02) : 87 - 98
  • [10] Vertex primitive s-transitive Cayley graphs
    Li, Jing Jian
    Yang, Jing
    Zhu, Wen Ying
    DISCRETE MATHEMATICS, 2020, 343 (09)
12345