On diregular digraphs with degree two and excess two

DOI10.1016/J.DAM.2017.10.034MaRDI QIDQ1701129zbMATH OpenOpenAlexFDO

Authors James Tuite

Publication date 22 February 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.00075, http://oro.open.ac.uk/52980/13/52980.pdf

zbMATH Keywords

digraphsdegree/diameter problemextremal digraphsexcess

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Distance in graphs (05C12)

Abstract: An important topic in the design of efficient networks is the construction of $(d,k,+epsilon)$-digraphs, i.e. $k$-geodetic digraphs with minimum out-degree $geqd$ and order $M(d,k)+epsilon$, where $M(d,k)$ represents the Moore bound for degree $d$ and diameter $k$ and $epsilon>0$ is the (small) excess of the digraph. Previous work has shown that there are no $(2,k,+1)$-digraphs for $kgeq2$. In a separate paper, the present author has shown that any $(2,k,+2)$-digraph must be diregular for $kgeq2$. In the present work, this analysis is completed by proving the nonexistence of diregular $(2,k,+2)$-digraphs for $kgeq3$ and classifying diregular $(2,2,+2)$-digraphs up to isomorphism.

Recommendations

• On diregular digraphs with degree two and excess three
• Digraphs with degree two and excess two are diregular
• On digraphs of excess one
• On diregularity of digraphs of defect at most two
• On \(k\)-geodetic digraphs with excess one

Cites work

• Digraphs of degree two which miss the Moore bound by two
• Digraphs with degree two and excess two are diregular
• Moore graphs and beyond: a survey of the degree/diameter problem
• On \(k\)-geodetic digraphs with excess one
• On digraphs of excess one
• On the impossibility of directed Moore graphs

Cited in

(8)

• On diregular digraphs with degree two and excess three
• On digraphs of excess one
• scientific article; zbMATH DE number 91052 (Why is no real title available?)
• The structure of digraphs with excess one
• Minimum Diameter of Diregular Digraphs of Degree 2
• Turán problems for \(k\)-geodetic digraphs
• Digraphs with degree two and excess two are diregular
• On \(k\)-geodetic digraphs with excess one

This page was built for publication: On diregular digraphs with degree two and excess two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1701129)