Further studies on circulant completion of graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-6034Keywords:
circulant completion, circulant completion graph, circulant span, circulant labelling, Φ-completion, ?-diagobal modulo n, ?-traceAbstract
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.
References
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.
Published
How to Cite
Issue
Section
Copyright (c) 2024 Sudev Naduvath, Toby
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
