Matjaž Krnc ; Tomaž Pisanski - Generalized Petersen graphs and Kronecker covers

dmtcs:4592 - Discrete Mathematics & Theoretical Computer Science, November 11, 2019, vol. 21 no. 4 - https://doi.org/10.23638/DMTCS-21-4-15
Generalized Petersen graphs and Kronecker covers

Authors: Matjaž Krnc ; Tomaž Pisanski

    The family of generalized Petersen graphs $G(n,k)$, introduced by Coxeter et al. [4] and named by Mark Watkins (1969), is a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. The Kronecker cover $KC(G)$ of a simple undirected graph $G$ is a a special type of bipartite covering graph of $G$, isomorphic to the direct (tensor) product of $G$ and $K_2$. We characterize all the members of generalized Petersen graphs that are Kronecker covers, and describe the structure of their respective quotients. We observe that some of such quotients are again generalized Petersen graphs, and describe all such pairs.The results of this paper have been presented at EUROCOMB 2019 and an extended abstract has been published elsewhere.


    Volume: vol. 21 no. 4
    Section: Graph Theory
    Published on: November 11, 2019
    Accepted on: November 11, 2019
    Submitted on: June 17, 2018
    Keywords: Generalized Petersen graphs,Kronecker cover,generalised Petersen graphs,MSC: 57M10, 05C10, 05C25,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
    Fundings :
      Source : OpenAIRE Research Graph
    • Renewable materials and healthy environments research and innovation centre of excellence; Funder: European Commission; Code: 739574

    Share

    Consultation statistics

    This page has been seen 1108 times.
    This article's PDF has been downloaded 603 times.