Download PDF - Spectral study of alliances in graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Spectral study of alliances in graphs

Authors 1, 2

Affiliations

  1. Department of Computer Engineering and Mathematics, Rovira i Virgili University of Tarragona, Av. Països Catalans 26, 43007 Tarragona, Spain
  2. Departamento de Matemáticas, Universidad Carlos III de Madrid, Avda. de la Universidad 30, 28911 Leganés (Madrid), Spain

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

ENG
defensive alliance, offensive alliance, dual alliance, domination, spectral radius, graph eigenvalues.

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2007/27/1
Export to PBN, Opens in new tab
Pages:
143-157
Main language of publication
English
Received
2006-02-20
Accepted
2006-07-10
Published
2007

DOI: 10.7151/dmgt.1351

Exact and natural sciences