Quasi-median graphs, their generalizations, and tree-like equalities

Three characterizations of quasi-median graphs are proved, for instance, they are partial Hamming graphs without convex house and convex Q(3)(-) such that certain relations on their edge sets coincide. Expansion procedures, weakly 2-convexity, and several relations on the edge set of a graph are essential for these results. Quasi-semimedian graphs are characterized which yields an additional characterization of quasi-median graphs. Two equalities for quasi-median graphs are proved. One of them asserts that if alpha(i), i greater than or equal to 0, denotes the number of induced Hamming subgraphs of a quasi-median graph, then Sigma(igreater than or equal to0) (-1)(i) alpha(i) = 1. Finally, an Euler-type formula is derived for graphs that can be obtained by a sequence of connected expansions from K-1. (C) 2003 Elsevier Science Ltd. All rights reserved.