Regular and Maximal Graphs with Prescribed Tripartite Graph as a Star Complement

Abstract

Let G be a graph of order n and μ be an adjacency eigenvalue of G with multiplicity k ≥ 1. A star complement H for μ in G is an induced subgraph of G of order n − k with no eigenvalue μ, and the subset X = V(G − H) is called a star set for μ in G. The star complement provides a strong link between graph structure and linear algebra. In this paper, the authors characterize the regular graphs with K _2,2,s (s ≥ 2) as a star complement for all possible eigenvalues, the maximal graphs with K _2,2,s as a star complement for the eigenvalue μ = 1, and propose some questions for further research.

Keywords

Adjacency eigenvalue / Star set / Star complement / Regular graph / Maximal graph

References

[1] Asgharsharghi L, Kiani D. On regular graphs with complete tripartite star complements. Ars Combin., 2015, 122: 431-437

[2] Bell F K. Characterizing line graphs by star complements. Linear Algebra Appl., 1999, 296: 15-25

[3] Bell F K. Line graphs of bipartite graphs with hamiltonian paths. J. Graph Theory, 2003, 43: 137-149

[4] Bondy J A, Murty U S R. Graph Theory, 2008, New York: Springer-Verlag

[5] Cvetković D, Doob M, Sachs H. Spectra of Graphs: Theory and Application, 1995 3rd ed. Heidelberg-Leipzig: Jonah Ambrosius Barth Verlag

[6] Cvetković D, Rowlinson P, Simić S. Eigenspaces of Graphs, 1997, Cambridge: Cambridge University Press

[7] Cvetković D, Rowlinson P, Simić S. Some characterizations of graphs by star complements. Linear Algebra Appl., 1999, 301: 81-97

[8] Cvetković D, Rowlinson P, Simić S. An Introduction to the Theory of Graph Spectra, 2010, Cambridge: Cambridge University Press

[9] Ellingham M. Basic subgraphs and graph spectra. Australas. J. Combin., 1993, 8: 247-265

[10] Fang X, You L, Huang Y. Maximal graphs with a prescribed complete bipartite graph as a star complement. AIMS Math., 2021, 6: 7153-7169

[11] Fang, X., You, L., Wu, R. and Huang, Y., Regular graphs with a complete bipartite graph as a star complement, 2022, arXiv: 2210.04160.

[12] Frankl P, Tokushige N. Extremal Problems for Finite Sets, Student Mathematical Library, 2018, Providence, RI: American Mathematical Soc. 86

[13] Ramezani F, Tayfeh-Rezaie B. Graphs with prescribed star complement for the eigenvalue 1. Ars Combin., 2014, 116: 129-145

[14] Rowlinson P. An extension of the star complement technique for regular graphs. Linear Algebra Appl., 2018, 557: 496-507

[15] Rowlinson P, Jackson P S. On graphs with complete bipartite star complements. Linear Algebra Appl., 1999, 298: 9-20

[16] Rowlinson P, Tayfeh-Rezaie B. Star complements in regular graphs: Old and new results. Linear Algebra Appl., 2010, 432: 2230-2242

[17] Stanić Z. On graphs whose second largest eigenvalue equals 1–the star complement technique. Linear Algebra Appl., 2007, 420(2): 700-710

[18] Stanić, Z. and Simić, S. K., On graphs with unicyclic star complement for 1 as the second largest eigenvalue, Contemporary Geometry and Related Topics, Univ. Belgrade Fac. Math., Belgrade, 2006, 475–484.

[19] Wang J, Yuan X, Liu L. Regular graphs with a prescribed complete multipartite graph as a star complement. Linear Algebra Appl., 2019, 579: 302-319

[20] Wu, R., You, L., Huang, Y. and Fang, X., Maximal graphs with $\overline {{K_{1,s}}} $ as a star complement, submitted, 2021.

[21] Wu, R., You, L., Huang, Y. and Fang, X., Maximal graphs with $\overline {{K_{1,1,s}}} $ as a star complement, submitted, 2021.

[22] Yang, Y., Huang, Q. and Wang, J., On a conjecture for regular graphs with complete multipartite star complement, 2021, arXiv: 1912.07594v2.

[23] Yuan X, Chen H, Liu L. On the characterization of graphs by star complements. Linear Algebra Appl., 2017, 533: 491-506

[24] Yuan X, Zhao Q, Liu L, Chen H. On graphs with prescribed star complements. Linear Algebra Appl., 2018, 559: 80-94