Further studies on circulant completion of graphs





circulant completion, circulant completion graph, circulant span, circulant labelling, Φ-completion, ?-diagobal modulo n, ?-trace


A circulant graph C(n,S) is a graph having its adjacency matrix as a circulant matrix. It can also be intrepreted as a graph with vertices v0,v1,...,vn-1 that are in one to one correspondence with the members of Zn and with edge set {vivj:i-j ∈ S}, where S known as the connection set or symbol, is a subset of non-identity members of Zn that is closed under inverses. This work extends the study of circulant completion and general formulae for calculating circulant completion number in two different perspectives, one in terms of circulant span and the other in terms of adjacency matrix.

Author Biography

Tony Antony, CHRIST (Deemed to be University).

Department of Mathematics.


B. Alspach, J. Morris, and V. Vilfred. Self-complementary circulant graphs. Ars Combin., 53:187{192, 1999.

B. Alspach and T. Parsons. Isomorphism of circulant graphs and digraphs. Discrete Math., 25(2):97-108, 1979.

T. B. Antony and S. Naduvath. On circulant completion of graphs. In Data Science and Security, pages 181-188. Springer, 2022.

T. B. Antony and S. Naduvath. On equitable chromatic completion of some graph classes. In AIP Conference Proceedings, volume 2516, page 210037. AIP Publishing LLC, 2022.

B. Elspas and J. Turner. Graphs with circulant adjacency matrices. J. Combin.Theory, 9(3):297-307, 1970.

F. Harary. Graph theory. Narosa Publishing House, New Delhi, 2001.

J. Kok. Chromatic completion number of corona of path and cycle graphs. Malaya J. Mat., 8(1, 2020):1-6, 2020.

E. A. Monakhova. A survey on undirected circulant graphs. Discrete Math. Algorithms Appl., 4(01):1250002, 2012.

E. A. Monakhova, A. Y. Romanov, and E. V. Lezhnev. Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for networks-on-chip. IEEE Access, 8:215010{215019, 2020.

E. Mphako-Banda and J. Kok. Stability in respect of chromatic completion of graphs. arXiv preprint arXiv:1810.13328, 2018.

E. Mphako-Banda and J. Kok. Chromatic completion number. J. Math. Comput. Sci., 10(2):2971-2983, 2020.

S. Naduvath and G. Augustine. A note on the sparing number of the sieve graphs of certain graphs. Appl. Math. E-Notes, 15:29-37, 2015.

V. K. Nguyen. Family of circulant graphs and its expander properties. San Jose State University, 2010.

V. Vilfred. -labelled graph and circulant graphs. Ph.D. Thesis, University of Kerala, Trivandrum, India, 1994.

V. Vilfred and P. Wilson. New family of circulant graphs without cayley isomorphism property with mi= 7. IOSR J. Math., 12:32{37, 2016.

D. West. Introduction to graph theory. Prentice Hall of India, New Delhi, 2001.



How to Cite

T. Antony and S. Naduvath, “Further studies on circulant completion of graphs”, Proyecciones (Antofagasta, On line), vol. 43, no. 3, pp. 761-773, May 2024.