×

zbMATH — the first resource for mathematics

On cycle permutation graphs. (English) Zbl 0559.05053
Cycle permutation graphs C(n,\(\alpha)\) are those permutation graphs where the underlying graph is a cycle with n vertices of which \(\alpha\) is a permutation. For some special types of cycle permutation graphs arising from certain kinds of permutations \(\alpha\) the crossing numbers are determined. Among these permutations are transpositions and cyclic permutations. The second part of the paper studies the problem of which permutations yield isomorphic permutation graphs (for the same base graph). For the so-called k-twisted prism (where the permutation is a k- cycle) all permutations yielding isomorphic cycle permutation graphs are characterized.
Reviewer: W.Dörfler

MSC:
05C99 Graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alspach, B., The classification of Hamiltonian generalized Petersen graphs, Graph theory newsletter, 11, 3, (1982), Abstract
[2] Alspach, B.; Robinson, P.; Rosenfield, M., A result on Hamiltonian cycles in generalized Petersen graphs, J. combin. theory, 31, 225-231, (1981), Ser. B · Zbl 0468.05054
[3] Behzad, M.; Chartrand, G.; Lesniak-Foster, L., Graphs and digraphs, (1979), Wadsworth Boston · Zbl 0403.05027
[4] Castagna, F.; Prins, G., Every generalized Petersen graph has a Tait coloring, Pacific J. math., 40, 1, 53-58, (1972) · Zbl 0236.05106
[5] Chartrand, G.; Harary, F., Planar permutation graphs, Ann. inst. H. poincare, III, 4, 433-438, (1967) · Zbl 0162.27605
[6] Dörfler, W., Automorphisms and isomorphisms of permutation graphs, Colloques inter., C.N.R.S., Problèmes combinatorics et théorie des graphs, 109-110, (1978), No. 260 · Zbl 0413.05063
[7] Dörfler, W., On mapping graphs and permutations graphs, Math. slovaca, 28, 3, 277-288, (1978) · Zbl 0421.05035
[8] Exoo, J.; Harary, F.; Kabell, J., The crossing numbers of some generalized Petersen graphs, Math. scand., 48, 2, 184-188, (1981) · Zbl 0442.05021
[9] Hedetniemi, S., On classes of graphs defined by special cutsets of lines, (), 171-190, Lecture Notes in Mathematics
[10] Klee, V., Which generalized prisms admit H-circuits, (), 173-178, Lecture Notes in Mathematics
[11] B. Piazza, Properties of permutation graphs, Ph.D. dissertation, Clemson University, in progress. · Zbl 0695.05041
[12] Pisanski, T.; Shawe-Taylor, J., Search for minimal trivalent cycle permutation graphs with girth 9, Discrete math., 36, 1, 113-115, (1981) · Zbl 0458.05055
[13] Ringeisen, R., Crossing #’s of permutation graphs of cycles, Notices amer. math soc., 26, 1, A-26, (1979), (Abstract)
[14] R. Sosic, private communication.
[15] S. Stueckle and R. Ringeisen, Cycle permutation graphs and generalized Petersen graphs, submitted for publication. · Zbl 0535.05055
[16] Watkins, M., A theorem on Tait colorings with an application to the generalized Petersen graphs, J. combin. theory, 6, 152-164, (1969) · Zbl 0175.50303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.