Non-existence of bipartite graphs of diameter at least 4 and defect 2
- Authors: Pineda-Villavicencio, Guillermo
- Date: 2011
- Type: Text , Journal article
- Relation: Journal of Algebraic Combinatorics Vol. 34, no. 2 (2011), p. 163-182
- Full Text:
- Reviewed:
- Description: The 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. © 2010 Springer Science+Business Media, LLC.
On bipartite graphs of defect at most 4
- Authors: Feria-Purón, Ramiro , Pineda-Villavicencio, Guillermo
- Date: 2011
- Type: Text , Journal article
- Relation: Discrete Applied Mathematics Vol.160, no.1-2 (2011), p.140-154
- Full Text:
- Reviewed:
- Description: We consider the bipartite version of the degree/diameter problem, namely, given natural numbers Δ ≥ 2 and D ≥ 2, find the maximum number Nb (Δ, D) of vertices in a bipartite graph of maximum degree Δ and diameter D. In this context, the Moore bipartite bound Mb (Δ, D) represents an upper bound for Nb (Δ, D). Bipartite graphs of maximum degree Δ, diameter D and order Mb (Δ, D)-called Moore bipartite graphs-have turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree Δ ≥ 2, diameter D ≥ 2 and order Mb (Δ, D) - ε{lunate} with small ε{lunate} > 0, that is, bipartite (Δ, D, - ε{lunate})-graphs. The parameter ε{lunate} is called the defect. This paper considers bipartite graphs of defect at most 4, and presents all the known such graphs. Bipartite graphs of defect 2 have been studied in the past; if Δ ≥ 3 and D ≥ 3, they may only exist for D = 3. However, when ε{lunate} > 2 bipartite (Δ, D, - ε{lunate})-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite (Δ, D, - 4)-graphs; the complete catalogue of bipartite (3, D, - ε{lunate})-graphs with D ≥ 2 and 0 ≤ ε{lunate} ≤ 4; the complete catalogue of bipartite (Δ, D, - ε{lunate})-graphs with Δ ≥ 2, 5 ≤ D ≤ 187 (D ≠6) and 0 ≤ ε{lunate} ≤ 4; a proof of the non-existence of all bipartite (Δ, D, - 4)-graphs with Δ ≥ 3 and odd D ≥ 5. Finally, we conjecture that there are no bipartite graphs of defect 4 for Δ ≥ 3 and D ≥ 5, and comment on some implications of our results for the upper bounds of Nb (Δ, D). © 2011 Elsevier B.V. All rights reserved.