Search

The harmonic polynomial was defined in order to understand better the harmonic topological index. Here, we obtain several properties of this polynomial, and we prove that several properties of a graph can be deduced from its harmonic polynomial. Also, we prove that graphs with the same harmonic polynomial share many properties although they are not necessarily isomorphic. [ABSTRACT FROM AUTHOR]

The concept of arithmetic–geometric index was introduced in the chemical graph theory recently, but it has shown to be useful. We obtain in this paper new lower bounds of the arithmetic–geometric index and we characterize graphs extremal with respect to them. [ABSTRACT FROM AUTHOR]

The concept of geometric-arithmetic index GA1 was introduced in the chemical graph theory recently, but it has shown to be useful. The aim of this paper is to give new inequalities involving the geometric-arithmetic index and characterize extremal graphs with respect to them. [ABSTRACT FROM AUTHOR]

The concepts of geometric–arithmetic and harmonic indices were introduced in the area of chemical graph theory recently. They have proven to correlate well with physical and chemical properties of some molecules. The aim of this paper is to obtain new inequalities involving the first Zagreb, the harmonic, and the geometric–arithmetic G A 1 indices. Furthermore, inequalities relating these indices and line graphs are proven. [ABSTRACT FROM AUTHOR]

We introduce the differential polynomial of a graph. The differential polynomial of a graph G of order n is the polynomial B(G;x):=∑k=−n∂(G)Bk(G)xn+k, where Bk(G) denotes the number of vertex subsets of G with differential equal to k. We state some properties of B(G; x) and its coefficients. In particular, we compute the differential polynomial for complete, empty, path, cycle, wheel and double star graphs. We also establish some relationships between B(G; x) and the differential polynomials of graphs which result by removing, adding, and subdividing an edge from G. [ABSTRACT FROM AUTHOR]

A graph H is a minor of a graph G if a graph isomorphic to H can be obtained from G by contracting some edges, deleting some edges, and deleting some isolated vertices. 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. One of the main aims in this work is to obtain quantitative information about the distortion of the hyperbolicity constant of the graph G/e obtained from the (simple or non-simple) graph G by contracting an arbitrary edge e from it. We prove that H is hyperbolic if and only if G is hyperbolic, for many minors H of G, even if H is obtained from G by contracting and/or deleting infinitely many edges. [ABSTRACT FROM AUTHOR]

If X is a geodesic metric space and $$x_1,x_2,x_3$$ are three points in $$X$$ , a geodesic triangle $$T=\{x_1,x_2,x_3\}$$ is the union of three geodesics $$[x_1x_2]$$ , $$[x_2x_3]$$ and $$[x_3x_1]$$ in $$X$$ . The space $$X$$ is $$\delta $$ - hyperbolic $$($$ in the Gromov sense $$)$$ if any side of $$T$$ is contained in a $$\delta $$ -neighborhood of the union of the two other sides, for every geodesic triangle $$T$$ in $$X$$ . 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. In this paper we obtain criteria which allow us to decide, for a large class of graphs, whether they are hyperbolic or not. We are especially interested in the planar graphs which are the 'boundary' (the $$1$$ -skeleton) of a tessellation of the Euclidean plane. Furthermore, we prove that a graph obtained as the $$1$$ -skeleton of a general CW $$2$$ -complex is hyperbolic if and only if its dual graph is hyperbolic. [ABSTRACT FROM AUTHOR]

If X is a geodesic metric space and x1,x2,x3∈X, a geodesic triangleT={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 a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by δ(X) the sharp hyperbolicity constant of X, i.e. δ(X)=inf{δ≥0:Xisδ-hyperbolic}. In this paper, we characterize the lexicographic product of two graphs G1∘G2 which are hyperbolic, in terms of G1 and G2: the lexicographic product graph G1∘G2 is hyperbolic if and only if G1 is hyperbolic, unless if G1 is a trivial graph (the graph with a single vertex); if G1 is trivial, then G1∘G2 is hyperbolic if and only if G2 is hyperbolic. In particular, we obtain the sharp inequalities δ(G1)≤δ(G1∘G2)≤δ(G1)+3/2 if G1 is not a trivial graph, and we characterize the graphs for which the second inequality is attained. [ABSTRACT FROM AUTHOR]

It is well-known that the different products of graphs are some of the more symmetric classes of graphs. Since we are interested in hyperbolicity, it is interesting to study this property in products of graphs. Some previous works characterize the hyperbolicity of several types of product graphs (Cartesian, strong, join, corona and lexicographic products). However, the problem with the direct product is more complicated. The symmetry of this product allows us to prove that, if the direct product G 1 × G 2 is hyperbolic, then one factor is bounded and the other one is hyperbolic. Besides, we prove that this necessary condition is also sufficient in many cases. In other cases, we find (not so simple) characterizations of hyperbolic direct products. Furthermore, we obtain good bounds, and even formulas in many cases, for the hyperbolicity constant of the direct product of some important graphs (as products of path, cycle and even general bipartite graphs). [ABSTRACT FROM AUTHOR]