The regular spanning Subgraph of a complete graph
DOI:
https://doi.org/10.26713/cma.v17i3.3568Keywords:
Regular Spanning Subgraph, Spectrum, Tree Number, energy of a graph, Vertex coloringAbstract
Let Kn be a complete graph with the vertex set {v1 , v2 , . . . , vn }. We define a Spanning
Subgraph of Kn as a subgraph consisting of all edges of Kn except the edges in the cycle
v1 v2 . . . vn v1 . Here we denote the spanning subgraph of a complete graph Kn by Sn . In this
article, we first show that the spanning subgraph Sn of a complete graph Kn is a (n − 3)
regular graph and discuss different graphical properties such as the spectrum, Laplacian
spectrum of Sn , tree number, energy, and finally the vertex coloring of Sn .
Downloads
References
W.N.Anderson and T. D. Morley, Eigenvalues of the Laplacian of a graphs, Lin. Multilin.
Alg. 18(1985), 141-145, https://doi.org/10.1080/03081088508817681.
R.B. Bapat, Graphs and Matrices, Springer-Verlag, 2nd ed.London(2014),
https://doi.org/10.1007/978-1-4471-6569-9.
M. Behzad, Graphs and their chromatic numbers Doctoral Thesis. Michigan state Univer-
sity(1965), https://doi.org/doi:10.25335/j5he-k143.
N. L. Biggs, Algebraic Graph Theory, Cambridge University Press(1974),
https://doi.org/10.1017/CBO9780511608704.
N. L. Biggs, Colouring square lattice graphs, Bull. London Math. Soc. 9(1977a), 54-56,
https://doi.org/10.1112/blms/9.1.54.
A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Springer, New York(2012), https://doi:
1007/978-1-4614-1939-6
P.J. Cameron, J.M. Geothals, J.J. Seidel, E.E. Shult, Line graphs, root systems, elliptic
geometry, J. Algebra 43(1976), 305-327, https://doi.org/10.1016/0021-8693(76)90162-9.
F. R. K. Chung, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics,
No. 92, AMS, Providence, RI(1997), https://doi.org/10.1090/cbms/092.
D. M. Cvetkovic, Chromatic number and the spectrum of a graph, Publ. Inst. Math.
(Beograd)14(1972), 25-38, http://eudml.org/doc/257394.
D. M. Cvetkovi´c, M. Doob, H. Sachs, Spectra of Graphs: Theory and Application, 3rd ed.,
Johann Ambrosius Barth, Heidelberg(1995), https://lccn.loc.gov/99184564.
B. Elspas, J. Turner, Graphs with circulant adjacency matrices, JCT 9(1970), 297-307,
https://doi.org/10.1016/S0021-9800(70)80068-0.
M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 23,
–305(1973), https://doi:10.21136/CMJ.1973.101168.
R.Grone and R. Merris, The Laplacian spectrum of a graph II, SIAM J. Disc. Math. 7(1994),
-229, https://doi.org/10.1137/S0895480191222653.
F. Harary, The determinant of the adjancency matrix of a graph, SIAM Review 4(1962),
-210, https://doi.org/10.1137/1004057.
F. Harary, Graph Theory, Narosa Publishing House, New Delhi(1998),
https://users.metu.edu.tr/aldoks/341/Book%201%20(Harary).pdf.
A. J. Hoffman, On eigenvalues and colourings of graphs, Graph Theory and its Applications
(Academic Press, New York), 79-92(1970), https://doi:10.1111/j.1749-6632.1970.tb56474.x.
G.Ivan, The energy of a graph: Old and new results, Algebraic Combinatories
and its Applications. A. Betten et.al., eds. (Springer-verlag, Berlin)(2001), 196-211,
http://dx.doi.org/10.1007/978-3-642-59448-913.
X. Li, Y. Shi and I. Gutman, Graph Energy, Springer, New York (2012),
https://doi:10.1007/978-1-4614-4220-2.
B.Mohar, Eigenvalues, diameter, and mean distance in graphs, Graphs Comb. 7(1991),
-64, https://doi.org/10.1007/BF01789463.
T. D. Parsons, Circulant graph imbeddings, JCT(B) 29(1980), 310-320,
https://doi.org/10.1016/0095-8956(80)90088-X.
J. J.Seidel, Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3,
Lin. Alg. Appl. 1 (1968), 281-298, https://doi.org/10.1016/0024-3795(68)90008-6.
H.Whitney, The colouring of graphs, Ann. Math. 33(1932b), 688-718,
https://doi.org/10.2307/1968214.
H.S.Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc.
(1967), 330-332, https://doi.org/10.1112/jlms/s1-42.1.330.
Published
Issue
Section
License
How to Cite
