On the hyperbolicity constant of circular-arc graphs
From MaRDI portal
Publication:2420429
Abstract: Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.
Recommendations
- On the hyperbolicity constant in graphs
- The hyperbolicity constant of infinite circulant graphs
- Circular-arc hypergraphs: rigidity via connectedness
- On the hyperbolicity constant of line graphs
- A note on the Hadwiger number of circular arc graphs
- Hadwiger's conjecture for proper circular arc graphs
- Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant
- On some subclasses of circular-arc graphs
- On the hyperbolicity constant in graph minors
- On the circular altitude of graphs
Cites work
- A survey of Nordhaus-Gaddum type relations
- Artin groups of finite type are biautomatic
- Bounds on Gromov hyperbolicity constant
- Characterizing hyperbolic spaces and real trees
- Chordality properties and hyperbolicity on graphs
- Computing the Gromov hyperbolicity of a discrete metric space
- Computing the hyperbolicity constant
- Cop and robber game and hyperbolicity
- Counting subgraphs in hyperbolic graphs with symmetry
- Data center interconnection networks are not hyperbolic
- Discrete groups. Transl. from the Japanese by Ken'ichi Ohshika
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- Extremal interval graphs
- Graph homotopy and Graham homotopy
- Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces
- Gromov hyperbolic cubic graphs
- Gromov hyperbolic graphs
- Gromov hyperbolic tessellation graphs
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 848089 (Why is no real title available?)
- Hyperbolic bridged graphs
- Hyperbolicity and chordality of a graph
- Hyperbolicity and complement of graphs
- Hyperbolicity and parameters of graphs.
- Hyperbolicity in median graphs
- Lack of Gromov-hyperbolicity in colored random networks
- Lack of Gromov-hyperbolicity in small-world networks
- Linear-time recognition of circular-arc graphs
- Mathematical properties on the hyperbolicity of interval graphs
- Metric embedding, hyperbolic space, and social networks
- New inequalities on the hyperbolicity constant of line graphs.
- Non-hyperbolicity of random graphs with given expected degrees
- Notes on diameters, centers, and approximating trees of -hyperbolic geodesic spaces and graphs
- On a classical theorem on the diameter and minimum degree of a graph
- On Complementary Graphs
- On the hyperbolicity constant in graphs
- On the hyperbolicity of bipartite graphs and intersection graphs
- On the hyperbolicity of chordal graphs
- On the hyperbolicity of edge-chordal and path-chordal graphs
- On the likelihood of forests
- Recognition of C₄-free and 1/2-hyperbolic graphs
- Small values of the hyperbolicity constant in graphs
- Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
- Topics in Intersection Graph Theory
- Traffic congestion in expanders and (p, )-hyperbolic spaces
Cited in
(8)- Domination on hyperbolic graphs
- The hyperbolicity constant of infinite circulant graphs
- A note on the Hadwiger number of circular arc graphs
- On the hyperbolicity of bipartite graphs and intersection graphs
- Circular-arc hypergraphs: rigidity via connectedness
- Recent Results on Hyperbolicity on Unitary Operators on Graphs
- On the hyperbolicity constant in graphs
- Gromov hyperbolicity of Johnson and Kneser graphs
This page was built for publication: On the hyperbolicity constant of circular-arc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2420429)
