5
$\begingroup$

Let $\Gamma$ be a finite connected bipartite graph with colour classes $U$ and $V$ such that:

  • every vertex of $U$ has degree $n$, and $n\ge 3$;
  • every vertex of $V$ has degree at least $4$;
  • $\Gamma$ has diameter $4$;
  • for every vertex $u$ of $U$, there are at least $(n+1)/2$ vertices in the neighbourhood $\Gamma(u)$ of $u$ that have degree the minimum degree of $\Gamma(u)$.

Is $\Gamma$ biregular (i.e., the vertices of $V$ have constant degree)? If not, then under what natural and weak conditions is biregularity forced to hold?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

I tried to construct an example that is not biregular. To make it easy, I assumed that n=3 and that the vertices of V all have degree 4 except one of degree 5 (so each vertex of U is automatically adjacent to at least two vertices of degree 4).

One option where the numbers work out is to have 7 vertices in U and 5 vertices in V, so if I set V = {A,B,C,D,E} and then make the 7 neighbourhoods equal to {ABC, ABD, ABE, ACE, ADE, BCD, CDE} then I think that vertex A has degree 5, and all the others degree 4.

I don't know what sort of condition you'd need to rule out examples like this..

Improve this answer
$\endgroup$
1
  • $\begingroup$ This example has small girth (=4), so is it possible to construct an example of girth 6? By the way, if the girth is 8, then it is well known that the graph is biregular (because then, we would have a thick generalised quadrangle). $\endgroup$
    – John Bamberg
    Commented Dec 17, 2016 at 0:02

You must log in to answer this question.

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