Cayley graphs of diameter two and any degree with order half of the Moore bound

详细信息    查看全文

• 作者：Marcel Abas ; ^{abas@stuba.sk" class="auth_mail}
• 关键词：Degree ; Diameter ; Moore bound ; Cayley graph
• 刊名：Discrete Applied Mathematics
• 出版年：20 August 2014
• 年：2014
• 卷：173
• 期：Complete
• 页码：1-7
• 全文大小：378 K

文摘

It is well known that the number of vertices of a graph of diameter two and maximum degree X14001656&_mathId=si2.gif&_user=111111111&_pii=S0166218X14001656&_rdoc=1&_issn=0166218X&md5=b2fe643221eb1589062fd8f36940e833" title="Click to view the MathML source">dmi>dmi> is at most d²+1mi>dmi>2+1. The number d²+1mi>dmi>2+1 is the Moore bound for diameter two. Let C(d,2)mi>Cmi>(<mi>dmi>,2) denote the largest order of a Cayley graph of degree dmi>dmi> and diameter two. Up to now, the only known construction of Cayley graphs of diameter two valid for all degrees dmi>dmi> is a construction giving mi>Cmi>(<mi>dmi>,2)>14<mi>dmi>2+<mi>dmi>. However, there is a construction yielding Cayley graphs of diameter two, degree dmi>dmi> and order mi>dmi>2&minus;<mi>Omi>(<mi>dmi>32) for an infinite set of degrees dmi>dmi> of a special type.

In this article we present, for any integer d≥4mi>dmi>≥4, a construction of Cayley graphs of diameter two, degree dmi>dmi> and of order mi>dmi>2&minus;<mi>tmi> for dmi>dmi> even and of order mi>dmi>2+<mi>dmi>)&minus;<mi>tmi> for dmi>dmi> odd, where 0≤t≤8mi>tmi>≤8 is an integer depending on the congruence class of 142a520413123926a63110233f4" title="Click to view the MathML source">dmi>dmi> modulo 8.

In addition, we show that, in asymptotic sense, the most of record Cayley graphs of diameter two is obtained by our construction.