Chordality and hyperbolicity of a graph

By Yaokun Wu, Chengpeng Zhang. 2009

62 citations recorded by the source corpus.

Let $G$ be a connected graph with the usual shortest-path metric $d$. The graph $G$ is $\delta$-hyperbolic provided for any vertices $x,y,u,v$ in it, the two larger of the three sums $d(u,v)+d(x,y),d(u,x)+d(v,y)$ and $d(u,y)+d(v,x)$ differ by at most $2\delta.$ The graph $G$ is $k$-chordal provided it has no induced cycle of length greater than $k.$ Brinkmann, Koolen and Moulton find that every 3-chordal graph is 1-hyperbolic and is not 1/2-hyperbolic if and only if it contains one of two special graphs as an isometric subgraph. For every $k\geq 4,$ we show that a $k$-chordal graph must be $\frac{\lfloor \frac{k}{2}\rfloor}{2}$-hyperbolic and there does exist a $k$-chordal graph which is not $\frac{\lfloor \frac{k-2}{2}\rfloor}{2}$-hyperbolic. Moreover, we prove that a 5-chordal graph is 1/2-hyperbolic if and only if it does not contain any of a list of six special graphs (See Fig. 3) as an isometric subgraph.

Subfields: Biochemistry, Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/d3299fe467e4f5174b132925fe4af46ba3411f8a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. José M. Rodríguez
  2. Jose Maria Sigarreta

In Geometry and Topology

  1. Jose Maria Sigarreta
  2. María Villeta
  3. Domingo Pestana
  4. José M. Rodríguez

Citations in the corpus