|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Chordality and hyperbolicity of a graph | | Yaokun Wu
; Chengpeng Zhang
; | | Date: |
19 Oct 2009 | | Abstract: | 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 $2delta.$ 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 $kgeq 4,$ we show that a $k$-chordal graph must be $frac{lfloor
frac{k}{2}
floor}{2}$-hyperbolic and there does exist a $k$-chordal graph
which is not $frac{lfloor frac{k-2}{2}
floor}{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. | | Source: | arXiv, 0910.3544 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER