Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
eigenvalue; star complement; non-main eigenvalue; Hamiltonian graph
eigenvalue; star complement; non-main eigenvalue; Hamiltonian graph
Summary:
Let $G$ be a finite graph with an eigenvalue $\mu $ of multiplicity $m$. A set $X$ of $m$ vertices in $G$ is called a star set for $\mu $ in $G$ if $\mu $ is not an eigenvalue of the star complement $G\setminus X$ which is the subgraph of $G$ induced by vertices not in $X$. A vertex subset of a graph is $(\kappa ,\tau )$-regular if it induces a $\kappa $-regular subgraph and every vertex not in the subset has $\tau $ neighbors in it. We investigate the graphs having a $(\kappa ,\tau )$-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples.
References:
[1] Bell, F. K.: Characterizing line graphs by star complements. Linear Algebra Appl. 296 (1999), 15-25. MR 1713270 | Zbl 0929.05072
[2] Bell, F. K., Simić, S. K.: On graphs whose star complement for $-2$ is a path or cycle. Linear Algebra Appl. 377 (2004), 249-265. MR 2021615
[3] Cardoso, D. M., Cvetković, D.: Graphs with least eigenvalue $-2$ attaining a convex quadratic upper bound for the stability number. Bull., Cl. Sci. Math. Nat., Sci. Math. 133 (2006), 41-55. DOI 10.2298/BMAT0631041C | MR 2361111
[4] Cardoso, D. M., Rama, P.: Equitable bipartitions of graphs and related results. J. Math. Sci., New York 120 (2004), 869-880. DOI 10.1023/B:JOTH.0000013552.96026.87 | MR 2099043 | Zbl 1079.05072
[5] Cardoso, D. M., Rama, P.: Spectral results on regular graphs with $(k, \tau)$-regular sets. Discrete Math. 307 (2007), 1306-1316. DOI 10.1016/j.disc.2005.11.068 | MR 2311101 | Zbl 1118.05059
[6] Cardoso, D. M., Rama, P.: Spectral results on graphs with regularity constraints. Linear Algebra Appl. 423 (2007), 90-98. MR 2312326 | Zbl 1119.05065
[7] Cardoso, D. M., Sciriha, I., Zerafa, C.: Main eigenvalues and $(k,\tau)$-regular sets. Linear Algebra Appl. 423 (2010), 2399-2408. MR 2599869
[8] Cvetković, D., Doob, M., Sachs, H.: Spectra of Graphs. Theory and Application. Pure and Applied Mathematics 87, Academic Press, New York, and VEB Deutscher Verlag der Wissenschaften, Berlin (1980). MR 0572262 | Zbl 0458.05042
[9] Cvetković, D., Rowlinson, P., Simić, S.: Eigenspaces of Graphs. [Paperback reprint of the hardback edition 1997]. Encyclopedia of Mathematics and Its Applications 66. Cambridge University Press, Cambridge (2008). MR 1440854 | Zbl 1143.05052
[10] Cvetković, D., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75. Cambridge University Press, Cambridge (2010). MR 2571608 | Zbl 1211.05002
[11] Halldórsson, M. M., Kratochvíl, J., Telle, J. A.: Independent sets with domination constraints. Discrete Appl. Math. 99 (2000), 39-54. DOI 10.1016/S0166-218X(99)00124-9 | MR 1743823 | Zbl 0939.05063
[12] Haemers, W. H., Peeters, M. J. P.: The maximum order of adjacency matrices of graphs with a given rank. Des. Codes Cryptogr., to appear, doi: 10.1007/s10623-011-9548-3. DOI 10.1007/s10623-011-9548-3 | MR 2988182 | Zbl 1254.05102
[13] Neumaier, A.: Regular sets and quasi-symmetric 2-designs. Combinatorial theory, Proc. Conf., Schloss Rauischholzhausen 1982, Lect. Notes Math. 969 (1982), 258-275. MR 0692246 | Zbl 0497.05014
[14] Rowlinson, P.: Star complements in finite graphs: A survey. Rend. Semin. Mat. Messina, Ser. II 8 (2002), 145-162. MR 1964838 | Zbl 1042.05061
[15] Rowlinson, P.: Co-cliques and star complements in extremal strongly regular graphs. Linear Algebra Appl. 421 (2007), 157-162. MR 2290694 | Zbl 1116.05052
[16] Rowlinson, P.: On induced matchings as star complements in regular graphs. J. Math. Sci., New York 182 (2012), 159-163. DOI 10.1007/s10958-012-0736-0 | MR 3141336 | Zbl 1254.05160
[17] Rowlinson, P.: The main eigenvalues of a graph: a survey. Appl. Anal. Discrete Math. 1 (2007), 445-471. DOI 10.2298/AADM0702445R | MR 2355287 | Zbl 1199.05241
[18] Rowlinson, P.: Regular star complements in strongly regular graphs. Linear Algebra Appl. 436 (2012), 1482-1488. DOI 10.1016/j.laa.2011.08.020 | MR 2890932 | Zbl 1236.05211
[19] Telle, J. A.: Characterization of domination-type parameters in graphs. Congr. Numerantium 94 (1993), 9-16. MR 1267255 | Zbl 0801.05058
[20] Thompson, D. M.: Eigengraphs: constructing strongly regular graphs with block designs. Util. Math. 20 (1981), 83-115. MR 0639883 | Zbl 0494.05043
[21] Zhang, F.: Matrix Theory. Basic Results and Techniques. Universitext. Springer, New York (1999). MR 1691203 | Zbl 0948.15001
Search
Partner of
