Grupo de Análisis Matemático Aplicado (GAMA)
http://hdl.handle.net/10016/5857
2019-06-25T20:33:27ZGraph Theory
http://hdl.handle.net/10016/28073
Graph Theory
Rodríguez García, José Manuel
2018-01-22T00:00:00ZHyperbolicity of direct products of graphs
http://hdl.handle.net/10016/28036
Hyperbolicity of direct products of graphs
Carballosa Torres, Walter; Cruz Rodríguez, Amauris de la; Martinez Perez, Alvaro; Rodríguez García, José Manuel
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) x 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).
2018-07-12T00:00:00ZHyperbolicity on Graph Operators
http://hdl.handle.net/10016/28010
Hyperbolicity on Graph Operators
Mendez Bermudez, J.A.; Reyes Guillermo, Rosalio; Rodríguez García, José Manuel; Sigarreta Almira, Jose Maria
A graph operator is a mapping F : Gamma → Gamma 0 , where Gamma and Gamma 0 are families of graphs. The different kinds of graph operators are an important topic in Discrete Mathematics and its applications. The symmetry of this operations allows us to prove inequalities relating the hyperbolicity constants of a graph G and its graph operators: line graph, Lambda(G); subdivision graph, S(G); total graph, T(G); and the operators R(G) and Q(G). In particular, we get relationships such as delta(G) ≤ delta(R(G)) ≤ delta(G) + 1/2, delta(Lambda(G)) ≤ delta(Q(G)) ≤ delta(Lambda(G)) + 1/2, delta(S(G)) ≤ 2delta(R(G)) ≤ delta(S(G)) + 1 and delta(R(G)) − 1/2 ≤ delta(Lambda(G)) ≤ 5delta(R(G)) + 5/2 for every graph which is not a tree. Moreover, we also derive some inequalities for the Gromov product and the Gromov product restricted to vertices.
2018-08-24T00:00:00ZHarmonic index and harmonic polynomial on graph operations
http://hdl.handle.net/10016/28007
Harmonic index and harmonic polynomial on graph operations
Hernandez Gomez, Juan C.; Mendez Bermudez, J.A.; Rodríguez García, José Manuel; Sigarreta Almira, Jose Maria
Some years ago, the harmonic polynomial was introduced to study the harmonic topological index. Here, using this polynomial, we obtain several properties of the harmonic index of many classical symmetric operations of graphs: Cartesian product, corona product, join, Cartesian sum and lexicographic product. Some upper and lower bounds for the harmonic indices of these operations of graphs, in terms of related indices, are derived from known bounds on the integral of a product on nonnegative convex functions. Besides, we provide an algorithm that computes the harmonic polynomial with complexity O(n 2 ).
2018-10-01T00:00:00Z