The Degree Diameter Problem for Bipartite Graphs

Citation

If you are using combinatoricsWiki, then we would like to ask you to cite the site as follows.

• E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). Combinatorics Wiki, http://combinatoricswiki.org.

If you are using a specific page in combinatoricsWiki, say the "The degree-diameter problem for bipartite graphs" page, then it would be better to cite the page as follows.

• E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). The degree-diameter problem for bipartite graphs, Combinatorics Wiki, http://combinatoricswiki.org.

Introduction

The degree/diameter problem for bipartite graphs can be stated as follows:

Given natural numbers d and k, find the largest possible number N^b(d,k) of vertices in a bipartite graph of maximum degree d and diameter k.

An upper bound for N^b(d,k) is given by the so-called bipartite Moore bound M^b(d,k)=2((d-1)^k-2)(d-2)^-1. Bipartite (d,k)-graphs whose order attains the bipartite Moore bound are called bipartite Moore graphs.

Bipartite Moore graphs have proved to be very rare. Feit and Higman, and also independently Singleton, proved that such graphs exist only when the diameter is 2,3,4 or 6. In the cases when the diameter is 3, 4 or 6, they have been constructed only when d-1 is a prime power.

Therefore, in attempting to settle the values of N^b(d,k), research activities in this problem have follow the following two directions:

• Increasing the lower bounds for N^b(d,k) by constructing ever larger graphs.

• Lowering and/or setting upper bounds for N^b(d,k) by proving the non-existence of graphs

whose order is close to the bipartite Moore bounds M^b(d,k)=2((d-1)^k-1)(d-2)^-1.

Increasing the lower bounds for N^b(d,k)

In recent years there has not been much activity in the constructions of large bipartite graphs. This may be, in part, because there was not an online table showing the latest constructions. In this direction Charles Delorme (in some cases collaborating with Bond and Gómez-Martí) provided some large bipartite graphs by using graph compounding, the concept of partial Cayley graph, and other techniques.

Now, with the release of this online table (see below), we expect to stimulate further research on this area.

Below is the table of the largest known bipartite graphs (as of January 2012) in the undirected degree diameter problem for bipartite graphs of degree at most 3 ≤ d ≤ 16 and diameter 3 ≤ k ≤ 10. This table represents the best lower bounds known at present on the order of (d,k)-bipartite graphs. Many of the graphs of diameter 3 ,4 and 6 are bipartite Moore graphs, and thus are optimal. All optimal graphs are marked in bold.

Table of the orders of the largest known bipartite graphs

[math]d[/math]\[math]k[/math]	3	4	5	6	7	8	9	10
3	14	30	56	126	168	256	506	800
4	26	80	160	728	840	2 184	4 970	11 748
5	42	170	336	2 730	3 110	9 234	27 936	90 068
6	62	312	684	7 812	8 310	29 790	117 360	452 032
7	80	346	1 134	8 992	23 436	80 940	400 160	1 987 380
8	114	800	1 710	39 216	40 586	201 480	1 091 232	6 927 210
9	146	1 170	2 496	74 898	117 648	449 480	2 961 536	20 017 260
10	182	1 640	4 000	132 860	224 694	1 176 480	7 057 400	50 331 156
11	190	1 734	5 850	142 464	398 580	2 246 940	15 200 448	130 592 354
12	266	2 928	8 200	354 312	664 300	4 650 100	30 001 152	300 383 050
13	274	3 064	11 480	374 452	1 062 936	5 314 680	50 990 610	617 330 936
14	366	4 760	14 760	804 468	1 771 560	14 172 480	95 087 738	1 213 477 190
15	374	4 946	20 496	842 048	2 480 184	14 172 480	168 016 334	2 300 326 510
16	394	5 134	27 300	884 062	4 022 340	36 201 060	288 939 118	4 119 507 330

The following table is the key to the colors in the table presented above:

Color	Details
*	Bipartite Moore graphs (optimal).
*	Graph duplications found by C. Delorme and G. Farhi.
*	Graphs found by C. Delorme, J. Gómez, and J. J. Quisquater.
*	Optimal graph found by R. Bar-Yehuda and T. Etzion and by J. Bond and C. Delorme.
*	Graph found independently by M. Conder and R. Nedela., by C. Delorme, J. Gómez, and J. J. Quisquater and by Eyal Loz.
*	Graphs found independently by Paul Hafner and by Eyal Loz.
*	Graphs found by Eyal Loz as part of the joint project The degree/diameter problem for several classes of graphs by E. Loz, H. Pérez-Rosés and G. Pineda-Villavicencio.
*	Graphs found by R. Feria-Puron, M. Miller and G. Pineda-Villavicencio and independently by G. Araujo and N. López.
*	Graphs found by G. Araujo and N. López.

Lowering and/or setting upper bounds for N^b(d,k)

The Moore bound can be reached in some cases, but not always in general. Some theoretical work was done to determine the lowest upper bounds. In this direction reserachers have been interested in bipartite graphs of maximum degree d, diameter k and order M^b(d,k)-δ for small δ. The parameter δ is called the defect. Such graphs are called bipartite (d,k,-δ)-graphs.

The bipartite (d,k,-2;)-graphs constitute the first interesting family of graphs to be studied. When d≥3 and k=2, bipartite (d,k,-2)-graphs are the complete bipartite graphs with partite sets of orders p and q, where either p=q=d-1 or p=d and q=d-2. For d≥3 and k≥3 only two such graphs are known; a unique bipartite (3, 3,-2)-graph and a unique bipartite (4, 3,-2)-graph.

Studies on bipartite (d,k,-2;)-graphs have been carried out by Charles Delorme, Leif Jorgensen, Mirka Miller and Guillermo Pineda-Villavicencio. They proved several necessary conditions for the existence of bipartite (d,3,-2;)-graphs, the uniqueness of the two known bipartite (d,k,-2;)-graphs for d≥3 and k≥3, and the non-existence of bipartite (d,k,-2;)-graphs for d≥3 and k≥4.

Lowest known upper bounds and the percentage of the order of the largest known bipartite graphs

[math]d[/math]\[math]k[/math]	3	4	5	6	7	8	9	10
3	14 100%	30 100%	56 100%	126 100%	248 67.74%	504 50.79%	1016 49.80%	2040 39.21%
4	26 100%	80 100%	236 67.79%	728 100%	2180 38.53%	6554 33.32%	19676 25.25%	59042 19.89%
5	42 100%	170 100%	676 49.70%	2730 100%	10916 28.49%	43684 21.13%	174756 15.98%	699044 12.88%
6	62 100%	312 100%	1556 43.95%	7812 100%	39056 21.27%	195306 15.25%	976556 12.01%	4882806 9.25%
7	80 100%	518 66.79%	3106 36.50%	18662 48.18%	111968 20.92%	671840 12.04%	4031072 9.92%	24186464 8.21%
8	114 100%	800 100%	5596 30.55%	39216 100%	274508 14.78%	1921594 10.48%	13451196 8.11%	94158410 7.35%
9	146 100%	1170 100%	9356 26.67%	74898 100%	599180 19.63%	4793484 9.37%	38347916 7.72%	306783372 6.52%
10	182 100%	1640 100%	14756 27.10%	132860 100%	1195736 18.79%	10761674 10.93%	96855116 7.28%	871696094 5.77%
11	220 86.36%	2222 78.03%	22216 26.33%	222222 64.10%	2222216 17.93%	22222216 10.11%	222222216 6.84%	2222222216 5.87%
12	266 100%	2928 100%	32204 25.46%	354312 100%	3897428 17.04%	42871770 10.84%	471589532 6.36%	5187484914 5.79%
13	314 85.98%	3770 81.27%	45236 25.37%	542906 68.97%	6514868 16.31%	78178484 6.79%	938141876 5.43%	11257702580 5.48%
14	366 100%	4760 100%	61876 23.85%	804468 100%	10458080 16.93%	135955114 10.42%	1767416556 5.38%	22976415302 5.28%
15	422 87.67%	5910 83.68%	82736 24.77%	1158390 72.69%	16217456 15.29%	227044464 0%	3178622576 5.28%	44500716144 5.17%
16	482 81.74%	7232 70.99%	108476 25.16%	1627232 54.32%	24408476 16.47%	366127226 9.88%	5491908476 5.26%	82378627226 5%

The following table is the key to the colors in the table presented above:

Color	Details
*	Moore bound.
*	Moore bound minus 2.
*	Moore bound minus 6.

References

• Conder, M.; Nedela, R. (2006), "A more detailed classification of symmetric cubic graphs", preprint.
• Bar-Yehuda, R.; Etzion, T. (1992), "Connections between two cycles - a new design of dense processor interconnection networks", Discrete Applied Mathematics 37-38.
• Bond, J.; Delorme, C. (1988), "New large bipartite graphs with given degree and diameter", Ars Combinatoria 25C: 123-132.
• Bond, J.; Delorme, C. (1993), "A note on partial Cayley graphs", Discrete Mathematics 114 (1-3): 63--74, doi:10.1016/0012-365X(93)90356-X.
• Delorme, C. (1985), "Grands graphes de degré et diamètre donnés", European Journal of Combinatorics 6: 291-302.
• Delorme, C. (1985), "Large bipartite graphs with given degree and diameter", Journal of Graph Theory 8: 325-334.
• Delorme, C.; Farhi, G. (1984), "Large graphs with given degree and diameter Part I", IEEE Transactions on Computers C-33: 857-860.
• Delorme, C.; Gómez (2002), "Some new large compound graphs", European Journal of Combinatorics 23 (5): 539-547, doi:10.1006/eujc.2002.0581.
• Delorme, C.; Gómez, J.; Quisquater, J. J., "On large bipartite graphs", submitted.
• Delorme, C.; Jorgensen, L.; Miller, M.; Pineda-Villavicencio, G., "On bipartite graphs of diameter 3 and defect 2", Journal of Graph Theory 61 (2009), no. 4, 271-288.
• Delorme, C.; Jorgensen, L.; Miller, M.; Pineda-Villavicencio, G., "On bipartite graphs of defect 2", European Journal of Combinatorics 30 (2009), no. 4, 798-808.
• Pineda-Villavicencio, G., Non-existence of bipartite graphs of diameter at least 4 and defect 2, Journal of Algebraic Combinatorics 34 (2011), no. 2, 163-182.
• Miller, M.; Širáň, J. (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey D, PDF version.

External links

• Eyal Loz's Degree-Diameter problem page, including adjacency lists for bipartite graphs smaller than 20,000 found as a part of the project The degree/diameter problem for several classes of graphs.