ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


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


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

Jose Maria Sigarreta Almira

Departamento de Matemáticas
Universidad Carlos III de Madrid
Avda. de la Universidad 30, 28911 Leganés (Madrid), Spain


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