Radial Moore graphs of radius three

详细信息    查看全文

• 作者：Geoffrey Exoo^a ; ^{ge@cs.indstate.edu} ; ^{geoffrey.exoo@gmail.com} ; Joan Gimbert^b ; ^{joangim@matematica.udl.cat} ; Nacho Ló ; pez^b ; ^{nlopez@matematica.udl.cat} ; José ; Gó ; mez^c ; ^{jgomez@ma4.upc.edu}
• 关键词：de Bruijn graph ; Moore bound ; Radial Moore graph ; Radius
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 出版时间：July, 2012
• 年：2012
• 卷：160
• 期：10-11
• 页码：1507-1512
• 全文大小：308 K

文摘

The maximum number of vertices in a graph of specified degree and diameter cannot exceed the Moore bound. Graphs achieving this bound are called Moore graphs. Because Moore graphs are so rare, researchers have considered various relaxations of the Moore graph constraints. Since the diameter of a Moore graph is equal to its radius, one can consider graphs in which the condition on the diameter is relaxed, by one, while the condition on the radius is maintained. Such graphs are called radial Moore graphs. It has previously been shown that radial Moore graphs exist for all degrees when the radius is two. In this paper, we extend this result to radius three. We also construct examples that settle the existence question for a few new cases, and summarize the state of knowledge on the problem.