ISSN:
1439-6912
Keywords:
05C38
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02122796
Permalink