Definition Let $G=U\cup V$ is bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. The complete bipartite graph denoted by $K_{p,q}$ is bipartite graph where every vertex in $U$ is connected to every vertex in $V$.

Background It is known that the eigenvalues of complete bipartite graph $K_{p,q}$ are $\sqrt{pq}$, -$\sqrt{pq}$, and 0 with multiplicity $p+q-2$. (see Theorem 3.4 in [1]).

Question My question: Can this result generalized to regular bipartite graph?

In other words what is the eigenvalues of $d$-regular bipartite graph, where $d\leq p$? (Note that in this case $|U|=|V|=p$ ).

Any help will be useful!

  • 1
    $\begingroup$ If your graph is $d$-regular, then you have $d$ as an eigenvalue. I'm not sure you would be able to say much more than that without more structural requirements. $\endgroup$ – Morgan Rodgers Feb 17 '16 at 14:56
  • $\begingroup$ @MorganRodgers Please note that if $\lambda$ is eigenvalues with multiplicity $l$, then -$\lambda$ is also eigenvalue with multiplicity $l$. $\endgroup$ – M.Badaoui Feb 17 '16 at 15:35
  • 1
    $\begingroup$ I don't think that all connected regular bipartite graphs with the same number of vertices are isomorphic. For example, take bipartite graphs associated with non-isomorphic projective planes of order 9. $\endgroup$ – Morgan Rodgers Feb 17 '16 at 15:44
  • 4
    $\begingroup$ I am pretty sure there is no general result in this direction. Considering just connected cubic bipartite graphs of order 16 for example (38) one can see that all but two have distinct (multi)sets of eigenvalues. $\endgroup$ – Jernej Feb 17 '16 at 17:19
  • 1
    $\begingroup$ There are 38 cubic bipartite graphs of order 16. $\endgroup$ – Jernej Feb 18 '16 at 8:51

Your Answer

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

Browse other questions tagged or ask your own question.