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 Q3− 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 αi, i≥0, denotes the number of induced Hamming subgraphs of a quasi-median graph, then ∑i≥0 (−1)i αi=1. Finally, an Euler-type formula is derived for graphs that can be obtained by a sequence of connected expansions from K1.