In this paper we obtain several tight bounds on different types of alliance numbers of a graph, namely (global) defensive alliance number, global offensive alliance number and global dual alliance number. In particular, we investigate the relationship between the alliance numbers of a graph and its algebraic connectivity, its spectral radius, and its Laplacian spectral radius.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1351,
author = {Juan Alberto Rodr\'\i guez-Velazquez and Jose Maria Sigarreta Almira},
title = {Spectral study of alliances in graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {27},
year = {2007},
pages = {143-157},
zbl = {1133.05072},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1351}
}
Juan Alberto Rodríguez-Velazquez; Jose Maria Sigarreta Almira. Spectral study of alliances in graphs. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 143-157. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1351/
[000] [1] M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J.25 (100) (1975) 619-633. | Zbl 0437.15004
[001] [2] S.M. Hedetniemi, S.T. Hedetniemi and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157-177. | Zbl 1051.05068
[002] [3] T.W. Haynes, S.T Hedetniemi and M.A. Henning, Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), Research Paper 47, 13 pp. | Zbl 1031.05096
[003] [4] J.A. Rodríguez, Laplacian eigenvalues and partition problems in hypergraphs, submitted.
[004] [5] J.A. Rodríguez and J.M. Sigarreta, Global alliances in planar graphs, submitted. | Zbl 1135.05052