The Square Graph of a Cycle Graph
DOI:
https://doi.org/10.26713/cma.v16i4.3246Keywords:
Square graph, Spectrum, Tree number, Energy of a graph, Vertex coloringAbstract
The square graph of a cycle graph \(C_{n}\) is a graph consisting of the same set of vertex as in \(C_{n}\) and two different vertices are considered adjacent if their distance in \(C_{n}\) is at most two. We denote the square graph of a cycle graph \(C_{n}\) by \(C^2_{n}\). In this article, we first show that the square graph \(C^2_{n}\) is a 4-regular graph for \(n\geq5\) and then discuss various graphical properties such as the spectrum, Laplacian spectrum of \(C^2_{n}\), tree number, energy and, finally, the vertex coloring of \(C^2_{n}\).
Downloads
References
W. N. Anderson and T. D. Morley, Eigenvalues of the Laplacian of a graphs, Linear and Multilinear Algebra 18(2) (1985), 141 – 145, DOI: 10.1080/03081088508817681.
R. B. Bapat, Graphs and Matrices, Springer-Verlag, 2nd edition, London, xi + 193 pages (2014), DOI: 10.1007/978-1-4471-6569-9.
M. Behzad, Graphs and Their Chromatic Numbers, Doctoral Thesis, Michigan State University, Michigan (1965), DOI: 10.25335/j5he-k143.
N. Biggs, Algebraic Graph Theory, 2nd edition, Cambridge University Press, viii + 205 pages (1974).
N. Biggs, Colouring square lattice graphs, Bulletin of the London Mathematical Society 9(1) (1977), 54 – 56, DOI: 10.1112/blms/9.1.54.
P. J. Cameron, J. M. Geothals, J. J. Seidel and E. E. Shult, Line graphs, root systems, elliptic geometry, Journal of Algebra 43(1) (1976), 305 – 327, DOI: 10.1016/0021-8693(76)90162-9.
D. M. Cvetkovic, Chromatic number and the spectrum of a graph, Publications de l’Institut Mathématique 14(28) (1972), 25 – 38, URL: http://eudml.org/doc/257394.
B. Elspas and J. Turner, Graphs with circulant adjacency matrices, Journal of Combinatorial Theory 9(3) (1970), 297 – 307, DOI: 10.1016/S0021-9800(70)80068-0.
R. Grone and R. Merris, The Laplacian spectrum of a graph II, SIAM Journal on Discrete Mathematics 7(2) (1994), 221 – 229, DOI: 10.1137/S0895480191222653.
F. Harary, Graph Theory, Addison-Wesley Publishing Company, Reading, Massachusetts, ix + 274 pages (1969).
F. Harary, The determinant of the adjancency matrix of a graph, SIAM Review 4(3) (1962), 202 – 210, DOI: 10.1137/1004057.
G. Ivan, The energy of a graph: Old and new results, in: Algebraic Combinatorics and Applications, A. Betten, A. Kohnert, R. Laue and A. Wassermann (editors), Springer, Berlin — Heidelberg, (2001), DOI: 10.1007/978-3-642-59448-9_13.
B. Mohar, Eigenvalues, diameter, and mean distance in graphs, Graphs and Combinatorics 7 (1991), 53 – 64, DOI: 10.1007/BF01789463.
A. Mukhopadhyay, The square root of a graph, Journal of Combinatorial Theory 2(3) (1967), 290 – 295, DOI: 10.1016/S0021-9800(67)80030-9.
T. D. Parsons, Circulant graph imbeddings, Journal of Combinatorial Theory, Series B 29(3) (1980), 310 – 320, DOI: 10.1016/0095-8956(80)90088-X.
A. Raychaudhuri, On power of strongly chordal and circular arc graphs, Ars Combinatoria 34 (1992), 147 – 160, URL: https://combinatorialpress.com/article/ars/Volume%20034/volume-34-paper-16.pdf.
I. C. Ross and F. Harary, The square of a tree, The Bell System Technical Journal 39(3) (1960), 641 – 647, DOI: 10.1002/j.1538-7305.1960.tb03936.x.
J. J. Seidel, Strongly regular graphs with (−1,1,0) adjacency matrix having eigenvalue 3, Linear Algebra and its Applications 1(2) (1968), 281 – 298, DOI: 10.1016/0024-3795(68)90008-6.
H. Whitney, The colouring of graphs, Annals of Mathematics 33(4) (1932), 688 – 718, DOI: 10.2307/1968214.
H. S. Wilf, The eigenvalues of a graph and its chromatic number, Journal of the London Mathematical Society s1-42(1) (1967), 330 – 332, DOI: 10.1112/jlms/s1-42.1.330.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
