Geodesic
On the toughness of cycle permutation graphs
Czechoslovak Mathematical Journal, Tome 51 (2001) no. 2, pp. 239-260 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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].
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].
Classification : 05C40, 05C58
Keywords: cycle permutation graph; toughness; maximal chain 
@article{CMJ_2001_51_2_a2,
     author = {Chao, Chong-Yun and Han, Shaocen},
     title = {On the toughness of cycle permutation graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {239--260},
     year = {2001},
     volume = {51},
     number = {2},
     mrnumber = {1844308},
     zbl = {0977.05073},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2001_51_2_a2/}
}
TY  - JOUR
AU  - Chao, Chong-Yun
AU  - Han, Shaocen
TI  - On the toughness of cycle permutation graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2001
SP  - 239
EP  - 260
VL  - 51
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2001_51_2_a2/
LA  - en
ID  - CMJ_2001_51_2_a2
ER  - 
%0 Journal Article
%A Chao, Chong-Yun
%A Han, Shaocen
%T On the toughness of cycle permutation graphs
%J Czechoslovak Mathematical Journal
%D 2001
%P 239-260
%V 51
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2001_51_2_a2/
%G en
%F CMJ_2001_51_2_a2
Chao, Chong-Yun; Han, Shaocen. On the toughness of cycle permutation graphs. Czechoslovak Mathematical Journal, Tome 51 (2001) no. 2, pp. 239-260. http://geodesic.mathdoc.fr/item/CMJ_2001_51_2_a2/

[1] D.  Bauer, E.  Schmeichel, and H. J.  Veldman: Some recent results on long cycles in tough graphs. Graph Theory, Combinatorics, and Applications—Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, Y.  Alavi, G.  Chartrand, O. R. Oellermann, and A. J. Schwenk (eds.), John Wiley & Sons, New York, 1991, pp. 113–121. | MR

[2] D.  Bauer, E.  Schmeichel, and H. J.  Veldman: Cycles in tough graphs-updating the last four years. Graph Theory, Combinatorics, and Applications—Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Y.  Alavi and A. J.  Schwenk (eds.), Wiley & Sons, New York, 1995, pp. 19–34. | MR

[3] C. Y.  Chao and S. C.  Han: A note on the toughness of generalized Petersen graphs. J. Math. Res. Exposition 12 (1992), 183–186. | MR

[4] C. Y. Chao and S. C.  Han: On the classification and toughness of generalized permutation star-graphs. Czechoslovak Math. J. 47 (1997), 431–452. | DOI | MR

[5] G.  Chartrand and R. J.  Wilson: The Petersen graph. Graphs and Applications, F.  Harary and J. S.  Maybee (eds.), John Wiley & Sons, 1982, pp. 69–99. | MR

[6] V.  Chvátal: Tough graphs and hamiltonian circuits. Math. Slovaca 28 (1979), 215–228. | MR

[7] W.  Döfler: On mapping graphs and permutation graphs. Math. Slovaca 28 (1979), 277–288. | MR

[8] K.  Ferland: On the toughness of some generalized Petersen graphs. Ars Combin. (1993), 65–88. | MR | Zbl

[9] W.  Goddard: The toughness of cubic graphs. Graphs Combin. 12 (1996), 17–22. | DOI | MR | Zbl

[10] D.  Guichard, B.  Piazza, and S.  Stueckle: On the vulnerability of permutation graphs of complete and complete bipartite graphs. Ars Combin. 31 (1991), 149–157. | MR

[11] B.  Piazza, R.  Ringeisen, and S.  Stueckle: On the vulnerability of cycle permutation graphs. Ars Combin. 29 (1990), 289–296. | MR

[12] W. T.  Tutte: On the algebraic theory of graph colorings. J.  Combin. Theory 1 (1960), 15–50. | DOI | MR