Maximal graphs with a prescribed complete bipartite graph as a star complement

Xiaona Fang; Lihua You; Yufei Huang; Xiaona Fang; Lihua You; Yufei Huang

doi:10.3934/math.2021419

AIMS Mathematics

2021, Volume 6, Issue 7: 7153-7169. doi: 10.3934/math.2021419

Previous Article Next Article

Research article

Maximal graphs with a prescribed complete bipartite graph as a star complement

1.
School of Mathematical Sciences, South China Normal University, Guangzhou, 510631, China
2.
Department of Mathematics Teaching, Guangzhou Civil Aviation College, Guangzhou, 510403, China

Received: 09 March 2021 Accepted: 20 April 2021 Published: 28 April 2021
MSC : 05C50

Let $ G $ be a graph of order $ n $ and $ \mu $ be an adjacency eigenvalue of $ G $ with multiplicity $ k\geq 1 $. A star complement for $ \mu $ in $ G $ is an induced subgraph of $ G $ of order $ n-k $ with no eigenvalue $ \mu $. In this paper, we characterize the maximal graphs with the bipartite graph $ K_{2, s} $ as a star complement for eigenvalues $ \mu = -2, 1 $ and study the cases of other eigenvalues for further research.
- adjacency eigenvalue,
- star set,
- star complement,
- maximal graph
Citation: Xiaona Fang, Lihua You, Yufei Huang. Maximal graphs with a prescribed complete bipartite graph as a star complement[J]. AIMS Mathematics, 2021, 6(7): 7153-7169. doi: 10.3934/math.2021419

Related Papers:

Abstract

Let $ G $ be a graph of order $ n $ and $ \mu $ be an adjacency eigenvalue of $ G $ with multiplicity $ k\geq 1 $. A star complement for $ \mu $ in $ G $ is an induced subgraph of $ G $ of order $ n-k $ with no eigenvalue $ \mu $. In this paper, we characterize the maximal graphs with the bipartite graph $ K_{2, s} $ as a star complement for eigenvalues $ \mu = -2, 1 $ and study the cases of other eigenvalues for further research.

References

[1]	L. Asgharsharghi, D. Kiani, On regular graphs with complete tripartite star complements, Ars Combin., 122 (2015), 431–437.
[2]	F. K. Bell, Characterizing line graphs by star complements, Linear Algebra Appl., 296 (1999), 15–25. doi: 10.1016/S0024-3795(99)00088-9
[3]	F. K. Bell, Line graphs of bipartite graphs with hamiltonian paths, J. Graph Theory, 43 (2003), 137–149. doi: 10.1002/jgt.10107
[4]	D. Cvetković, M. Doob, H. Sachs, Spectra of graphs: theory and application, New York: Academic Press, 1980.
[5]	D. Cvetković, P. Rowlinson, S. Simić, Eigenspaces of Graphs, Cambridge: Cambridge University Press, 1997.
[6]	D. Cvetković, P. Rowlinson, S. Simić, Some characterization of graphs by star complements, Linear Algebra Appl., 301 (1999), 81–97. doi: 10.1016/S0024-3795(99)00179-2
[7]	D. Cvetković, P. Rowlinson, S. Simić, An introduction to the theory of graph spectra, Cambridge: Cambridge University Press, 2010.
[8]	F. Ramezani, B. Tayfeh-Rezaie, Graphs with prescribed star complement for the eigenvalue 1, Ars Combin., 116 (2014), 129–145.
[9]	P. Rowlinson, On bipartite graphs with complete bipartite star complements, Linear Algebra Appl., 458 (2014), 149–160. doi: 10.1016/j.laa.2014.06.011
[10]	P. Rowlinson, An extension of the star complement technique for regular graphs, Linear Algebra Appl., 557 (2018), 496–507. doi: 10.1016/j.laa.2018.08.018
[11]	P. Rowlinson, P. S. Jackson, On graphs with complete bipartite star complements, Linear Algebra Appl., 298 (1999), 9–20. doi: 10.1016/S0024-3795(99)00135-4
[12]	P. Rowlinson, B. Tayfeh-Rezaie, Star complements in regular graphs: old and new results, Linear Algebra Appl., 432 (2010), 2230–2242. doi: 10.1016/j.laa.2009.04.022
[13]	Z. Stani$\acute{c}$, On graphs whose second largest eigenvalue equals 1 – the star complement technique, Linear Algebra Appl., 420 (2007), 700–710. doi: 10.1016/j.laa.2006.08.025
[14]	Z. Stani$\acute{c}$, S. K. Simi$\acute{c}$, On graphs with unicyclic star complement for 1 as the second largest eigenvalue, In: Proceedings of the Conference Contemporary Geometry and Related Topics, Belgrade, June 26–July 2, 2005, Faculty of Mathematics, Belgrade, 2006,475–484.
[15]	J. Wang, X. Yuan, L. Liu, Regular graphs with a prescribed complete multipartite graph as a star complement, Linear Algebra Appl., 579 (2019), 302–319. doi: 10.1016/j.laa.2019.06.004
[16]	Y. Yang, Q. Huang, J. Wang, Regular graphs with $\overline {sK_1\cup K_t} $ as a star complement, arXiv: 1912. 07594, 2019.
[17]	X. Yuan, H. Chen, L. Liu, On the characterization of graphs by star complements, Linear Algebra Appl., 533 (2017), 491–506. doi: 10.1016/j.laa.2017.08.001
[18]	X. Yuan, Q. Zhao, L. Liu, H. Chen, On graphs with prescribed star complements, Linear Algebra Appl., 559 (2018), 80–94. doi: 10.1016/j.laa.2018.09.001

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)