2009/10/19 by Yaokun Wu, Chengpeng Zhang, Wu, Yaokun +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Amino Acid Enzymes and Metabolism #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #math.CO
paper · pdf · doi:10.48550/arxiv.0910.3544
44 pages, second version
openalex publication_date 2009/10/19 · arxiv created 2010/06/02 · arxiv updated 2010/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected graph with the usual shortest-path metric d. The graph G is δ-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δ. 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≥ 4, we show that a k-chordal graph must be (\lfloor (k)/(2)\rfloor)/(2)-hyperbolic and there does exist a k-chordal graph which is not (\lfloor (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.