A family of mixed graphs with large order and diameter 2

详细信息    查看全文

• 作者：G. Araujo-Pardo^a ; ^{garaujo@matem.unam.mx} ; C. Balbuena^b ; ^{m.camino.balbuena@upc.edu} ; M. Miller¹ ; M. Ždí ; malová ; ^c ; ^{zdimalova@math.sk}
• 关键词：Mixed Moore graphs ; Projective planes
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：19 February 2017
• 年：2017
• 卷：218
• 期：Complete
• 页码：57-63
• 全文大小：433 K
• 卷排序：218

文摘

A mixed regular graph is a connected simple graph in which each vertex has both a fixed outdegree (the same indegree) and a fixed undirected degree. A mixed regular graphs is said to be optimal if there is not a mixed regular graph with the same parameters and bigger order.We present a construction that provides mixed graphs of undirected degree qq, directed degree q−12 and order 2q22q2, for qq being an odd prime power. Since the Moore bound for a mixed graph with these parameters is equal to 9q2−4q+34 the defect of these mixed graphs is (q−22)2−14.In particular we obtain a known mixed Moore graph of order 1818, undirected degree 33 and directed degree 11 called Bosák’s graph and a new mixed graph of order 5050, undirected degree 55 and directed degree 22, which is proved to be optimal.