Some Identities for Enumerators of Circulant Graphs
Valery Liskovets
DOI: 10.1023/B:JACO.0000011937.70237.0b
Abstract
We establish analytically several new identities connecting enumerators of different types of circulant graphs mainly of prime, twice prime and prime-squared orders. In particular, it is shown that the half-sum of the number of undirected circulants and the number of undirected self-complementary circulants of prime order is equal to the number of directed self-complementary circulants of the same order. Several identities hold only for prime orders p such that ( p + 1)/2 is also prime. Some conjectured generalizations and interpretations are discussed.
Pages: 189–209
Keywords: cycle index; cyclic group; nearly doubled primes; cunningham chain; self-complementary graph; regular tournament
Full Text: PDF
References
1. B. Alspach, J. Morris, and V. Vilfred, “Self-complementary circulant graphs,” Ars Combinatoria 53 (1999), 187-191.
2. R. Baillie, “New primes of the form k \cdot 2n + 1,” Math. Comput. 33(148) (1979), 1333-1336.
3. C.Y. Chao and J.G. Wells, “A class of vertex-transitive digraphs,” J. Combin. Th. B 32(3) (1982), 336-346.
4. G.L. Chia and C.K. Lim, “A class of self-complementary vertex-transitive digraphs,” J. Graph Th. 10(2) (1986), 241-249.
5. B. Elspas and J. Turner, “Graphs with circulant adjacency matrices,” J. Combin. Th. 9(3) (1970), 297-307.
6. A. Farrugia, Self-Complementary Graphs and Generalisations: A Comprehensive Reference Manual, Master's Thesis, Univ. of Malta (1999) (currently available at http://www.math.uwaterloo. ca/~afarrugia/sc-graph.html).
7. T. Forbes, “Prime clasters and Cunningham chains,” Math. Comput. 68(228) (1999), 1739-1747.
8. D. Fron\check cek, A. Rosa and J. \check Sirá\check n, “The existence of selfcomplementary circulant graphs,” Europ. J. Combin. 17(7) (1996), 625-628.
9. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
10. M. Klin, V. Liskovets, and R. P\ddot oschel, “Analytical enumeration of circulant graphs with primesquared number of vertices,” Sém. Lotharing. Combin., 36 (1996), B36d (currently available at
2. R. Baillie, “New primes of the form k \cdot 2n + 1,” Math. Comput. 33(148) (1979), 1333-1336.
3. C.Y. Chao and J.G. Wells, “A class of vertex-transitive digraphs,” J. Combin. Th. B 32(3) (1982), 336-346.
4. G.L. Chia and C.K. Lim, “A class of self-complementary vertex-transitive digraphs,” J. Graph Th. 10(2) (1986), 241-249.
5. B. Elspas and J. Turner, “Graphs with circulant adjacency matrices,” J. Combin. Th. 9(3) (1970), 297-307.
6. A. Farrugia, Self-Complementary Graphs and Generalisations: A Comprehensive Reference Manual, Master's Thesis, Univ. of Malta (1999) (currently available at http://www.math.uwaterloo. ca/~afarrugia/sc-graph.html).
7. T. Forbes, “Prime clasters and Cunningham chains,” Math. Comput. 68(228) (1999), 1739-1747.
8. D. Fron\check cek, A. Rosa and J. \check Sirá\check n, “The existence of selfcomplementary circulant graphs,” Europ. J. Combin. 17(7) (1996), 625-628.
9. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
10. M. Klin, V. Liskovets, and R. P\ddot oschel, “Analytical enumeration of circulant graphs with primesquared number of vertices,” Sém. Lotharing. Combin., 36 (1996), B36d (currently available at