Discussiones Mathematicae Graph Theory 27(1) (2007) 143-157
doi: 10.7151/dmgt.1351

[BIBTex] [PDF] [PS]


Juan Alberto Rodríguez-Velazquez

Department of Computer Engineering and Mathematics
Rovira i Virgili University of Tarragona
Av. Països Catalans 26, 43007 Tarragona, Spain
e-mail: juanalberto.rodriguez@urv.cat

Jose Maria Sigarreta Almira

Departamento de Matemáticas
Universidad Carlos III de Madrid
Avda. de la Universidad 30, 28911 Leganés (Madrid), Spain
e-mail: josemaria.sigarreta@uc3m.es


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.

Keywords: defensive alliance, offensive alliance, dual alliance, domination, spectral radius, graph eigenvalues.

2000 Mathematics Subject Classification: 05C69, 15A42, 05C50.


[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.
[2] S.M. Hedetniemi, S.T. Hedetniemi and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157-177.
[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.
[4] J.A. Rodríguez, Laplacian eigenvalues and partition problems in hypergraphs, submitted.
[5] J.A. Rodríguez and J.M. Sigarreta, Global alliances in planar graphs, submitted.

Received 20 February 2006
Revised 10 July 2006