Back to Search
Start Over
Alliance polynomial of regular graphs.
- Source :
-
Discrete Applied Mathematics . Jul2017, Vol. 225, p22-32. 11p. - Publication Year :
- 2017
-
Abstract
- The alliance polynomial of a graph G with order n and maximum degree Δ is the polynomial A ( G ; x ) = ∑ k = − Δ Δ A k ( G ) x n + k , where A k ( G ) is the number of exact defensive k -alliances in G . We obtain some properties of A ( G ; x ) and its coefficients for regular graphs. In particular, we characterize the degree of regular graphs by the number of non-zero coefficients of their alliance polynomial. Besides, we prove that the family of alliance polynomials of Δ -regular graphs with small degree is a very special one, since it does not contain alliance polynomials of graphs which are not Δ -regular. By using this last result and direct computation we find that the alliance polynomial determines uniquely each cubic graph of order less than or equal to 10 . [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 225
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 122947211
- Full Text :
- https://doi.org/10.1016/j.dam.2017.03.016