(k, +)-Distance-Hereditary Graphs

Summary

This work introduces, characterize, and provides algorithmic results for (k, +)-distance-hereditary graphs, a class of distance-hereditary graphs used to model interconnection networks with desirable connectivity properties.

Keywords

Pathwidth, Combinatorics, Chordal graph, Indifference graph, Mathematics

References

A Routing Algorithm for Networks Based on Distance-Hereditary TopologiesGabriele Di Stefano — 1996
Compact-Port Routing Models and Applications to Distance-Hereditary GraphsSerafino Cicerone, Gabriele Di Stefano, Michele Flammini — 2001
Graph Classes: A SurveyAndreas Brandstädt, Van Bang Lê, Jeremy Spinrad — 1987
Graphs with bounded induced distanceSerafino Cicerone, Gabriele Di Stefano — 1998
Graph Classes Between Parity and Distance-hereditary GraphsSerafino Cicerone, Gabriele Di Stefano — 1999
Fault-tolerant meshes with small degreeJehoshua Bruck, Robert Cypher, Ching‐Tien Ho — 1993
Completely separable graphsPeter L. Hammer, Frédéric Maffray — 1990
Networks with small stretch numberSerafino Cicerone, Gabriele Di Stefano — 2000
A Graph Model for Fault-Tolerant Computing SystemsHayes — 1976
Distance-hereditary graphsHans‐Jürgen Bandelt, Henry Martyn Mulder — 1986
Almost distance-hereditary graphsMéziane Aı̈der — 2002
Self-Repairing NetworksArthur M. Farley, Andrzej Proskurowski — 1993
On the fault tolerance of some popular bounded-degree networksT. Leighton, Bruce M. Maggs, Ramesh K. Sitaraman — 1992
Graph Spanners: a SurveyJosé Soares — 1992
Graph spannersDavid Peleg, Alejandro A. Schäffer — 1989
On the Fault Tolerance of Some Popular Bounded-Degree NetworksFrank Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman — 1998
Fault-Tolerant Meshes with Small DegreeJehoshua Bruck, Robert Cypher, Ching‐Tien Ho — 1997
(k, +)-Distance-hereditary graphs (Extended abstract)Serafino Cicerone, Gianluca D'Ermiliis, G. Stefano — 2001
Survivable Networks with Bounded Delay: The Edge Failure CaseSerafino Cicerone, G. Stefano, Dagmar Handke — 1999

Cited by

A characterization of almost-2-distance-hereditary graphs in terms of their forbidden subgraphsS. Hayat, R. Sundareswaran, M. Shanmugapriya — 2026

Related papers

On 2K2-free graphs - Structural and Combinatorial ViewS. Dhanalakshmi, N. Sadagopan, V. Manogna — 2016
Computing the K-terminal Reliability of Circle GraphsMin-Sheng Lin, Chien‐Min Chen — 2016
Efficient algorithms for tuple domination on co-biconvex graphs and web graphsMaría Patricia Dobson, Valeria Leoni, María Inés Lopez Pujato — 2020
Edge clique partition in (k, ℓ)-graphsÁtila Arueira Jones, Fábio Protti, Renata R. Del-Vecchio — 2022
Minimizing Branching Vertices in Distance-preserving SubgraphsKshitij Gajjar, Jaikumar Radhakrishnan — 2018
Complexity of Edge Monitoring on Some Graph ClassesGuillaume Bagan, Fairouz Beggas, Mohammed Haddad — 2017
A Class ofParametric Regular Networks for Multicomputer ArchitectureslО. Г. Монахов, Э. А. Монахова — 2000
Distance-based Invariants and Measures in GraphsAleksander Kelenc — 2019
The Balanced Connected Subgraph ProblemSujoy Bhore, Sourav Chakraborty, Satyabrata Jana — 2018