On median graphs and median grid graphs (Q1567686)

Let \(G= (V,E)\) be a graph with \(|V|= n\) and \(|E|= m\). A cycle \(Q_4\) of length four is called a square and the distance \(d(u,v)\) between vertices \(u\) and \(v\) of \(G\) is the usual shortest path distance. A vertex \(x\) is a median of a triple of vertices \(u\), \(v\) and \(w\) if \(d(u,x)+ d(x,v)= d(u,v)\), \(d(v,x)+ d(x,w)= d(v,w)\) and \(d(u,x)+ d(x,w)= d(u,w)\) and a connected graph \(G\) is a median graph if every triple of its vertices has a unique median. For a graph \(G\), Djoković and Winkler's relation \(\Theta\) is defined on \(E(G)\) in the following manner: If \(e= xy\in E(G)\) and \(f= uv\in E(G)\), then \(e\Theta f\) if \(d(x,u)+ d(y,v)\neq d(x,v)+ d(y,u)\). It is known that \(\Theta\) defines an equivalence relation on \(E(G)\) of a median graph \(G\). The number of these equivalence classes be denoted by \(k\). The authors get the following first result for \(Q_4\)-free median graphs \(G\): For these graphs the equation \(2n- m-k+ h= 2\) holds, where \(h\) is the number of subgraphs of \(G\) isomorphic to \(Q_3\) (Theorem 4). In the second part median grid graphs are considered and characterized structurally; a grid graph is a subgraph of a complete grid (the Cartesian product of two paths) and complete grids are median graphs. The authors get as second result a characterization of a connected grid graph \(G\) by five equivalent statements, for instance: \(G\) is a median graph, \(G\) is a square-edge graph, or \(G\) contains \(m-n+1\) squares (Theorem 7).