- Title
- On bipartite graphs of defect 2
- Creator
- Delorme, Charles; Jørgensen, Leif K.; Miller, Mirka; Pineda-Villavicencio, Guillermo
- 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
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2009
- 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.
- Subject
- diameter problem for bipartite graphs; degree problem for bipartite graphs; bipartite Moore bounds; bipartite Moore graphs
- Identifier
- http://hdl.handle.net/1959.13/809097
- Identifier
- uon:7826
- Identifier
- ISSN:0195-6698
- Language
- eng
- Reviewed
- Hits: 2546
- Visitors: 1643
- Downloads: 2
| Thumbnail | File | Description | Size | Format |
|---|