| Title:
|
Relations between $(\kappa,\tau)$-regular sets and star complements (English) |
| Author:
|
Anđelić, Milica |
| Author:
|
Cardoso, Domingos M. |
| Author:
|
Simić, Slobodan K. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
63 |
| Issue:
|
1 |
| Year:
|
2013 |
| Pages:
|
73-90 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
eigenvalue |
| Keyword:
|
star complement |
| Keyword:
|
non-main eigenvalue |
| Keyword:
|
Hamiltonian graph |
| MSC:
|
05C38 |
| MSC:
|
05C50 |
| idZBL:
|
Zbl 1274.05286 |
| idMR:
|
MR3035498 |
| DOI:
|
10.1007/s10587-013-0005-5 |
| . |
| Date available:
|
2013-03-01T16:03:57Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143171 |
| . |
| Reference:
|
[1] Bell, F. K.: Characterizing line graphs by star complements.Linear Algebra Appl. 296 (1999), 15-25. Zbl 0929.05072, MR 1713270 |
| Reference:
|
[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 |
| Reference:
|
[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. MR 2361111, 10.2298/BMAT0631041C |
| Reference:
|
[4] Cardoso, D. M., Rama, P.: Equitable bipartitions of graphs and related results.J. Math. Sci., New York 120 (2004), 869-880. Zbl 1079.05072, MR 2099043, 10.1023/B:JOTH.0000013552.96026.87 |
| Reference:
|
[5] Cardoso, D. M., Rama, P.: Spectral results on regular graphs with $(k, \tau)$-regular sets.Discrete Math. 307 (2007), 1306-1316. Zbl 1118.05059, MR 2311101, 10.1016/j.disc.2005.11.068 |
| Reference:
|
[6] Cardoso, D. M., Rama, P.: Spectral results on graphs with regularity constraints.Linear Algebra Appl. 423 (2007), 90-98. Zbl 1119.05065, MR 2312326 |
| Reference:
|
[7] Cardoso, D. M., Sciriha, I., Zerafa, C.: Main eigenvalues and $(k,\tau)$-regular sets.Linear Algebra Appl. 423 (2010), 2399-2408. MR 2599869 |
| Reference:
|
[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). Zbl 0458.05042, MR 0572262 |
| Reference:
|
[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). Zbl 1143.05052, MR 1440854 |
| Reference:
|
[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). Zbl 1211.05002, MR 2571608 |
| Reference:
|
[11] Halldórsson, M. M., Kratochvíl, J., Telle, J. A.: Independent sets with domination constraints.Discrete Appl. Math. 99 (2000), 39-54. Zbl 0939.05063, MR 1743823, 10.1016/S0166-218X(99)00124-9 |
| Reference:
|
[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. Zbl 1254.05102, MR 2988182, 10.1007/s10623-011-9548-3 |
| Reference:
|
[13] Neumaier, A.: Regular sets and quasi-symmetric 2-designs.Combinatorial theory, Proc. Conf., Schloss Rauischholzhausen 1982, Lect. Notes Math. 969 (1982), 258-275. Zbl 0497.05014, MR 0692246 |
| Reference:
|
[14] Rowlinson, P.: Star complements in finite graphs: A survey.Rend. Semin. Mat. Messina, Ser. II 8 (2002), 145-162. Zbl 1042.05061, MR 1964838 |
| Reference:
|
[15] Rowlinson, P.: Co-cliques and star complements in extremal strongly regular graphs.Linear Algebra Appl. 421 (2007), 157-162. Zbl 1116.05052, MR 2290694 |
| Reference:
|
[16] Rowlinson, P.: On induced matchings as star complements in regular graphs.J. Math. Sci., New York 182 (2012), 159-163. Zbl 1254.05160, MR 3141336, 10.1007/s10958-012-0736-0 |
| Reference:
|
[17] Rowlinson, P.: The main eigenvalues of a graph: a survey.Appl. Anal. Discrete Math. 1 (2007), 445-471. Zbl 1199.05241, MR 2355287, 10.2298/AADM0702445R |
| Reference:
|
[18] Rowlinson, P.: Regular star complements in strongly regular graphs.Linear Algebra Appl. 436 (2012), 1482-1488. Zbl 1236.05211, MR 2890932, 10.1016/j.laa.2011.08.020 |
| Reference:
|
[19] Telle, J. A.: Characterization of domination-type parameters in graphs.Congr. Numerantium 94 (1993), 9-16. Zbl 0801.05058, MR 1267255 |
| Reference:
|
[20] Thompson, D. M.: Eigengraphs: constructing strongly regular graphs with block designs.Util. Math. 20 (1981), 83-115. Zbl 0494.05043, MR 0639883 |
| Reference:
|
[21] Zhang, F.: Matrix Theory. Basic Results and Techniques.Universitext. Springer, New York (1999). Zbl 0948.15001, MR 1691203 |
| . |
