The Moore Bound for Irregular Graphs |
| |
| Authors: | Noga Alon Shlomo Hoory Nathan Linial |
| |
| Institution: | (1) Mathematics and Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. e-mail: noga@math.tau.ac.il, IL;(2) Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel e-mail: shlomoh@cs.huji.ac.il, IL;(3) Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel e-mail: nati@cs.huji.ac.il, IL |
| |
| Abstract: | What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover irregular
graphs as well, yielding an affirmative answer to an old open problem (4] p. 163, problem 10).
Received: June 27, 2000 Final version received: July 3, 2001 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
