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]

Let G = (V , E) be a finite undirected graph. A set S of vertices in V is said to be total k -dominating if every vertex in V is adjacent to at least k vertices in S. The total k -domination number, γ k t (G) , is the minimum cardinality of a total k -dominating set in G. In this work we study the total k -domination number of Cartesian product of two complete graphs which is a lower bound of the total k -domination number of Cartesian product of two graphs. We obtain new lower and upper bounds for the total k -domination number of Cartesian product of two complete graphs. Some asymptotic behaviors are obtained as a consequence of the bounds we found. In particular, lim inf n → ∞ γ k t (G □ H) n : G , H are graphs of order n ≤ 2 k 2 − 1 + k + 4 2 − 1 − 1 . We also prove that the equality is attained if k is even. The equality holds when G , H are both isomorphic to the complete graph, K n , with n vertices. Furthermore, we obtain closed formulas for the total 2-domination number of Cartesian product of two complete graphs of whatever order. Besides, we prove that, for k = 3 , the inequality above is improvable to lim inf n → ∞ γ 3 t (K n □ K n) / n ≤ 11 / 5. [ABSTRACT FROM AUTHOR]

In this work we obtain inequalities relating a general topological index of a graph, F (G) = ∑ u v ∈ E (G) f (d u , d v) , with its corresponding exponential index, e F (G) = ∑ u v ∈ E (G) e f (d u , d v) when a (symmetric) function f (· , ·) is evaluated in the degree of the two adjacent vertices to each edge. Besides, we relate two general exponential indices e F 1 and e F 2 that verify a general inequality. These general relations directly yield with new inequalities and bounds involving some well-known topological indices like the generalized atom-bound connectivity index A B C α , the generalized second Zagreb index M 2 α , the generalized Platt index P α , and their corresponding exponential indices e A B C α , e M 2 α , e P α . The results and methodology shown in this work can also be applied to other exponential topological indices. Also, our analysis shows the applicability of the exponential topological indices to the study of several physico-chemical properties of octane isomers. [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 concept of general sum connectivity index was introduced in the area of chemical graph theory recently. Several of its particular cases have proven to correlate well with physical and chemical properties of some molecules. The main aim of this paper is to obtain new inequalities relating the general sum connectivity indices of a graph and its line graph. [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]

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]

Let G = (V,E) be a graph of order n and let 1 ≤ k < n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V , two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper we characterize precisely, for each value of k, which graphs have a regular k-token graph and which connected graphs have a planar k-token graph. [ABSTRACT FROM AUTHOR]

If X is a geodesic metric space and $${x_1, x_2, x_3 \in X}$$ , a geodesic triangle T = { x, x, x} is the union of the three geodesics [ x x], [ x x] and [ x x] 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: X is δ-hyperbolic}. In this paper we characterize the hyperbolic product graphs for graph join G + H and the corona $${G\odot\mathcal H: G + H}$$ is always hyperbolic, and $${G\odot\mathcal H}$$ is hyperbolic if and only if G is hyperbolic. Furthermore, we obtain simple formulae for the hyperbolicity constant of the graph join G + H and the corona $${G \odot \mathcal H}$$ . [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]

Given any function f : Z + → R + , let us define the f-index I f (G) = ∑ u ∈ V (G) f (d u) and the f-polynomial P f (G , x) = ∑ u ∈ V (G) x 1 / f (d u) − 1 , for x > 0 . In addition, we define P f (G , 0) = lim x → 0 + P f (G , x) . We use the f-polynomial of a large family of topological indices in order to study mathematical relations of the inverse degree, the generalized first Zagreb, and the sum lordeg indices, among others. In this paper, using this f-polynomial, we obtain several properties of these indices of some classical graph operations that include corona product and join, line, and Mycielskian, among others. [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]