zbMATH — the first resource for mathematics

Distance-hereditary graphs. (English) Zbl 0605.05024
A distance-hereditary graph is a connected graph in which every induced path is isometric, that is, the distance between any two vertices in an induced path equals their distance in the graph. A block graph is a conncted graph in which every block (i.e., maximal 2-connected subgraph) is complete. Let G be a graph with distance function d. Then d is said to satisfy the four-point condition if for any four vertices u, v, w, x the larger two of the three distance sums \(d(u,v)+d(w,x)\), \(d(u,w)+d(v,x)\) and \(d(u,x)+d(v,w)\) are equal. An induced subgraph H of a graph G is said to be an isometric subgraph if for any two vertices u, v of H the distance between u and v in H equals the distance between u and v in G. The authors show that if G is a connected graph having distance function d, then the following conditions are equivalent: (i) G is a block graph, (ii) d satisfies the four-point condition and (iii) neither \(K_ 4\) minus an edge nor any circuit \(C_ n\) with \(n\geq 4\) is an isometric subgraph of G. It is also shown that the finite distance-hereditary graphs of order at least 2 are precisely those graphs which are obtained by applying a sequence of extensions (which are described in the paper) to \(K_ 2\). Several consequences of this result are addressed. Moreover, distance-hereditary graphs are characterized in terms of the distance function d, or via forbidden isometric subgraphs.
Reviewer: O.Oellermann

05C38 Paths and cycles
05C75 Structural characterization of families of graphs
Full Text: DOI
[1] \scH. J. Bandelt, Characterizing median graphs, European J. Math., in press. · Zbl 0536.05057
[2] Blumenthal, L.M, ()
[3] Buneman, P, A note on the metric properties of trees, J. combin. theory ser. B, 17, 48-50, (1974) · Zbl 0286.05102
[4] Burlet, M; Uhry, J.P, Parity graphs, Ann. discrete math., 16, 1-26, (1982) · Zbl 0496.05044
[5] Corneil, D.G; Lerchs, H; Burlingham, L.Stewart, Complement reducible graphs, Discrete appl. math., 3, 163-174, (1981) · Zbl 0463.05057
[6] Howorka, E, A characterization of distance-hereditary graphs, Quart. J. math. Oxford ser. 2, 28, 417-420, (1977) · Zbl 0376.05040
[7] Howorka, E, A characterization of ptolemaic graphs; survey of results, (), 355-361
[8] Howorka, E, On metric properties of certain clique graphs, J. combin theory ser. B, 27, 67-74, (1979) · Zbl 0337.05138
[9] Howorka, E, A characterization of ptolemaic graphs, J. graph theory, 5, 323-331, (1981) · Zbl 0437.05046
[10] Jamison-Waldner, R.E, Convexity and block graphs, Congressus numerantium, 33, 129-142, (1981) · Zbl 0495.05056
[11] Jamison-Waldner, R.E, A perspective on abstract convexity: classifying alignments by varieties, (), 113-150 · Zbl 0482.52001
[12] Jung, H.A, On a class of posets and the corresponding comparability graphs, J. combin. theory ser. B, 24, 125-133, (1978) · Zbl 0382.05045
[13] Kay, D.C; Chartrand, G, A characterization of certain ptolemaic graphs, Canad. J. math., 17, 342-346, (1965) · Zbl 0139.17301
[14] Melter, R.A; Tomescu, I, Isometric embeddability for graphs, Ars combin., 12, 111-115, (1981) · Zbl 0492.05026
[15] Mulder, H.M, (), Math. Centre Tracts 132
[16] Simões Pereira, J.M.S, A note on the tree realizability of a distance matrix, J. combin. theory, 6, 303-310, (1969) · Zbl 0177.26903
[17] Soltan, V.P, d-convexity in graphs, Soviet math. dokl., 28, 419-421, (1983) · Zbl 0553.05060
[18] Soltan, V.P, (), [Russian]
[19] Sumner, D.P, Dacey graphs, J. austral. math. soc., 18, 4, 492-502, (1974) · Zbl 0314.05108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.