Cube intersection concepts in median graphs

In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph GG and k≥0k≥0, the intersection graph Qk(G)Qk(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in GG, and two vertices HxHx and HyHy in Qk(G)Qk(G) are adjacent whenever the intersection Hx∩HyHx∩Hy contains a subgraph isomorphic to QkQk. Characterizations of clique-graphs in terms of these intersection concepts when k>0k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph GG, denoted Qm2(G), whose vertices are maximal hypercubes of GG, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph HH is diamond-free if and only if there exists a median graph GG such that HH is isomorphic to Qm2(G). We also study convergence of median graphs to the one-vertex graph with respect to all these operations.