2020/07/28 by Heather M. Guarnera, Guarnera, Heather M., Feodor F. Dragan +3
Computer Science · Engineering · #Advanced Graph Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2007.14377
openalex publication_date 2020/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is Helly if its disks satisfy the Helly property, i.e., every family of pairwise intersecting disks in G has a common intersection. It is known that for every graph G, there exists a unique smallest Helly graph H(G) into which G isometrically embeds; H(G) is called the injective hull of G. Motivated by this, we investigate the structural properties of the injective hulls of various graph classes. We say that a class of graphs C is closed under Hellification if G ∈ C implies H(G) ∈ C. We identify several graph classes that are closed under Hellification. We show that permutation graphs are not closed under Hellification, but chordal graphs, square-chordal graphs, and distance-hereditary graphs are. Graphs that have an efficiently computable injective hull are of particular interest. A linear-time algorithm to construct the injective hull of any distance-hereditary graph is provided and we show that the injective hull of several graphs from some other well-known classes of graphs are impossible to compute in subexponential time. In particular, there are split graphs, cocomparability graphs, bipartite graphs G such that H(G) contains Ω(an) vertices, where n=|V(G)| and a>1.