3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
5
  • $\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
    Commented Feb 6, 2016 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
    Commented Feb 6, 2016 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
    Commented Feb 6, 2016 at 22:26
  • $\begingroup$ I sincerely appreciate your answer, thank you very much. $\endgroup$
    – martin tassy
    Commented Feb 6, 2016 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
    Commented Feb 6, 2016 at 22:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .