×

A new generalization of generalized Petersen graphs. (English) Zbl 1441.05103

Summary: We discuss a new family of cubic graphs, which we call group divisible generalized Petersen graphs (GDGP-graphs), that bears a close resemblance to the family of generalized Petersen graphs; both in definition and properties. The focus of our paper is on determining the algebraic properties of graphs from our new family. We look for highly symmetric graphs, e.g., graphs with large automorphism groups, and vertex- or arc-transitive graphs. In particular, we present arithmetic conditions for the defining parameters that guarantee that graphs with these parameters are vertex-transitive or Cayley, and we find one arc-transitive GDGP-graph which is neither a \(CQ\) graph of Y.-Q. Feng and K. Wang [Eur. J. Comb. 24, No. 6, 719–731 (2003; Zbl 1035.05048)], nor a generalized Petersen graph.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

Citations:

Zbl 1035.05048

Software:

Mathematica; GAP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Boben, T. Pisanski and A. ˇZitnik,I-graphs and the corresponding configurations,J. Combin. Des.13(2005), 406-424, doi:10.1002/jcd.20054. · Zbl 1076.05065
[2] I. Z. Bouwer, W. W. Chernoff, B. Monson and Z. Star,The Foster Census, Charles Babbage Research Centre, 1988. · Zbl 0639.05043
[3] M. Conder and P. Dobcs´anyi, Trivalent symmetric graphs on up to 768 vertices,J. Combin. Math. Combin. Comput.40(2002), 41-63. · Zbl 0996.05069
[4] M. D. E. Conder, I. Est´elyi and T. Pisanski, Vertex-transitive Haar graphs that are not Cayley graphs, in:Discrete geometry and symmetry, Springer, Cham, volume 234 ofSpringer Proc. Math. Stat., pp. 61-70, 2018. · Zbl 1409.05100
[5] M. D. E. Conder, T. Pisanski and A. ˇZitnik,GI-graphs: a new class of graphs with many symmetries,J. Algebraic Combin.40(2014), 209-231, doi:10.1007/s10801-013-0484-3. · Zbl 1297.05108
[6] H. S. M. Coxeter, Self-dual configurations and regular graphs,Bull. Amer. Math. Soc.56(1950), 413-455, doi:10.1090/S0002-9904-1950-09407-5. · Zbl 0040.22803
[7] Y.-Q. Feng and K. Wang,s-regular cyclic coverings of the three-dimensional hypercubeQ3, European J. Combin.24(2003), 719-731, doi:10.1016/S0195-6698(03)00055-6. · Zbl 1035.05048
[8] B. Frelih and K. Kutnar, Classification of cubic symmetric tetracirculants and pentacirculants, European J. Combin.34(2013), 169-194, doi:10.1016/j.ejc.2012.08.005. · Zbl 1254.05074
[9] R. Frucht, J. E. Graver and M. E. Watkins, The groups of the generalized Petersen graphs,Proc. Cambridge Philos. Soc.70(1971), 211-218, doi:10.1017/s0305004100049811. · Zbl 0221.05069
[10] J. L. Gross and T. W. Tucker,Topological graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1987, a WileyInterscience Publication. · Zbl 0621.05013
[11] K. Jasenˇc´akov´a,m-spanning generalized Petersen graphs, Master’s thesis, Comenius University, Bratislava, 2017.
[12] J. Karlub´ık,Applications of software package GAP in conjecture formulation and testing in algebraic graph theory, Master’s thesis, Comenius University, Bratislava, 2018.
[13] M. Lovreˇciˇc Saraˇzin, A note on the generalized Petersen graphs that are also Cayley graphs,J. Combin. Theory Ser. B69(1997), 226-229, doi:10.1006/jctb.1997.1729. · Zbl 0867.05027
[14] M. Lovreˇciˇc Saraˇzin and D. Maruˇsiˇc, Vertex-transitive expansions of(1,3)-trees,Discrete Math.310(2010), 1772-1782, doi:10.1016/j.disc.2009.11.036. · Zbl 1222.05103
[15] M. Lovreˇciˇc Saraˇzin, W. Pacco and A. Previtali, Generalizing the generalized Petersen graphs, Discrete Math.307(2007), 534-543, doi:10.1016/j.disc.2005.09.043. · Zbl 1111.05048
[16] R. Nedela and M. ˇSkoviera, Which generalized Petersen graphs are Cayley graphs?,J. Graph Theory19(1995), 1-11, doi:10.1002/jgt.3190190102. · Zbl 0812.05026
[17] T. Pisanski, A classification of cubic bicirculants,Discrete Math.307(2007), 567-578, doi: 10.1016/j.disc.2005.09.053. · Zbl 1109.05055
[18] M. E. Watkins, Vertex-transitive graphs that are not Cayley graphs, in:Cycles and rays (Montreal, PQ, 1987), Kluwer Acad. Publ., Dordrecht, volume 301 ofNATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pp. 243-256, 1990. · Zbl 0705.05039
[19] E. W. Weisstein, Crossed Prism Graph, 25th April 2017.,http://mathworld.wolfram. com/CrossedPrismGraph.html.
[20] J.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.