Cartesian products of block graphs
Tóm tắt
Hamming graphs (being the Cartesian products of complete graphs) are known to be the quasi-median graphs not containing the 3-vertex path as a convex subgraph. Similarly, the Cartesian products of trees have been characterized among median graphs by a single forbidden convex subgraph. In this note a common generalization of these two results is given that characterizes the Cartesian products of block graphs.
Tài liệu tham khảo
H.-J. Bandelt, G. Burosch, andJ.-M. Laborde. Cartesian products of trees and paths.J. Graph Theory, to appear.
H.-J. Bandelt andH. M. Mulder. Infinite median graphs, (0,2)-graphs, and hypercubes.J. Graph Theory 7 (1983), 487–497.
H.-J. Bandelt andH. M. Mulder. Cartesian factorization of interval-regular graphs having no long isometric odd cycles. In:Graph Theory, Combinatorics, and Applications, Vol. 1 (Y. Alavi et al. eds.). Wiley, New York 1991, 55–75, for a corrigendum see Math. Reviews94f: 05110.
H.-J. Bandelt, H. M. Mulder, andE. Wilkeit. Quasi-median graphs and algebras.J. Graph Theory 18 (1994), 681–703.
V. D. Chepoi.d-Convexity and local conditions on graphs, (in Russian).Issled. Priklad. Mat. i Inf., Shtünca, Kishinev (1980), 184–191.
F. R. K. Chung, R. L. Graham, andM. E. Saks. A dynamic location problem for graphs.Combinatorica 9 (1989), 111–131.
H. M. Mulder. The interval function of a graph.Math. Centre Tracts 132, Amsterdam, 1980.
M. van de Vel. Binary convexities and distributive lattices.Proc. London Math. Soc. (3)48 (1984), 1–33.
E. Wilkeit. The retracts of Hamming graphs.Discrete Math. 102 (1992), 197–218.