Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/809097

OpenURL Link
Title
On bipartite graphs of defect 2
Author/Creator
Delorme, Charles;  Jørgensen, Leif K.;  Miller, Mirka;  Pineda-Villavicencio, Guillermo
Institution
The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description
It is known that the Moore bipartite bound provides an upper bound on the order of a connected bipartite graph. In this paper we deal with bipartite graphs of maximum degree ∆ ≥ 2, diameter D ≥ 2 and defect 2 (having 2 vertices less than the Moore bipartite bound). We call such graphs bipartite (∆,D,−2)-graphs. We find that the eigenvalues other than ±∆ of such graphs are the roots of the polynomials Hᴅ₋₁(x) ± 1, where Hᴅ₋₁(x) is the Dickson polynomial of the second kind with parameter ∆ − 1 and degree D − 1. For any diameter, we prove that the irreducibility over the field ℚ of rational numbers of the polynomial Hᴅ₋₁(x) − 1 provides a sufficient condition for the non-existence of bipartite (∆,D,−2)-graphs for ∆ ≥ 3 and D ≥ 4. Then, by checking the irreducibility of these polynomials, we prove the non-existence of bipartite (∆,D,−2)-graphs for all ∆ ≥ 3 and D ∈ {4,6,8}. For odd diameters, we develop an approach that allows us to consider only one partite set of the graph in order to study the non-existence of the graph. Based on this, we prove the non-existence of bipartite (∆,5,−2)-graphs for all ∆ ≥ 3. Finally, we conjecture that there are no bipartite (∆,D,−2)-graphs for ∆ ≥ 3 and D ≥ 4.
Relation
European Journal of Combinatorics Vol. 30, Issue 4, p. 798-808
Publisher Link
http://dx.doi.org/10.1016/j.ejc.2008.09.030
Date
2009
Publisher
Elsevier
Keyword(s)
diameter problem for bipartite graphs;  degree problem for bipartite graphs;  bipartite Moore bounds;  bipartite Moore graphs
Resource Type
journal article
Identifier
http://hdl.handle.net/1959.13/809097
Identifier
ISSN:0195-6698
Reviewed
Reviewed
12 Visitors 15 Hits 2 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"European Journal of Combinatorics"
 
OR