pinedavillavicencio-onbipartite-2009.pdf (628.03 kB)
On bipartite graphs of defect 2
journal contribution
posted on 2009-05-01, 00:00 authored by C Delorme, L K Jørgensen, M Miller, Guillermo Pineda VillavicencioGuillermo Pineda VillavicencioIt 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 HD - 1 (x) ± 1, where HD - 1 (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 Q of rational numbers of the polynomial HD - 1 (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.
History
Journal
European journal of combinatoricsVolume
30Issue
4Pagination
798 - 808Publisher
ElsevierLocation
Amsterdam, The NetherlandsPublisher DOI
Link to full text
ISSN
0195-6698Language
engPublication classification
C1.1 Refereed article in a scholarly journalCopyright notice
2008, Elsevier LtdUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC