For a connected bipartite graph $G$ are the two following properties equivalent:

1)Every minimal cycle in $G$ has length 4, that is every cycle of length strictly greater than 4 can be divided in cycles of length 4 ($Z^d$ is such a graph).

2) For all triplet of vertices $\{ v_1, v_2, v_3 \}$ in $G$ there exist three geodesics from $v_1$ to $v_2$, $v_1$ to $v_3$ and $v_2$ to $v_3$ respectively, whose union form a subtree of $G$.

If yes, is there any reference for this? If no what would be a counter example?

Thank you for the answer


No. For instance a 3x3 grid is a median graph (it has a unique median for every three vertices, a stronger version of your property 2 which does not require uniqueness) but it is not chordal bipartite (the outer 8-cycle has no chord).

  • $\begingroup$ Sorry I think the property I am looking for is that every minimal cycle has length 4, that is every cycle of length strictly greater than 4 can be broken into cycle of length 4 ( which is the case of the 3x3 grid). I am not very knowledgeable in graph theory so I thought this was the definition of chordal bipartite. $\endgroup$ – martin tassy Feb 6 '16 at 22:23
  • $\begingroup$ Still no. Remove one vertex from a cube. Then the three neighbors of the removed vertex have no median, but the three remaining 4-cycles form a cycle basis (the remaining 6-cycle can be "broken into" three 4-cycles, in the same sense that the outer 8-cycle of a 3x3 grid can be broken into four 4-cycles. $\endgroup$ – David Eppstein Feb 6 '16 at 22:26
  • $\begingroup$ @martintassy What do you mean by "broken into cycle of length 4"? Usually chordal graph is about chords, it is natural to think the same for chordal bipartite. $\endgroup$ – Fedor Petrov Feb 6 '16 at 22:26
  • $\begingroup$ I sincerely appreciate your answer, thank you very much. $\endgroup$ – martin tassy Feb 6 '16 at 22:27
  • $\begingroup$ I am sincerely sorry for the approximative formulation, I am not very knowledgeable in graph theory. What I am looking for is for a different characterization of the property 2 (I need to check if some particular Cayley graph has it). Clearly chordal bipartite or having minimal cycles of length 4 does not work since the discretization of $S^2$ into a grid does not have property 2. I was hoping to find a reference in the literature. $\endgroup$ – martin tassy Feb 6 '16 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.