On median graphs and median grid graphs

摘要

Let G be a Q_4-free median graph on n vertices and m edges. Let k be the number of equivalence classes of Djokovic-Winkler's relation Θ and let h be the number of Q_3's in G. Then we prove that 2n - m - k + h = 2. We also characterize median grid graphs in several different ways, for instance, they are the grid graphs with m - n + 1 squares. To obtain these results we introduce the notion of square-edges, i. e. edges contained in exactly one 4-cycle of a graph.