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 w the MathML source">d is at most e251bcbc46ea4185b" title="Click to view the MathML source">d²+1. The number w the MathML source">d²+1 is the Moore bound for diameter two. Let w the MathML source">C(d,2) denote the largest order of a Cayley graph of degree w the MathML source">d and diameter two. Up to now, the only known construction of Cayley graphs of diameter two valid for all degrees w the MathML source">d is a construction giving w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14001656&_mathId=si8.gif&_user=111111111&_pii=S0166218X14001656&_rdoc=1&_issn=0166218X&md5=c06b2acb754c243f4ee0afe30ac1a706">width="123" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X14001656-si8.gif">. However, there is a construction yielding Cayley graphs of diameter two, degree w the MathML source">d and order w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14001656&_mathId=si10.gif&_user=111111111&_pii=S0166218X14001656&_rdoc=1&_issn=0166218X&md5=3cd020832c496a7f6052f3c641b397e7">width="75" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X14001656-si10.gif"> for an infinite set of degrees w the MathML source">d of a special type.

In this article we present, for any integer w the MathML source">d≥4, a construction of Cayley graphs of diameter two, degree w the MathML source">d and of order w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14001656&_mathId=si14.gif&_user=111111111&_pii=S0166218X14001656&_rdoc=1&_issn=0166218X&md5=26e54ccde171017a38c5d806587fdb2f">width="51" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X14001656-si14.gif"> for w the MathML source">d even and of order w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14001656&_mathId=si16.gif&_user=111111111&_pii=S0166218X14001656&_rdoc=1&_issn=0166218X&md5=32b5941c0202abcd8d38715746738478">width="91" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X14001656-si16.gif"> for w the MathML source">d odd, where w the MathML source">0≤t≤8 is an integer depending on the congruence class of w the MathML source">d modulo 8.

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