pinedavillavicencio-nonexistenceof-2011.pdf (662.88 kB)
Non-existence of bipartite graphs of diameter at least 4 and defect 2
journal contribution
posted on 2011-09-01, 00:00 authored by Guillermo Pineda VillavicencioGuillermo Pineda VillavicencioThe Moore bipartite bound represents an upper bound on the order of a bipartite graph of maximum degree Δ and diameter D. Bipartite graphs of maximum degree Δ, diameter D and order equal to the Moore bipartite bound are called Moore bipartite graphs. Such bipartite graphs exist only if D=2,3,4 and 6, and for D=3,4,6, they have been constructed only for those values of Δ such that Δ-1 is a prime power. The scarcity of Moore bipartite graphs, together with the applications of such large topologies in the design of interconnection networks, prompted us to investigate what happens when the order of bipartite graphs misses the Moore bipartite bound by a small number of vertices. In this direction the first class of graphs to be studied is naturally the class of bipartite graphs of maximum degree Δ, diameter D, and two vertices less than the Moore bipartite bound (defect 2), that is, bipartite (Δ,D,-2)-graphs. For Δ≥3 bipartite (Δ,2,-2)-graphs are the complete bipartite graphs with partite sets of orders Δ and Δ-2. In this paper we consider bipartite (Δ,D,-2)-graphs for Δ≥3 and D≥3. Some necessary conditions for the existence of bipartite (Δ,3,-2)-graphs for Δ≥3 are already known, as well as the non-existence of bipartite (Δ,D,-2)-graphs with Δ≥3 and D=4,5,6,8. Furthermore, it had been conjectured that bipartite (Δ,D,-2)-graphs for Δ≥3 and D≥4 do not exist. Here, using graph spectra techniques, we completely settle this conjecture by proving the non-existence of bipartite (Δ,D,-2)-graphs for all Δ≥3 and all D≥6.
History
Journal
Journal of algebraic combinatoricsVolume
34Issue
2Pagination
163 - 182Publisher
SpringerLocation
New York, N.Y.Publisher DOI
Link to full text
ISSN
0925-9899eISSN
1572-9192Language
engPublication classification
C1.1 Refereed article in a scholarly journalCopyright notice
2010, Springer Science+Business Media, LLCUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC