×

Enumerating graphs via even/odd dichotomy. (English) Zbl 1394.05058

Summary: Following the author et al. [Ars Math. Contemp. 10, No. 2, 427–437 (2016; Zbl 1351.05106)], an automorphism of a graph is said to be even/odd if it acts on the vertex set of the graph as an even/odd permutation. In this paper the formula for calculating the number of graphs of order \(n\) admitting odd automorphisms and the formula for calculating the number of graphs of order \(n\) without odd automorphisms are given together with their asymptotic estimates.
Such numbers are also considered for the subclass of vertex-transitive graphs. A positive integer \(n\) is a Cayley number if every vertex-transitive graph of order \(n\) is a Cayley graph. In analogy, a positive integer \(n\) is said to be a vertex-transitive-odd number (in short, a VTO-number) if every vertex-transitive graph of order \(n\) admits an odd automorphism. It is proved that there exists infinitely many VTO numbers which are square-free and have arbitrarily long prime factorizations. Further, it is proved that Cayley numbers congruent to 2 modulo 4, cubefree nilpotent Cayley numbers congruent to 3 modulo 4, and numbers of the form \(2 p\), \(p\) a prime, are VTO numbers. At the other extreme, it is proved that for a positive integer \(n\) the complete graph \(K_n\) and its complement are the only vertex-transitive graphs of order \(n\) admitting odd automorphisms if and only if \(n\) is a Fermat prime.

MSC:

05C30 Enumeration in graph theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures

Citations:

Zbl 1351.05106
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B.; Mishna, M., Enumeration of Cayley graphs and digraphs, Discrete Math., 256, 527-539, (2002) · Zbl 1023.05076
[2] Alspach, B.; Sutcliffe, R. J., Vertex-transitive graphs of order \(2 p\), Annals New York Acad. Sci., 319, 19-27, (1979)
[3] Baik, Y. G.; Feng, Y. Q.; Sim, H. S.; Xu, M., On the normality of Cayley graphs of abelian groups, Algebra Colloq., 5, 297-304, (1998) · Zbl 0904.05037
[4] Bosma, W.; Cannon, J.; Playoust, C., The {\scmagma} algebra system I: the user language, J. Symbolic Comput., 24, 235-265, (1997) · Zbl 0898.68039
[5] Dobson, E.; Spiga, P.; Verret, G., Cayley graphs on abelian groups, Combinatorica, 36, 4, 371-393, (2016) · Zbl 1399.05100
[6] Dobson, T.; Spiga, P., Cayley numbers with arbitrarily many distinct prime factors, J. Combin. Theory Ser. B, 122, 301-310, (2017) · Zbl 1350.05058
[7] Feng, Y.-Q., On vertex-transitive graphs of odd prime-power order, Discrete Math., 248, 265-269, (2002) · Zbl 0990.05067
[8] Hammack, R.; Imrich, W.; S, ., Handbook of product graphs, (2011), CRC Press · Zbl 1283.05001
[9] Harary, F., The number of linear, directed, rooted, and connected graphs, Trans. Amer. Math. Soc., 78, 445-463, (1955) · Zbl 0065.16702
[10] Harary, F.; Palmer, E. M., Graphical enumeration, (1973), Academic Press New York-London · Zbl 0266.05108
[11] Hujdurović, A.; Kutnar, K.; Marušič, D., Odd automorphisms in vertex-transitive graphs, Ars Math. Contemp., 10, 427-437, (2016) · Zbl 1351.05106
[12] Imrich, W., Graphical regular representations of groups of odd order, (Combinatorics (Proc. Colloq., Keszthely, 1976), (1978), Bolyai-North-Holland), 611-621
[13] Iranmanesh, M. A.; Praeger, C. E., On non-Cayley vertex-transitive graphs of order a product of three primes, J. Combin. Theory Ser. B, 81, 1-19, (2001) · Zbl 1025.05033
[14] Jajcay, R.; širan, J., More constructions of vertex-transitive non-Cayley graphs based on counting closed walks, Australas. J. Combin., 14, 121-132, (1996) · Zbl 0872.05018
[15] K. Kutnar, D. Marušič, Odd extensions of transitive groups via symmetric graphs, manuscript.; K. Kutnar, D. Marušič, Odd extensions of transitive groups via symmetric graphs, manuscript.
[16] Li, C. H., On isomorphisms of finite Cayley graphs -a survey, Discrete Math., 256, 301-334, (2002) · Zbl 1018.05044
[17] Li, C. H.; Seress, A., On vertex-transitive non-Cayley graphs of square-free order, Des. Codes Cryptogr., 34, 265-281, (2005) · Zbl 1075.20002
[18] Malnič, A.; Marušič, D.; šparl, P.; Frelih, B., Symmetry structure of bicirculants, Discrete Math., 307, 409-414, (2007) · Zbl 1110.05045
[19] Marušič, D., On vertex symmetric digraphs, Disctere Math., 36, 69-81, (1981) · Zbl 0459.05041
[20] Marušič, D., Cayley properties of vertex symmetric graphs, Ars Combin., 16, 297-302, (1983) · Zbl 0535.05034
[21] Marušič, D., Vertex-transitive graphs and digraphs of order \(p^k\), Annals of Discrete Math., 115, 115-128, (1985) · Zbl 0571.05024
[22] Marušič, D.; Scapellato, R., Characterizing vertex-transitive \(p q\)-graphs with an imprimitive automorphism subgroup, J. Graph Theory, 16, 375-387, (1992) · Zbl 0764.05035
[23] McKay, B. D.; Praeger, C. E., Vertex-transitive graphs which are not Cayley graphs. I, J. Aust. Math. Soc. Ser. A, 56, 1, 53-63, (1994) · Zbl 0795.05070
[24] McKay, B. D.; Praeger, C. E., Vertex-transitive graphs that are not Cayley graphs. II, J. Graph Theory, 22, 321-334, (1996) · Zbl 0864.05041
[25] Oberschelp, W., Kombinatorische anzahlbestimmungen in relationen, Math. Ann., 174, 53-78, (1967) · Zbl 0155.35002
[26] Pakianathan, J.; Shankar, K., Nilpotent numbers, Amer. Math. Monthly, 107, 631-634, (2000) · Zbl 0986.20026
[27] Polya, G., Kombinatorische anzahlbestimmungen für gruppen, graphen und chemische verbindungen, Acta Math., 68, 145-254, (1937) · JFM 63.0547.04
[28] Potočnik, P.; Spiga, P.; Verret, G., Asymptotic enumeration of vertex-transitive graphs of fixed valency, J. Combin. Theory Ser. B, 122, 221-240, (2017) · Zbl 1350.05064
[29] Redfield, J. H., The theory of graph-reduced distributions, Amer. J. Math., 49, 433-455, (1927) · JFM 53.0106.03
[30] G. Royle, Transitive graphs, http://school.maths.uwa.edu.au/ gordon/trans/; G. Royle, Transitive graphs, http://school.maths.uwa.edu.au/ gordon/trans/ · Zbl 0683.20002
[31] Seress, A.; vertex transitive, On., On vertex-transitive non-Cayley graphs of order \(p q r\), Discrete Math., 182, 279-292, (1998)
[32] Turner, J., Point-symmetric graphs with a prime number of points, J. Combin. Theory, 3, 136-145, (1967) · Zbl 0161.20803
[33] Wielandt, H., Finite permutation groups (R. bercov, trans.), (1964), Academic Press New York-London, (in German)
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.