> Merkliste Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp: E-Artikel Titel: Which generalized petersen graphs are cayley graphs? Beteiligte: Nedela, Roman; Škoviera, Martin Erschienen: Wiley, 1995 Erschienen in: Journal of Graph Theory Sprache: Englisch DOI: 10.1002/jgt.3190190102 ISSN: 0364-9024; 1097-0118 Entstehung: Anmerkungen: Beschreibung: <jats:title>Abstract</jats:title><jats:p>The generalized Petersen graph <jats:italic>GP</jats:italic> (<jats:italic>n, k</jats:italic>), <jats:italic>n</jats:italic> ≤ 3, 1 ≥ <jats:italic>k</jats:italic> < <jats:italic>n</jats:italic>/2 is a cubic graph with vertex‐set {u<jats:sub>j</jats:sub>; i ϵ Z<jats:sub>n</jats:sub>} ∪ {v<jats:sub>j</jats:sub>; i ϵ Z<jats:sub>n</jats:sub>}, and edge‐set {u<jats:sub>i</jats:sub>u<jats:sub>i</jats:sub>, u<jats:sub>i</jats:sub>v<jats:sub>i</jats:sub>, v<jats:sub>i</jats:sub>v<jats:sub>i+k, iϵ</jats:sub>Z<jats:sub>n</jats:sub>}. In the paper we prove that</jats:p><jats:p>(i) <jats:italic>GP</jats:italic>(<jats:italic>n, k</jats:italic>) is a Cayley graph if and only if <jats:italic>k</jats:italic><jats:sup>2</jats:sup> 1 (mod <jats:italic>n</jats:italic>); and</jats:p><jats:p>(ii) <jats:italic>GP</jats:italic>(<jats:italic>n, k</jats:italic>) is a vertex‐transitive graph that is not a Cayley graph if and only if <jats:italic>k</jats:italic><jats:sup>2</jats:sup> ‐1 (mod <jats:italic>n</jats:italic>) or (<jats:italic>n, k</jats:italic>) = (10, 2), the exceptional graph being isomorphic to the 1‐skeleton of the dodecahedon.</jats:p><jats:p>The proof of (i) is based on the classification of orientable regular embeddings of the <jats:italic>n</jats:italic>‐dipole, the graph consisting of two vertices and <jats:italic>n</jats:italic> parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” <jats:italic>Proceedings of the Cambridge Philosophical Society</jats:italic>, Vol. 70 (1971), pp. 211‐218]. © 1995 John Wiley & Sons, Inc.</jats:p>