Relations between ( κ , τ ) -regular sets and star complements

Milica Anđelić; Domingos M. Cardoso; Slobodan K. Simić

Czechoslovak Mathematical Journal (2013)

  • Volume: 63, Issue: 1, page 73-90
  • ISSN: 0011-4642

Abstract

top
Let G be a finite graph with an eigenvalue μ of multiplicity m . A set X of m vertices in G is called a star set for μ in G if μ is not an eigenvalue of the star complement G ∖ X which is the subgraph of G induced by vertices not in X . A vertex subset of a graph is ( κ , τ ) -regular if it induces a κ -regular subgraph and every vertex not in the subset has τ neighbors in it. We investigate the graphs having a ( κ , τ ) -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.

How to cite

top

Anđelić, Milica, Cardoso, Domingos M., and Simić, Slobodan K.. "Relations between $(\kappa ,\tau )$-regular sets and star complements." Czechoslovak Mathematical Journal 63.1 (2013): 73-90. <http://eudml.org/doc/252519>.

@article{Anđelić2013,
abstract = {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.},
author = {Anđelić, Milica, Cardoso, Domingos M., Simić, Slobodan K.},
journal = {Czechoslovak Mathematical Journal},
keywords = {eigenvalue; star complement; non-main eigenvalue; Hamiltonian graph; star set; star complement; non-main eigenvalue; Hamiltonian graph},
language = {eng},
number = {1},
pages = {73-90},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Relations between $(\kappa ,\tau )$-regular sets and star complements},
url = {http://eudml.org/doc/252519},
volume = {63},
year = {2013},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 63
IS - 1
SP - 73
EP - 90
AB - 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.
LA - eng
KW - eigenvalue; star complement; non-main eigenvalue; Hamiltonian graph; star set; star complement; non-main eigenvalue; Hamiltonian graph
UR - http://eudml.org/doc/252519
ER -

References

top
  1. Bell, F. K., Characterizing line graphs by star complements, Linear Algebra Appl. 296 (1999), 15-25. (1999) Zbl0929.05072MR1713270
  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. (2004) MR2021615
  3. Cardoso, D. M., Cvetković, D., 10.2298/BMAT0631041C, Bull., Cl. Sci. Math. Nat., Sci. Math. 133 (2006), 41-55. (2006) MR2361111DOI10.2298/BMAT0631041C
  4. Cardoso, D. M., Rama, P., 10.1023/B:JOTH.0000013552.96026.87, J. Math. Sci., New York 120 (2004), 869-880. (2004) Zbl1079.05072MR2099043DOI10.1023/B:JOTH.0000013552.96026.87
  5. Cardoso, D. M., Rama, P., 10.1016/j.disc.2005.11.068, Discrete Math. 307 (2007), 1306-1316. (2007) Zbl1118.05059MR2311101DOI10.1016/j.disc.2005.11.068
  6. Cardoso, D. M., Rama, P., Spectral results on graphs with regularity constraints, Linear Algebra Appl. 423 (2007), 90-98. (2007) Zbl1119.05065MR2312326
  7. Cardoso, D. M., Sciriha, I., Zerafa, C., Main eigenvalues and ( k , τ ) -regular sets, Linear Algebra Appl. 423 (2010), 2399-2408. (2010) MR2599869
  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). (1980) Zbl0458.05042MR0572262
  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). (2008) Zbl1143.05052MR1440854
  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). (2010) Zbl1211.05002MR2571608
  11. Halldórsson, M. M., Kratochvíl, J., Telle, J. A., 10.1016/S0166-218X(99)00124-9, Discrete Appl. Math. 99 (2000), 39-54. (2000) Zbl0939.05063MR1743823DOI10.1016/S0166-218X(99)00124-9
  12. Haemers, W. H., Peeters, M. J. P., 10.1007/s10623-011-9548-3, Des. Codes Cryptogr., to appear, doi: 10.1007/s10623-011-9548-3. Zbl1254.05102MR2988182DOI10.1007/s10623-011-9548-3
  13. Neumaier, A., Regular sets and quasi-symmetric 2-designs, Combinatorial theory, Proc. Conf., Schloss Rauischholzhausen 1982, Lect. Notes Math. 969 (1982), 258-275. (1982) Zbl0497.05014MR0692246
  14. Rowlinson, P., Star complements in finite graphs: A survey, Rend. Semin. Mat. Messina, Ser. II 8 (2002), 145-162. (2002) Zbl1042.05061MR1964838
  15. Rowlinson, P., Co-cliques and star complements in extremal strongly regular graphs, Linear Algebra Appl. 421 (2007), 157-162. (2007) Zbl1116.05052MR2290694
  16. Rowlinson, P., 10.1007/s10958-012-0736-0, J. Math. Sci., New York 182 (2012), 159-163. (2012) Zbl1254.05160MR3141336DOI10.1007/s10958-012-0736-0
  17. Rowlinson, P., 10.2298/AADM0702445R, Appl. Anal. Discrete Math. 1 (2007), 445-471. (2007) Zbl1199.05241MR2355287DOI10.2298/AADM0702445R
  18. Rowlinson, P., 10.1016/j.laa.2011.08.020, Linear Algebra Appl. 436 (2012), 1482-1488. (2012) Zbl1236.05211MR2890932DOI10.1016/j.laa.2011.08.020
  19. Telle, J. A., Characterization of domination-type parameters in graphs, Congr. Numerantium 94 (1993), 9-16. (1993) Zbl0801.05058MR1267255
  20. Thompson, D. M., Eigengraphs: constructing strongly regular graphs with block designs, Util. Math. 20 (1981), 83-115. (1981) Zbl0494.05043MR0639883
  21. Zhang, F., Matrix Theory. Basic Results and Techniques, Universitext. Springer, New York (1999). (1999) Zbl0948.15001MR1691203

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.