Paley-type graphs of order a product of two distinct primes

Angsuman Das

Algebra and discrete mathematics, Tome 28 (2019) no. 1, pp. 44-59.

Résumé

In this paper, we initiate the study of Paley-type graphs ${\mathrm{\Gamma }}_N$ modulo $N=pq$, where $p$, $q$ are distinct primes of the form $4k+1$. It is shown that ${\mathrm{\Gamma }}_N$ is an edge-regular, symmetric, Eulerian and Hamiltonian graph. Also, the vertex connectivity, edge connectivity, diameter and girth of ${\mathrm{\Gamma }}_N$ are studied and their relationship with the forms of $p$ and $q$ are discussed. Moreover, we specify the forms of primes for which ${\mathrm{\Gamma }}_N$ is triangulated or triangle-free and provide some bounds (exact values in some particular cases) for the order of the automorphism group $\mathrm{Aut}({\mathrm{\Gamma }}_N)$ of the graph ${\mathrm{\Gamma }}_N$, the chromatic number, the independence number, and the domination number of ${\mathrm{\Gamma }}_N$.

Détail

Mots-clés : Cayley graph, quadratic residue, Pythagorean prime.

Bibliographie

[1] W. Ananchuen, “On the adjacency properties of generalized Paley graphs”, Australas. J. Combin., 24 (2001), 129–147 | MR | Zbl

[2] W. Ananchuen and L. Caccetta, “Cubic and quadruple Paley graphs with the $n$-e.c. property”, Discrete Math., 306 (2006), 2954–2961 | DOI | MR | Zbl

[3] R. D. Baker, G. L. Ebert, J. Hemmeter and A. Woldar, “Maximal cliques in the Paley graph of square order”, J. Statist. Plann. Inference, 56:1 (1996), 33–38 | DOI | MR | Zbl

[4] S. D. Cohen, “Clique Numbers of Paley Graphs”, Quaest. Math., 11:2 (1988), 225–231 | DOI | MR | Zbl

[5] A. Das, Quadratic Residue Cayley Graphs on Composite Modulus, Mathematics and Computing, Springer Proceedings in Mathematics and Statistics, 139, 2015 | MR | Zbl

[6] A. N. Elsawy, Paley graphs and their generalizations, M. S. Thesis, Heinrich Heine University, Germany, 2009

[7] R. E. Giudici and A. A. Olivieri, “Quadratic modulo $2^n$ Cayley graphs”, Discrete Math., 215 (2000), 73–79 | DOI | MR | Zbl

[8] C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 2001 | DOI | MR | Zbl

[9] R. Hammack, W. Imrich and S. Klavzar, Handbook of Product Graphs, 2nd ed., CRC Press, 2011 | MR | Zbl

[10] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc., 1998 | MR | Zbl

[11] T. K. Lim and C. E. Praeger, “On generalized Paley graphs and their automorphism groups”, Michigan Math. J., 58 (2009), 293–308 | MR

[12] E. Maistrelli and D. B. Penman, “Some colouring problems for Paley graph”, Discrete Math., 306:1 (2006), 99–106 | DOI | MR | Zbl

[13] T. Moran, I. Orlov and S. Richelson, Topology-Hiding Computation, Cryptology E-print Archive, 2014 Available at http://eprint.iacr.org/2014/1022.pdf

[14] K. H. Rosen, Elementary Number Theory and Its Applications, Addison-Wesley, 1984 | MR | Zbl

[15] D. B. West, Introduction to Graph Theory, Prentice Hall, 2001 | MR

[16] K. Wu, W. Su, H. Luo and X. Xu, “A generalization of generalized Paley graphs and new lower bounds for $R(3,q)$”, The Electronic Journal of Combinatorics, 17 (2010) | MR

[17] H. Zhang, “Independent Sets in Direct Products of Vertex-Transitive Graphs”, J. Combin. Theory Ser. B, 102:3 (2012), 832–838 | DOI | MR | Zbl