Skip to main content
SpringerLink
Log in

Hereditary modular graphs

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

In a hereditary modular graphG, for any three verticesu, v, w of an isometric subgraph ofG, there exists a vertex of this subgraph that is simultaneously on some shortestu, v-path,u, w-path andv, w-path. It is shown that the hereditary modular graphs are precisely those bipartite graphs which do not contain any isometric cycle of length greater than four. There is a polynomial-time algorithm available which decides whether a given (bipartite) graph is hereditary modular or not. Finally, the chordal bipartite graphs are characterized by forbidden isometric subgraphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. H. J.Bandelt, Characterizing median graphs,European J. Combinatorics, to appear.

  2. H. J. Bandelt, A. Dählmann andH. Schütte, Absolute retracts of bipartite graphs,Discrete Applied Math.,16 (1987), 191–215.

    Google Scholar 

  3. H. J. Bandelt andH. M. Mulder, Distance-hereditary graphs,J. Combinatorial Theory Ser. B 41 (1986), 182–208.

    Google Scholar 

  4. M. C. Golumbic andC. F. Goss, Perfect elimination and chordal bipartite graphs,J. Graph Theory 2 (1978), 155–163.

    Google Scholar 

  5. P. Hell, Absolute retracts in graphs,Lecture Notes Math. 406 (1974), 291–301.

    Google Scholar 

  6. E. Howorka, A characterization of distance-hereditary graphs,Quart. J. Math. Oxford Ser. 2 28 (1977), 417–420.

    Google Scholar 

  7. E. Howorka, Betweenness in graphs,Abstracts Amer. Math. Soc. 2 (1981), 783–06-5.

    Google Scholar 

  8. H. A. Jung, On a class of posets and the corresponding comparability graphs,J. Combinatorial Theory Ser. B 24 (1978), 125–133.

    Google Scholar 

  9. H. M. Mulder, The interval function of a graph.Math. Centre Tracts 132 (Mathematisch Centrum, Amsterdam, 1980).

    Google Scholar 

  10. E. Pesch andW. Poguntke, A characterization of absolute retracts ofn-chromatic graphs,Discrete Math. 57 (1985), 99–104.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität Oldenburg, Fachbereich 6, D-2900, Oldenburg, BRD

    H. -J. Bandelt

Authors
  1. H. -J. Bandelt
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bandelt, H.J. Hereditary modular graphs. Combinatorica 8, 149–157 (1988). https://doi.org/10.1007/BF02122796

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02122796

AMS subject classification (1980)

Search

Navigation