Non-existence of bipartite graphs of diameter at least 4 and defect 2
Guillermo Pineda-Villavicencio
DOI: 10.1007/s10801-010-0266-0
Abstract
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.
Pages: 163–182
Keywords: keywords degree/diameter problem; Moore bipartite bound; Moore bipartite graphs; defect; dickson polynomials of the second kind
Full Text: PDF
References
1. Bannai, E., Ito, T.: On finite Moore graphs. J. Math. Sci., Univ. Tokyo 20, 191-208 (1973)
2. Bannai, E., Ito, T.: Regular graphs with excess one. Discrete Math. 37, 147-158 (1981).
3. Benson, C.T.: Minimal regular graphs of girth eight and twelve. Can. J. Math. 18, 1091-1094 (1966)
4. Biggs, N.L.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)
5. Biggs, N.L., Ito, T.: Graphs with even girth and small excess. Math. Proc. Camb. Philos. Soc. 88(1), 1-10 (1980)
6. Dally, W.J., Towles, B.P.: Principles and Practices of Interconnection Networks. Morgan Kaufmann, San Francisco (2004)
7. Delorme, C., Jørgensen, L.K., Miller, M., Pineda-Villavicencio, G.: On bipartite graphs of defect
2. Eur. J. Comb. 30(4), 798-808 (2009)
8. Delorme, C., Jørgensen, L.K., Miller, M., Pineda-Villavicencio, G.: On bipartite graphs of diameter 3 and defect
2. J. Graph Theory 61(4), 271-288 (2009)
9. Duato, J., Yalamanchili, S., Ni, L.: Interconnection Networks: An Engineering Approach. Morgan Kaufmann, San Francisco (2003). Revised printing ed.
10. Feit, W., Higman, G.: The nonexistence of certain generalized polygons. J. Algebra 1, 114-131 (1964).
11. Godsil, C.D., McKay, B.D.: Feasibility conditions for the existence of walk-regular graphs. Linear Algebra Appl. 30, 51-61 (1980)
12. Heydemann, M.C.: Cayley graphs and interconnection networks. In: Graph Symmetry: Algebraic Methods and Applications. NATO ASI Series, Series C: Mathematical and Physical Sciences, vol.
497. Kluwer Academic, Dordrecht (1996)
13. Jørgensen, L.K.: Nonexistence of certain cubic graphs with small diameters. Discrete Math. 114, 265-273 (1993).
14. Lidl, R., Mullen, G.L., Turnwald, G.: Dickson Polynomials. Pitman Monographs and Surveys in Pure and Applied Mathematics, vol.
65. Logman, London (1993)
15. Miller, M., Širá\check n, J.: Moore graphs and beyond: A survey of the degree/diameter problem. Electron. J. Comb. 1-61 (2005). Dynamic survey DS14
16. Pineda-Villavicencio, G.: Topology of interconnection networks with given degree and diameter. PhD Thesis, School of Information Technology and Mathematical Sciences, University of Ballarat, Ballarat, Australia, Dec
2009. J Algebr Comb (2011) 34:163-182
17. Singleton, R.C.: On minimal graphs of maximum even girth. J. Comb. Theory 1(3), 306-332 (1966).
2. Bannai, E., Ito, T.: Regular graphs with excess one. Discrete Math. 37, 147-158 (1981).
3. Benson, C.T.: Minimal regular graphs of girth eight and twelve. Can. J. Math. 18, 1091-1094 (1966)
4. Biggs, N.L.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)
5. Biggs, N.L., Ito, T.: Graphs with even girth and small excess. Math. Proc. Camb. Philos. Soc. 88(1), 1-10 (1980)
6. Dally, W.J., Towles, B.P.: Principles and Practices of Interconnection Networks. Morgan Kaufmann, San Francisco (2004)
7. Delorme, C., Jørgensen, L.K., Miller, M., Pineda-Villavicencio, G.: On bipartite graphs of defect
2. Eur. J. Comb. 30(4), 798-808 (2009)
8. Delorme, C., Jørgensen, L.K., Miller, M., Pineda-Villavicencio, G.: On bipartite graphs of diameter 3 and defect
2. J. Graph Theory 61(4), 271-288 (2009)
9. Duato, J., Yalamanchili, S., Ni, L.: Interconnection Networks: An Engineering Approach. Morgan Kaufmann, San Francisco (2003). Revised printing ed.
10. Feit, W., Higman, G.: The nonexistence of certain generalized polygons. J. Algebra 1, 114-131 (1964).
11. Godsil, C.D., McKay, B.D.: Feasibility conditions for the existence of walk-regular graphs. Linear Algebra Appl. 30, 51-61 (1980)
12. Heydemann, M.C.: Cayley graphs and interconnection networks. In: Graph Symmetry: Algebraic Methods and Applications. NATO ASI Series, Series C: Mathematical and Physical Sciences, vol.
497. Kluwer Academic, Dordrecht (1996)
13. Jørgensen, L.K.: Nonexistence of certain cubic graphs with small diameters. Discrete Math. 114, 265-273 (1993).
14. Lidl, R., Mullen, G.L., Turnwald, G.: Dickson Polynomials. Pitman Monographs and Surveys in Pure and Applied Mathematics, vol.
65. Logman, London (1993)
15. Miller, M., Širá\check n, J.: Moore graphs and beyond: A survey of the degree/diameter problem. Electron. J. Comb. 1-61 (2005). Dynamic survey DS14
16. Pineda-Villavicencio, G.: Topology of interconnection networks with given degree and diameter. PhD Thesis, School of Information Technology and Mathematical Sciences, University of Ballarat, Ballarat, Australia, Dec
2009. J Algebr Comb (2011) 34:163-182
17. Singleton, R.C.: On minimal graphs of maximum even girth. J. Comb. Theory 1(3), 306-332 (1966).
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition