On the Toughness of Cycle Permutation Graphs

被引：0
作者：
Chao Chong-Yun
Shaocen Han
机构：
[1] University of Pittsburgh,Department of Mathematics
来源：
Czechoslovak Mathematical Journal | 2001年 / 51卷 / 2期
关键词：
cycle permutation graph; toughness; maximal chain;
D O I：
10.1023/A:1013786612087
中图分类号：
学科分类号：
摘要：
Motivated by the conjectures in [11], we introduce the maximal chains of a cycle permutation graph, and we use the properties of maximal chains to establish the upper bounds for the toughness of cycle permutation graphs. Our results confirm two conjectures in [11].
引用
收藏
页码：239 / 260
页数：21
相关论文
共 14 条
  • [1] Chao C.Y.(1992)A note on the toughness of generalized Petersen graphs J. Math. Res. Exposition 12 183-186
  • [2] Han S.C.(1997)On the classification and toughness of generalized permutation star-graphs Czechoslovak Math. J. 47 431-452
  • [3] Chao C.Y.(1979)Tough graphs and hamiltonian circuits Math. Slovaca 28 215-228
  • [4] Han S.C.(1979)On mapping graphs and permutation graphs Math. Slovaca 28 277-288
  • [5] Chvátal V.(1996)The toughness of cubic graphs Graphs Combin. 12 17-22
  • [6] Döfler W.(1991)On the vulnerability of permutation graphs of complete and complete bipartite graphs Ars Combin. 31 149-157
  • [7] Goddard W.(1990)On the vulnerability of cycle permutation graphs Ars Combin. 29 289-296
  • [8] Guichard D.(1960)On the algebraic theory of graph colorings J. Combin. Theory 1 15-50
  • [9] Piazza B.(undefined)undefined undefined undefined undefined-undefined
  • [10] Stueckle S.(undefined)undefined undefined undefined undefined-undefined
12