On diregular digraphs with degree two and excess two

DOI10.1016/J.DAM.2017.10.034zbMATH Open1380.05091arXiv1705.00075OpenAlexW2611943276MaRDI QIDQ1701129FDOQ1701129

Authors: James Tuite 

Publication date: 22 February 2018

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

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.

Full work available at URL: https://arxiv.org/abs/1705.00075

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

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)

Cites Work

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

Cited In (8)

• On diregular digraphs with degree two and excess three
• On digraphs of excess one
• Title not available (Why is that?)
• 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)