Non existence of some mixed Moore graphs of diameter 2 using SAT

详细信息    查看全文

• 作者：Nacho Ló ; pez^a ; ^{nlopez@matematica.udl.es" class="auth_mail" title="E-mail the corresponding author} ; Josep M. Miret^a ; ^{miret@matematica.udl.es" class="auth_mail" title="E-mail the corresponding author} ; Cè ; sar Ferná ; ndez^b ; ^{cesar@diei.udl.cat" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Moore bound ; Mixed Moore graph ; Directed strongly regular graph ; Satisfiability problem
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：589-596
• 全文大小：960 K

文摘

Mixed graphs with maximum number of vertices regarding to a given maximum degree and given diameter are known as mixed Moore graphs. In this paper we model the problem of the existence of mixed Moore graphs of diameter 2 through the Boolean satisfiability problem. As a consequence, we prove the non existence of mixed Moore graphs of order 40, 54 and 84.