http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Bipartite_Graphs&feed=atom&action=history
The Degree Diameter Problem for Bipartite Graphs - Revision history
2024-03-28T14:27:06Z
Revision history for this page on the wiki
MediaWiki 1.31.1
http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Bipartite_Graphs&diff=649&oldid=prev
Guillermo at 05:55, 18 February 2022
2022-02-18T05:55:28Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en-GB">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 05:55, 18 February 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Citation==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">If you are using combinatoricsWiki, then we would like to ask you to cite the site as follows.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). Combinatorics Wiki, http://combinatoricswiki.org.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">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. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). The degree-diameter problem for bipartite graphs, Combinatorics Wiki, http://combinatoricswiki.org.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Introduction==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Introduction==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The '''degree/diameter problem for bipartite graphs''' can be stated as follows:</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The '''degree/diameter problem for bipartite graphs''' can be stated as follows:</div></td></tr>
</table>
Guillermo
http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Bipartite_Graphs&diff=524&oldid=prev
Grahame: /* Table of the orders of the largest known bipartite graphs */
2021-03-30T14:34:56Z
<p><span dir="auto"><span class="autocomment">Table of the orders of the largest known bipartite graphs</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en-GB">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 14:34, 30 March 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l48" >Line 48:</td>
<td colspan="2" class="diff-lineno">Line 48:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| '''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</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| '''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</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| '''13''' ||style="background-color: <del class="diffchange diffchange-inline">#CC6600</del>;" | <del class="diffchange diffchange-inline">270 </del>||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</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| '''13''' ||style="background-color: <ins class="diffchange diffchange-inline">pink</ins>;" | <ins class="diffchange diffchange-inline">274 </ins>||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</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| '''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</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| '''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</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| '''15''' || style="background-color: <del class="diffchange diffchange-inline">#CC6600</del>;" | <del class="diffchange diffchange-inline">370 </del>|| 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</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| '''15''' || style="background-color: <ins class="diffchange diffchange-inline">pink</ins>;" | <ins class="diffchange diffchange-inline">374 </ins>|| 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</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| '''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</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| '''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</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l78" >Line 78:</td>
<td colspan="2" class="diff-lineno">Line 78:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|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.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>|style="background-color: yellow; text-align: center;" | * || Graphs found by R. Feria-Puron, M. Miller and G. Pineda-Villavicencio.  </div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>|style="background-color: yellow; text-align: center;" | * || Graphs found by R. Feria-Puron, M. Miller and G. Pineda-Villavicencio <ins class="diffchange diffchange-inline">and independently by G. Araujo and N. López. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">|-</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">|style="background-color: pink; text-align: center;" | * || Graphs found by G. Araujo and N. López</ins>.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></center></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></center></div></td></tr>
</table>
Grahame
http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Bipartite_Graphs&diff=297&oldid=prev
Grahame: 1 revision imported
2019-01-03T14:39:32Z
<p>1 revision imported</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr class="diff-title" lang="en-GB">
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: #fff; color: #222; text-align: center;">Revision as of 14:39, 3 January 2019</td>
</tr><tr><td colspan="2" class="diff-notice" lang="en-GB"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>
Grahame
http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Bipartite_Graphs&diff=296&oldid=prev
CW>Gpineda: /* References */
2012-01-17T04:22:40Z
<p><span dir="auto"><span class="autocomment">References</span></span></p>
<p><b>New page</b></p><div>==Introduction==<br />
The '''degree/diameter problem for bipartite graphs''' can be stated as follows:<br />
<br />
''Given natural numbers ''d'' and ''k'', find the largest possible number ''N<sup>b</sup>(d,k)'' of vertices in a bipartite graph of maximum degree ''d'' and diameter ''k''.''<br />
<br />
An upper bound for ''N<sup>b</sup>(d,k)'' is given by the so-called ''bipartite Moore bound'' ''M<sup>b</sup>(d,k)=2((d-1)<sup>k</sup>-2)(d-2)<sup>-1</sup>''. Bipartite ''(d,k)''-graphs whose order attains the bipartite Moore bound are called ''bipartite Moore graphs''.<br />
<br />
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.<br />
<br />
Therefore, in attempting to settle the values of ''N<sup>b</sup>(d,k)'', research activities in this problem have follow the following two directions:<br />
<br />
*Increasing the lower bounds for ''N<sup>b</sup>(d,k)'' by constructing ever larger graphs.<br />
<br />
* Lowering and/or setting upper bounds for ''N<sup>b</sup>(d,k)'' by proving the non-existence of graphs<br />
whose order is close to the bipartite Moore bounds ''M<sup>b</sup>(d,k)=2((d-1)<sup>k</sup>-1)(d-2)<sup>-1</sup>''.<br />
<br />
==Increasing the lower bounds for ''N<sup>b</sup>(d,k)''==<br />
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&oacute;mez-Mart&iacute;) provided some large bipartite graphs by using graph compounding, the concept of partial Cayley graph, and other techniques. <br />
<br />
Now, with the release of this online table (see below), we expect to stimulate further research on this area.<br />
<br />
Below is the table of the largest known [http://en.wikipedia.org/wiki/Bipartite_graph bipartite] graphs (as of January 2012) in the undirected [[The Degree/Diameter Problem | degree diameter problem]] for bipartite graphs of [http://en.wikipedia.org/wiki/Degree_(graph_theory) degree] at most 3&nbsp;≤&nbsp;''d''&nbsp;≤&nbsp;16 and [http://en.wikipedia.org/wiki/Distance_(graph_theory) diameter] 3&nbsp;≤&nbsp;''k''&nbsp;≤&nbsp;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.<br />
<br />
===Table of the orders of the largest known bipartite graphs===<br />
<br />
<center> <br />
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"<br />
| '''<math>d</math>\<math>k</math>'''|| '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8''' || '''9''' || '''10''' <br />
|-<br />
| '''3''' ||style="background-color: #bbffff;" | '''14'''||style="background-color: #bbffff;" | '''30''' ||style="background-color: #0066CC;" | '''56''' ||style="background-color: #bbffff;" | '''126''' ||style="background-color: #993300;" | 168||style="background-color: #66ff66;" | 256||style="background-color: #FF9900;" | 506 || style="background-color: #66ff66;" | 800<br />
|-<br />
| '''4''' || style="background-color: #bbffff;" | '''26''' ||style="background-color: #bbffff;" | '''80''' || style="background-color: #ff0000;" | 160 ||style="background-color: #bbffff;" | '''728''' ||style="background-color: #ff0000;" | 840 ||style="background-color: #FF9900;" | 2 184 ||style="background-color: #FF9900;" | 4 970 ||style="background-color: #FF9900;" | 11 748 <br />
|-<br />
| '''5''' ||style="background-color: #bbffff;" | '''42''' ||style="background-color: #bbffff;" | '''170''' ||style="background-color: #FF9900;" | 336 ||style="background-color: #bbffff;" | '''2 730''' ||style="background-color: #FF9900;" | 3 110 ||style="background-color: #FF9900;" | 9 234 ||style="background-color: #FF9900;" | 27 936 ||style="background-color: #FF9900;" | 90 068 <br />
|-<br />
| '''6''' ||style="background-color: #bbffff;" | '''62''' ||style="background-color: #bbffff;" | '''312''' ||style="background-color: #FF9900;" | 684 ||style="background-color: #bbffff;" | '''7 812''' ||style="background-color: #66ff66;" | 8 310 ||style="background-color: #FF9900;" | 29 790 ||style="background-color: #FF9900;" | 117 360 ||style="background-color: #FF9900;" | 452 032 <br />
|- <br />
| '''7''' ||style="background-color: #ff0000;" | '''80''' ||style="background-color: #CC6600;" | 346 ||style="background-color: #FF9900;" | 1 134 ||style="background-color: #CC6600;" | 8 992 ||style="background-color: #66ff66;" | 23 436 ||style="background-color: #FF9900;" | 80 940 ||style="background-color: #FF9900;" | 400 160 ||style="background-color: #FF9900;" | 1 987 380 <br />
|- <br />
| '''8''' ||style="background-color: #bbffff;" | '''114''' ||style="background-color: #bbffff;" | '''800''' ||style="background-color: #FF9900;" | 1 710 ||style="background-color: #bbffff;" | '''39 216''' ||style="background-color: #66ff66;" | 40 586 ||style="background-color: #FF9900;" | 201 480 ||style="background-color: #FF9900;" | 1 091 232 ||style="background-color: #FF9900;" | 6 927 210 <br />
|- <br />
| '''9''' || style="background-color: #bbffff;" | '''146''' ||style="background-color: #bbffff;" | '''1 170''' ||style="background-color: #FF9900;" | 2 496 ||style="background-color: #bbffff;" | '''74 898''' ||style="background-color: #66ff66;" | 117 648 ||style="background-color: #FF9900;" | 449 480 ||style="background-color: #FF9900;" | 2 961 536 ||style="background-color: #FF9900;" | 20 017 260 <br />
|- <br />
| '''10''' || style="background-color: #bbffff;" | '''182''' ||style="background-color: #bbffff;" | '''1 640''' ||style="background-color: #66ff66;" | 4 000 ||style="background-color: #bbffff;" | '''132 860''' ||style="background-color: #66ff66;" | 224 694 ||style="background-color: #66ff66;" | 1 176 480 ||style="background-color: #FF9900;" | 7 057 400 ||style="background-color: #FF9900;" | 50 331 156 <br />
|- 97 386 380<br />
| '''11''' ||style="background-color: yellow;" | 190 || style="background-color: #CC6600;" | 1 734 ||style="background-color: #66ff66;" | 5 850 ||style="background-color: #CC6600;" | 142 464 ||style="background-color: #66ff66;" | 398 580 ||style="background-color: #66ff66;" | 2 246 940 || style="background-color: #FF9900;" | 15 200 448 ||style="background-color: #FF9900;" | 130 592 354<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|-<br />
| '''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<br />
|}<br />
</center><br />
<br />
The following table is the key to the colors in the table presented above:<br />
<br />
<center><br />
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"<br />
|'''Color''' || style="text-align: center;" |'''Details'''<br />
|-<br />
|style="background-color: #bbffff; text-align: center;" | * || Bipartite Moore graphs (optimal).<br />
|-<br />
|style="background-color: #CC6600; text-align: center;" | * || Graph duplications found by C. Delorme and G. Farhi.<br />
|-<br />
|style="background-color: #66ff66; text-align: center;" | * || Graphs found by C. Delorme, J. Gómez, and J. J. Quisquater.<br />
|-<br />
|style="background-color: #0066CC; text-align: center;" | * || Optimal graph found by R. Bar-Yehuda and T. Etzion and by J. Bond and C. Delorme.<br />
|-<br />
|style="background-color: #993300; text-align: center;" | * || Graph found independently by M. Conder and R. Nedela., by C. Delorme, J. Gómez, and J. J. Quisquater and by Eyal Loz.<br />
|-<br />
|style="background-color: #ff0000; text-align: center;" | * || Graphs found independently by Paul Hafner and by Eyal Loz. <br />
|-<br />
|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.<br />
|-<br />
|style="background-color: yellow; text-align: center;" | * || Graphs found by R. Feria-Puron, M. Miller and G. Pineda-Villavicencio. <br />
|}<br />
</center><br />
<br />
==Lowering and/or setting upper bounds for ''N<sup>b</sup>(d,k)''== <br />
<br />
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<sup>b</sup>(d,k)-&delta;'' for small ''&delta;''. The parameter ''&delta;'' is called the defect. Such graphs are called bipartite ''(d,k,-&delta;)''-graphs.<br />
<br />
The bipartite ''(d,k,-2;)''-graphs constitute the first interesting family of graphs to be studied. When ''d&ge;3'' and ''k=2'', bipartite ''(d,k,-2)''-graphs are the [http://en.wikipedia.org/wiki/Complete_bipartite_graph 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&ge;3'' and ''k&ge;3'' only two such graphs are known; a unique bipartite ''(3, 3,-2)''-graph and a unique bipartite ''(4, 3,-2)''-graph.<br />
<br />
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&ge;3'' and ''k&ge;3'', and the non-existence of bipartite ''(d,k,-2;)''-graphs for ''d&ge;3'' and ''k&ge;4''. <br />
<br />
===Lowest known upper bounds and the percentage of the order of the largest known bipartite graphs===<br />
<br />
<center><br />
{| border="1"<br />
| '''<math>d</math>\<math>k</math>'''|| '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8''' || '''9''' || '''10''' <br />
|-<br />
|'''3'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''14'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''30'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|'''56'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''126'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|248<br />
|-<br />
|67.74%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|504<br />
|-<br />
|50.79%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|1016<br />
|-<br />
|49.80%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|2040<br />
|-<br />
|39.21%<br />
|}<br />
|-<br />
|'''4'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''26'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''80'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|236<br />
|-<br />
|67.79%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''728'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|2180<br />
|-<br />
|38.53%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|6554<br />
|-<br />
|33.32%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|19676<br />
|-<br />
|25.25%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|59042<br />
|-<br />
|19.89%<br />
|}<br />
|-<br />
|'''5'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''42'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''170'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|676<br />
|-<br />
|49.70%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''2730'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|10916<br />
|-<br />
|28.49%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|43684<br />
|-<br />
|21.13%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|174756<br />
|-<br />
|15.98%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|699044<br />
|-<br />
|12.88%<br />
|}<br />
|-<br />
|'''6'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''62'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''312'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|1556<br />
|-<br />
|43.95%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''7812'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|39056<br />
|-<br />
|21.27%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|195306<br />
|-<br />
|15.25%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|976556<br />
|-<br />
|12.01%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|4882806<br />
|-<br />
|9.25%<br />
|}<br />
|-<br />
|'''7'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|'''80'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|518<br />
|-<br />
|66.79%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|3106<br />
|-<br />
|36.50%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|18662<br />
|-<br />
|48.18%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|111968<br />
|-<br />
|20.92%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|671840<br />
|-<br />
|12.04%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|4031072<br />
|-<br />
|9.92%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|24186464<br />
|-<br />
|8.21%<br />
|}<br />
|-<br />
|'''8'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''114'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''800'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|5596<br />
|-<br />
|30.55%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''39216'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|274508<br />
|-<br />
|14.78%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|1921594<br />
|-<br />
|10.48%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|13451196<br />
|-<br />
|8.11%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|94158410<br />
|-<br />
|7.35%<br />
|}<br />
|-<br />
|'''9'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''146'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''1170'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|9356<br />
|-<br />
|26.67%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''74898'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|599180<br />
|-<br />
|19.63%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|4793484<br />
|-<br />
|9.37%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|38347916<br />
|-<br />
|7.72%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|306783372<br />
|-<br />
|6.52%<br />
|}<br />
|-<br />
|'''10'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''182'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''1640'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|14756<br />
|-<br />
|27.10%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''132860'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|1195736<br />
|-<br />
|18.79%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|10761674<br />
|-<br />
|10.93%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|96855116<br />
|-<br />
|7.28%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|871696094<br />
|-<br />
|5.77%<br />
|}<br />
|-<br />
|'''11'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(100,100,255);" <br />
|220<br />
|-<br />
|86.36%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|2222<br />
|-<br />
|78.03%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|22216<br />
|-<br />
|26.33%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|222222<br />
|-<br />
|64.10%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|2222216<br />
|-<br />
|17.93%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|22222216<br />
|-<br />
|10.11%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|222222216<br />
|-<br />
|6.84%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|2222222216<br />
|-<br />
|5.87%<br />
|}<br />
|-<br />
|'''12'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''266'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''2928'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|32204<br />
|-<br />
|25.46%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''354312'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|3897428<br />
|-<br />
|17.04%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|42871770<br />
|-<br />
|10.84%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|471589532<br />
|-<br />
|6.36%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|5187484914<br />
|-<br />
|5.79%<br />
|}<br />
|-<br />
|'''13'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|314<br />
|-<br />
|85.98%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|3770<br />
|-<br />
|81.27%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|45236<br />
|-<br />
|25.37%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|542906<br />
|-<br />
|68.97%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|6514868<br />
|-<br />
|16.31%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|78178484<br />
|-<br />
|6.79%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|938141876<br />
|-<br />
|5.43%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|11257702580<br />
|-<br />
|5.48%<br />
|}<br />
|-<br />
|'''14'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''366'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''4760'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|61876<br />
|-<br />
|23.85%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|'''804468'''<br />
|-<br />
|100%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|10458080<br />
|-<br />
|16.93%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|135955114<br />
|-<br />
|10.42%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|1767416556<br />
|-<br />
|5.38%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|22976415302<br />
|-<br />
|5.28%<br />
|}<br />
|-<br />
|'''15'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|422<br />
|-<br />
|87.67%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|5910<br />
|-<br />
|83.68%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|82736<br />
|-<br />
|24.77%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|1158390<br />
|-<br />
|72.69%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|16217456<br />
|-<br />
|15.29%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|227044464<br />
|-<br />
|0%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|3178622576<br />
|-<br />
|5.28%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|44500716144<br />
|-<br />
|5.17%<br />
|}<br />
|-<br />
|'''16'''<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|482<br />
|-<br />
|81.74%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|7232<br />
|-<br />
|70.99%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|108476<br />
|-<br />
|25.16%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(40,40,255);" <br />
|1627232<br />
|-<br />
|54.32%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|24408476<br />
|-<br />
|16.47%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|366127226<br />
|-<br />
|9.88%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|5491908476<br />
|-<br />
|5.26%<br />
|}<br />
| align="center" |<br />
{| border="2" style="background:rgb(210,210,255);" <br />
|82378627226<br />
|-<br />
|5%<br />
|}<br />
|}<br />
</center><br />
<br />
<br />
The following table is the key to the colors in the table presented above:<br />
<br />
<center><br />
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"<br />
|'''Color''' || style="text-align: center;" |'''Details'''<br />
|-<br />
|style="background-color: rgb(40,40,255); text-align: center;" | * || Moore bound.<br />
|-<br />
|style="background-color: rgb(100,100,255); text-align: center;" | * || Moore bound minus 2.<br />
|-<br />
|style="background-color: rgb(210,210,255); text-align: center;" | * || Moore bound minus 6. <br />
|-<br />
|}<br />
</center><br />
<br />
==References==<br />
* Conder, M.; Nedela, R. (2006), "A more detailed classification of symmetric cubic graphs", preprint.<br />
* Bar-Yehuda, R.; Etzion, T. (1992), "Connections between two cycles - a new design of dense processor interconnection networks", Discrete Applied Mathematics 37-38.<br />
* Bond, J.; Delorme, C. (1988), "New large bipartite graphs with given degree and diameter", Ars Combinatoria 25C: 123-132.<br />
* 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.<br />
* Delorme, C. (1985), "Grands graphes de degr&eacute; et diam&egrave;tre donn&eacute;s", European Journal of Combinatorics 6: 291-302.<br />
* Delorme, C. (1985), "Large bipartite graphs with given degree and diameter", Journal of Graph Theory 8: 325-334.<br />
* Delorme, C.; Farhi, G. (1984), "Large graphs with given degree and diameter Part I", IEEE Transactions on Computers C-33: 857-860.<br />
* Delorme, C.; G&oacute;mez (2002), "Some new large compound graphs", European Journal of Combinatorics 23 (5): 539-547, doi:10.1006/eujc.2002.0581.<br />
* Delorme, C.; Gómez, J.; Quisquater, J. J., "On large bipartite graphs", submitted.<br />
* 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.<br />
* 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.<br />
*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.<br />
* Miller, M.; Širáň, J. (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey D, [http://www.combinatorics.org/Surveys/ds14.pdf PDF version].<br />
<br />
==External links==<br />
* [http://www.eyal.com.au/wiki/The_Degree/Diameter_Problem 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''.<br />
<br />
<br />
<br />
<br />
<br />
[[Category:The Degree/Diameter Problem]]</div>
CW>Gpineda