Displaying similar documents to “Gromov hyperbolic cubic graphs”

The hyperbolicity constant of infinite circulant graphs

José M. Rodríguez, José M. Sigarreta (2017)

Open Mathematics

Similarity:

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 a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. Deciding whether or not a graph is hyperbolic is usually very difficult; therefore, it is interesting to find classes of graphs which are hyperbolic. A graph...

Gromov hyperbolicity of planar graphs

Alicia Cantón, Ana Granados, Domingo Pestana, José Rodríguez (2013)

Open Mathematics

Similarity:

We prove that under appropriate assumptions adding or removing an infinite amount of edges to a given planar graph preserves its non-hyperbolicity, a result which is shown to be false in general. In particular, we make a conjecture that every tessellation graph of ℝ2 with convex tiles is non-hyperbolic; it is shown that in order to prove this conjecture it suffices to consider tessellation graphs of ℝ2 such that every tile is a triangle and a partial answer to this question is given....

Structure of geodesics in the Cayley graph of infinite Coxeter groups

Ryszard Szwarc (2003)

Colloquium Mathematicae

Similarity:

Let (W,S) be a Coxeter system such that no two generators in S commute. Assume that the Cayley graph of (W,S) does not contain adjacent hexagons. Then for any two vertices x and y in the Cayley graph of W and any number k ≤ d = dist(x,y) there are at most two vertices z such that dist(x,z) = k and dist(z,y) = d - k. Allowing adjacent hexagons, but assuming that no three hexagons can be adjacent to each other, we show that the number of such intermediate vertices at a given distance from...

Path and cycle factors of cubic bipartite graphs

M. Kano, Changwoo Lee, Kazuhiro Suzuki (2008)

Discussiones Mathematicae Graph Theory

Similarity:

For a set S of connected graphs, a spanning subgraph F of a graph is called an S-factor if every component of F is isomorphic to a member of S. It was recently shown that every 2-connected cubic graph has a {Cₙ | n ≥ 4}-factor and a {Pₙ | n ≥ 6}-factor, where Cₙ and Pₙ denote the cycle and the path of order n, respectively (Kawarabayashi et al., J. Graph Theory, Vol. 39 (2002) 188-193). In this paper, we show that every connected cubic bipartite graph has a {Cₙ | n ≥ 6}-factor, and has...