Graphs with bounded induced distance

DOI10.1016/S0166-218X(00)00227-4MaRDI QIDQ5928866zbMATH OpenOpenAlexFDO

Authors Serafino Cicerone, Gabriele Di Stefano

Publication date 23 July 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(00)00227-4

zbMATH Keywords

distance-hereditary graphsinduced distancestretch number

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Review text

The authors introduce the class BID(\(k\)) of graphs with bounded induced distance of order \(k\). A graph \(G\) belongs to BID(\(k\)) if the distance between any two vertices in every connected induced subgraph of \(G\) is at most \(k\) times their distance in \(G\). These graphs can model communication networks, and BID(1) corresponds to the class of distance-hereditary graphs. The authors give two characterizations of graphs belonging to BID(\(k\)). One is based on the so-called stretch number and the other on the cycle-chord condition. Furthermore, they investigate classes of order \(k\leq 2\) more precisely, and they show that the recognition problem for the class BID(\(k\)) is Co-NP-complete. Finally, the authors present some interesting open problems.

Recommendations

• scientific article; zbMATH DE number 1262797
• Almost distance-hereditary graphs
• Networks with small stretch number
• scientific article; zbMATH DE number 1696525
• Characterizations of graphs with stretch number less than 2

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Completely separable graphs
• Decomposition of Directed Graphs
• Designing networks with compact routing tables
• Distance-hereditary graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Dominating cliques in distance-hereditary graphs
• Graph classes between parity and distance-hereditary graphs
• Graph spanners
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1262797 (Why is no real title available?)
• scientific article; zbMATH DE number 205350 (Why is no real title available?)
• Interval Routing
• Parallel concepts in graph theory
• Transforming trees by successive local complementations

Cited in

(13)

• Bounded graphs
• Distance labeling scheme and split decomposition
• (k,+)-distance-hereditary graphs
• The feasible region of induced graphs
• Graph topologies induced by edge lengths
• Self-spanner graphs
• scientific article; zbMATH DE number 1696525 (Why is no real title available?)
• Characterizations of graphs with stretch number less than 2
• Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
• Extended Distance-Hereditary Graphs
• scientific article; zbMATH DE number 1262797 (Why is no real title available?)
• Bounded degrees and prescribed distances in graphs
• Networks with small stretch number

This page was built for publication: Graphs with bounded induced distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5928866)