On the hyperbolicity of chordal graphs (Q5939209): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00026-001-8007-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2028452681 / rank | |||
Normal rank |
Latest revision as of 23:53, 19 March 2024
scientific article; zbMATH DE number 1625393
Language | Label | Description | Also known as |
---|---|---|---|
English | On the hyperbolicity of chordal graphs |
scientific article; zbMATH DE number 1625393 |
Statements
On the hyperbolicity of chordal graphs (English)
0 references
20 May 2002
0 references
The hyperbolicity of a metric space is the infimum of all \(\delta\) for which \(d(x,y)+ d(u,v)\leq \max\{d(x, u)+ d(y,v), d(x,v)+ d(y,u)\}+ \delta\) for all elements \(x\), \(y\), \(u\), \(v\) from the space. The notion can be viewed as expressing how `tree like' the space is, as spaces with hyperbolicity \(0\) are precisely the metric trees. This paper considers the hyperbolicity of graphs, with \(d\) the usual graph distance. It is proved that a chordal graph has hyperbolicity at most two. The paper also characterizes which chordal graphs have hyperbolicity one, in terms of forbidden isometric subgraphs.
0 references
block graphs
0 references
four-point condition
0 references
hyperbolicity
0 references
trees
0 references
distance
0 references
chordal graph
0 references