Geodesic
Relations between $(\kappa,\tau)$-regular sets and star complements
Czechoslovak Mathematical Journal, Tome 63 (2013) no. 1, pp. 73-90
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-013-0005-5
Classification : 05C38, 05C50
Keywords: eigenvalue; star complement; non-main eigenvalue; Hamiltonian graph 
@article{10_1007_s10587_013_0005_5,
     author = {An{\dj}eli\'c, Milica and Cardoso, Domingos M. and Simi\'c, Slobodan K.},
     title = {Relations between $(\kappa,\tau)$-regular sets and star complements},
     journal = {Czechoslovak Mathematical Journal},
     pages = {73--90},
     year = {2013},
     volume = {63},
     number = {1},
     doi = {10.1007/s10587-013-0005-5},
     mrnumber = {3035498},
     zbl = {1274.05286},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0005-5/}
}
TY  - JOUR
AU  - Anđelić, Milica
AU  - Cardoso, Domingos M.
AU  - Simić, Slobodan K.
TI  - Relations between $(\kappa,\tau)$-regular sets and star complements
JO  - Czechoslovak Mathematical Journal
PY  - 2013
SP  - 73
EP  - 90
VL  - 63
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0005-5/
DO  - 10.1007/s10587-013-0005-5
LA  - en
ID  - 10_1007_s10587_013_0005_5
ER  - 
%0 Journal Article
%A Anđelić, Milica
%A Cardoso, Domingos M.
%A Simić, Slobodan K.
%T Relations between $(\kappa,\tau)$-regular sets and star complements
%J Czechoslovak Mathematical Journal
%D 2013
%P 73-90
%V 63
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0005-5/
%R 10.1007/s10587-013-0005-5
%G en
%F 10_1007_s10587_013_0005_5
Anđelić, Milica; Cardoso, Domingos M.; Simić, Slobodan K. Relations between $(\kappa,\tau)$-regular sets and star complements. Czechoslovak Mathematical Journal, Tome 63 (2013) no. 1, pp. 73-90. doi: 10.1007/s10587-013-0005-5

[1] Bell, F. K.: Characterizing line graphs by star complements. Linear Algebra Appl. 296 (1999), 15-25. | MR | Zbl

[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

[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 | MR

[4] Cardoso, D. M., Rama, P.: Equitable bipartitions of graphs and related results. J. Math. Sci., New York 120 (2004), 869-880. | DOI | MR | Zbl

[5] Cardoso, D. M., Rama, P.: Spectral results on regular graphs with $(k, \tau)$-regular sets. Discrete Math. 307 (2007), 1306-1316. | DOI | MR | Zbl

[6] Cardoso, D. M., Rama, P.: Spectral results on graphs with regularity constraints. Linear Algebra Appl. 423 (2007), 90-98. | MR | Zbl

[7] Cardoso, D. M., Sciriha, I., Zerafa, C.: Main eigenvalues and $(k,\tau)$-regular sets. Linear Algebra Appl. 423 (2010), 2399-2408. | MR

[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 | Zbl

[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 | Zbl

[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 | Zbl

[11] Halldórsson, M. M., Kratochvíl, J., Telle, J. A.: Independent sets with domination constraints. Discrete Appl. Math. 99 (2000), 39-54. | DOI | MR | Zbl

[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 | MR | Zbl

[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 | Zbl

[14] Rowlinson, P.: Star complements in finite graphs: A survey. Rend. Semin. Mat. Messina, Ser. II 8 (2002), 145-162. | MR | Zbl

[15] Rowlinson, P.: Co-cliques and star complements in extremal strongly regular graphs. Linear Algebra Appl. 421 (2007), 157-162. | MR | Zbl

[16] Rowlinson, P.: On induced matchings as star complements in regular graphs. J. Math. Sci., New York 182 (2012), 159-163. | DOI | MR | Zbl

[17] Rowlinson, P.: The main eigenvalues of a graph: a survey. Appl. Anal. Discrete Math. 1 (2007), 445-471. | DOI | MR | Zbl

[18] Rowlinson, P.: Regular star complements in strongly regular graphs. Linear Algebra Appl. 436 (2012), 1482-1488. | DOI | MR | Zbl

[19] Telle, J. A.: Characterization of domination-type parameters in graphs. Congr. Numerantium 94 (1993), 9-16. | MR | Zbl

[20] Thompson, D. M.: Eigengraphs: constructing strongly regular graphs with block designs. Util. Math. 20 (1981), 83-115. | MR | Zbl

[21] Zhang, F.: Matrix Theory. Basic Results and Techniques. Universitext. Springer, New York (1999). | MR | Zbl

Cité par Sources :