PDF

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

SPECTRAL STUDY OF ALLIANCES IN GRAPHS

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

Abstract

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.

References

[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