A construction of dense mixed graphs of diameter 2

详细信息    查看全文

• 作者：C. Araujo-Pardo¹ ; ^{garaujo@math.unam.mx" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Mixed Moore graphs ; projective planes
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：54
• 期：Complete
• 页码：235-240
• 全文大小：195 K

文摘

A mixed graph is said to be dense, if its order is close to the Moore bound and it is optimal if there is not a mixed graph with the same parameters and bigger order. We give a construction that provides dense mixed graphs of undirected degree q  , directed degree w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301354&_mathId=si1.gif&_user=111111111&_pii=S1571065316301354&_rdoc=1&_issn=15710653&md5=755f38e09a7be7aab645b8dd69268f9a">width="26" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S1571065316301354-si1.gif"> and order w the MathML source">2q², for q   being an odd prime power. Since the Moore bound for a mixed graph with these parameters is equal to w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301354&_mathId=si3.gif&_user=111111111&_pii=S1571065316301354&_rdoc=1&_issn=15710653&md5=931af666d4e6565952fa132367c784ab">width="60" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S1571065316301354-si3.gif"> the defect of these mixed graphs is w the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316301354&_mathId=si4.gif&_user=111111111&_pii=S1571065316301354&_rdoc=1&_issn=15710653&md5=c578804538c6f63925541c956f57e065">width="74" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S1571065316301354-si4.gif">. In particular we obtain a known mixed Moore graph of order 18, undirected degree 3 and directed degree 1, called Bosák's graph and a new mixed graph of order 50, undirected degree 5 and directed degree 2, which is proved to be optimal.