Difference between revisions of "The Degree Diameter Problem for Bipartite Graphs"

From Combinatorics Wiki

CW>Gpineda
(→‎References)
 
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
 +
==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==
 
==Introduction==
 
The '''degree/diameter problem for bipartite graphs''' can be stated as follows:
 
The '''degree/diameter problem for bipartite graphs''' can be stated as follows:
Line 48: Line 59:
 
| '''12''' ||style="background-color: #bbffff;" | '''266''' ||style="background-color: #bbffff;" | '''2 928''' ||style="background-color: #66ff66;" | 8 200||style="background-color: #bbffff;" | '''354 312''' ||style="background-color: #66ff66;" | 664 300 ||style="background-color: #66ff66;" | 4 650 100  ||style="background-color: #FF9900;" | 30 001 152 ||style="background-color: #FF9900;" | 300 383 050
 
| '''12''' ||style="background-color: #bbffff;" | '''266''' ||style="background-color: #bbffff;" | '''2 928''' ||style="background-color: #66ff66;" | 8 200||style="background-color: #bbffff;" | '''354 312''' ||style="background-color: #66ff66;" | 664 300 ||style="background-color: #66ff66;" | 4 650 100  ||style="background-color: #FF9900;" | 30 001 152 ||style="background-color: #FF9900;" | 300 383 050
 
|-
 
|-
−
| '''13''' ||style="background-color: #CC6600;" | 270 ||style="background-color: #CC6600;" | 3 064 ||style="background-color: #66ff66;" |11 480 ||style="background-color: #CC6600;" | 374 452 ||style="background-color: #66ff66;" | 1 062 936 ||style="background-color: #66ff66;" | 5 314 680  ||style="background-color: #FF9900;" | 50 990 610 ||style="background-color: #FF9900;" | 617 330 936
+
| '''13''' ||style="background-color: pink;" | 274 ||style="background-color: #CC6600;" | 3 064 ||style="background-color: #66ff66;" |11 480 ||style="background-color: #CC6600;" | 374 452 ||style="background-color: #66ff66;" | 1 062 936 ||style="background-color: #66ff66;" | 5 314 680  ||style="background-color: #FF9900;" | 50 990 610 ||style="background-color: #FF9900;" | 617 330 936
 
|-
 
|-
 
| '''14''' ||style="background-color: #bbffff;" | '''366''' ||style="background-color: #bbffff;" | '''4 760''' ||style="background-color: #66ff66;" | 14 760 ||style="background-color: #bbffff;" | '''804 468''' ||style="background-color: #66ff66;" | 1 771 560 ||style="background-color: #66ff66;" | 14 172 480 ||style="background-color: #FF9900;" |95 087 738 ||style="background-color: #FF9900;" | 1 213 477 190
 
| '''14''' ||style="background-color: #bbffff;" | '''366''' ||style="background-color: #bbffff;" | '''4 760''' ||style="background-color: #66ff66;" | 14 760 ||style="background-color: #bbffff;" | '''804 468''' ||style="background-color: #66ff66;" | 1 771 560 ||style="background-color: #66ff66;" | 14 172 480 ||style="background-color: #FF9900;" |95 087 738 ||style="background-color: #FF9900;" | 1 213 477 190
 
|-
 
|-
−
| '''15''' || style="background-color: #CC6600;" | 370 || style="background-color: #CC6600;" | 4 946 ||style="background-color: #66ff66;" | 20 496 || style="background-color: #CC6600;" | 842 048 ||style="background-color: #66ff66;" | 2 480 184 || style="background-color: #66ff66;" | 14 172 480  ||style="background-color: #FF9900;" | 168 016 334 ||style="background-color: #FF9900;" | 2 300 326 510
+
| '''15''' || style="background-color: pink;" | 374 || style="background-color: #CC6600;" | 4 946 ||style="background-color: #66ff66;" | 20 496 || style="background-color: #CC6600;" | 842 048 ||style="background-color: #66ff66;" | 2 480 184 || style="background-color: #66ff66;" | 14 172 480  ||style="background-color: #FF9900;" | 168 016 334 ||style="background-color: #FF9900;" | 2 300 326 510
 
|-
 
|-
 
| '''16''' ||style="background-color: #CC6600;" | 394  ||style="background-color: #CC6600;" | 5 134 ||style="background-color: #66ff66;" | 27 300 || style="background-color: #CC6600;" | 884 062 || style="background-color: #66ff66;" | 4 022 340 ||style="background-color: #66ff66;" | 36 201 060 ||style="background-color: #FF9900;" | 288 939 118 ||style="background-color: #FF9900;" | 4 119 507 330
 
| '''16''' ||style="background-color: #CC6600;" | 394  ||style="background-color: #CC6600;" | 5 134 ||style="background-color: #66ff66;" | 27 300 || style="background-color: #CC6600;" | 884 062 || style="background-color: #66ff66;" | 4 022 340 ||style="background-color: #66ff66;" | 36 201 060 ||style="background-color: #FF9900;" | 288 939 118 ||style="background-color: #FF9900;" | 4 119 507 330
Line 78: Line 89:
 
|style="background-color: #FF9900; text-align: center;" | * || 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.
 
|style="background-color: #FF9900; text-align: center;" | * || 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.
 
|-
 
|-
−
|style="background-color: yellow; text-align: center;" | * || Graphs found by R. Feria-Puron, M. Miller and G. Pineda-Villavicencio.  
+
|style="background-color: yellow; text-align: center;" | * || Graphs found by R. Feria-Puron, M. Miller and G. Pineda-Villavicencio and independently by G. Araujo and N. López.
 +
|-
 +
|style="background-color: pink; text-align: center;" | * || Graphs found by G. Araujo and N. López.  
 
|}
 
|}
 
</center>
 
</center>

Latest revision as of 05:55, 18 February 2022

Citation

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

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 Nb(d,k) of vertices in a bipartite graph of maximum degree d and diameter k.

An upper bound for Nb(d,k) is given by the so-called bipartite Moore bound Mb(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 Nb(d,k), research activities in this problem have follow the following two directions:

  • Increasing the lower bounds for Nb(d,k) by constructing ever larger graphs.
  • Lowering and/or setting upper bounds for Nb(d,k) by proving the non-existence of graphs

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

Increasing the lower bounds for Nb(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 Nb(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 Mb(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.
Retrieved from ‘http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Bipartite_Graphs&oldid=649’