Almost distance-hereditary graphs
Distance-hereditary graphs (graphs in which the distances are preserved by induced subgraphs) have been introduced and characterized by \textit{E. Howorka} [Q. J. Math., Oxf. II. Ser. 28, 417-420 (1977; Zbl 0376.05040)]. Several characterizations involving metric properties have been obtained by \textit{H.-J. Bandelt} and \textit{H. M. Mulder} [J. Comb. Theory, Ser. B 41, 182-208 (1986; Zbl 0605.05024)]. In this paper the notion of distance-hereditary graphs is extended by introducing the class of almost distance-hereditary graphs (a very weak increase of the distance is allowed by induced subgraphs, i.e., for all connected induced subgraphs \(H=(Y,F)\) of \(G\), one has \(d_{H}(u,v)\leq d_{G}(u,v)+1\) for every \(u,v\in Y\)). A characterization of these graphs in terms of forbidden-induced subgraphs is obtained and other both combinatorial and metric properties are derived in the paper.
- Distance-hereditary graphs
- Distance-hereditary and strongly distance-hereditary graphs
- Bipartite almost distance-hereditary graphs
- Distance-hereditary digraphs
- Equistable distance-hereditary graphs
- On an extension of distance hereditary graphs
- On an extension of distance-hereditary graphs
- scientific article; zbMATH DE number 815104
- Dualizing distance-hereditary graphs
- Distance-hereditary comparability graphs
- On an extension of distance hereditary graphs
- Distance-hereditary graphs
- Hereditary modular graphs
- Distance labeling scheme and split decomposition
- (k,+)-distance-hereditary graphs
- Dualizing distance-hereditary graphs
- Bipartite almost distance-hereditary graphs
- Distance-hereditary graphs are clique-perfect
- Self-spanner graphs
- Hamilton cycles in almost distance-hereditary graphs
- Distance-hereditary and strongly distance-hereditary graphs
- Extended Distance-Hereditary Graphs
- On an extension of distance-hereditary graphs
- scientific article; zbMATH DE number 4063145 (Why is no real title available?)
- scientific article; zbMATH DE number 2044923 (Why is no real title available?)
- scientific article; zbMATH DE number 1501961 (Why is no real title available?)
- Requiring adjacent chords in cycles
- Hamiltonian cycle in almost distance-hereditary graphs with degree condition restricted to claws†
- Graphs with bounded induced distance
- A characterization of almost-2-distance-hereditary graphs in terms of their forbidden subgraphs
- Distance-hereditary graphs and signpost systems
- Distance-hereditary digraphs
- Hamiltonian problem on claw-free and almost distance-hereditary graphs
This page was built for publication: Almost distance-hereditary graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957743)
