On the hyperbolicity of bipartite graphs and intersection graphs

David Coudert 1 Guillaume Ducoffe 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Hyperbolicity is a measure of the tree-likeness of a graph from a metric perspective. Recently , it has been used to classify complex networks depending on their underlying geometry. Motivated by a better understanding of the structure of graphs with bounded hyperbolicity, we here investigate on the hyperbolicity of bipartite graphs. More precisely, given a bipartite graph B = (V0 ∪ V1 , E) we prove it is enough to consider any one side Vi of the bipartition of B to obtain a close approximate of its hyperbolicity δ(B) — up to an additive constant 2. We obtain from this result the sharp bounds δ(G) − 1 ≤ δ(L(G)) ≤ δ(G) + 1 and δ(G) − 1 ≤ δ(K(G)) ≤ δ(G) + 1 for every graph G, with L(G) and K(G) being respectively the line graph and the clique graph of G. Finally, promising extensions of our techniques to a broader class of intersection graphs are discussed and illustrated with the case of the biclique graph BK(G), for which we prove (δ(G) − 3)/2 ≤ δ(BK(G)) ≤ (δ(G) + 3)/2.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2016, 214, pp.187-195. 〈10.1016/j.dam.2016.06.017〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01220132
Contributeur : David Coudert <>
Soumis le : mardi 12 juillet 2016 - 14:12:24
Dernière modification le : lundi 4 décembre 2017 - 15:14:19

Fichier

bipartite.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Guillaume Ducoffe. On the hyperbolicity of bipartite graphs and intersection graphs. Discrete Applied Mathematics, Elsevier, 2016, 214, pp.187-195. 〈10.1016/j.dam.2016.06.017〉. 〈hal-01220132v2〉

Partager

Métriques

Consultations de la notice

201

Téléchargements de fichiers

136