Alliance polynomial and hyperbolicity in regular graphs

Resumen

One of the open problems in graph theory is the characterization of any graph by a polynomial. Research in this area has been largely driven by the advantages offered by the use of computers which make working with graphs: it is simpler to represent a graph by a polynomial (a vector) that by the adjacency matrix (a matrix). We introduce the alliance polynomial of a graph. The alliance polynomial of a graph G with order n and maximum degree ?_1 is the polynomial A(G; x) = ?_(k=?-??_1)^(?_1)??Ak(G) x^(n+k) ?, where A{_k}(G) is the number of exact defensive k-alliances in G. Also, we develop and implement an algorithm that computes in an efficient way the alliance polynomial. We obtain some properties of A(G; x) and its coefficients for: • Path, cycle, complete and star graphs. In particular, we prove that they are characterized by their alliance polynomials. • Cubic graphs (graphs with all of their vertices of degree 3), since they are a very interesting class of graphs with many applications. We prove that they verify unimodality. Also, we compute the alliance polynomial for cubic graphs of small order, which satisfy uniqueness. • Regular graphs (graphs with the same degree for all vertices). 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 connected ?-regular graphs with small degree is a very special one, since it does not contain alliance polynomials of graphs which are not connected ?-regular. If X is a geodesic metric space and x1, x2, x3 ? X, a geodesic triangle T = {x1, x2, x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is ?-hyperbolic (in the Gromov sense) if any side of T is contained in the ?-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by ?(X) the sharp hyperbolicity constant of X, i.e., ?(X) := inf{? >= 0 : X is ?-hyperbolic }. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. We obtain information about the hyperbolicity constant of cubic graphs. These graphs are also very important in the study of Gromov hyperbolicity, since for any graph G with bounded maximum degree there exists a cubic graph G* such that G is the hyperbolic if and only if G* is hyperbolic. We find some characterizations for the cubic graphs which have small hyperbolicity constants. Besides, we obtain bounds for the hyperbolicity constant of the complement graph of a cubic graph; our main result of this kind says that for any finite cubic graph G which is not isomorphic either to K_4 or to K_3,3, the inequalities 5k/4 <= ? (G ?) <=3k/2 hold, if k is the length of every edge in G. --------------------