Analysis of Complex Networks

13.3 Treelike Equalities and Euler-Type Inequalities

In this section we present treelike equalities and Euler type inequalities for median graphs and their generalizations: quasi-median graphs, partial cubes, and cage-amalgamation graphs.

13.3.1 Treelike Eequalities and Euler-Type Inequalities for Median Graphs

Let G be a median graph. Two splits{A, } and {B, } of G are said to be incompatible if all four of the possible intersections A∩ B, A∩ , ∩ B, and ∩ are nonempty (otherwise they are called compatible). The corresponding Θ-classes F_A and F_B are said to cross if the splits{A, } and {B, } are incompatible. The next theorem, probably observed for the first time by Isbell [44] (in slightly different ...