On Networks with Order Close to the Moore Bound

The degree/diameter problem for mixed graphs asks for the largest possible order of a mixed graph with given diameter and degree parameters. Similarly the degree/geodecity problem concerns the smallest order of a k -geodetic mixed graph with given minimum undirected and directed degrees; this is a g...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2022-10, Vol.38 (5), Article 143
Main Authors: Tuite, James, Erskine, Grahame
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The degree/diameter problem for mixed graphs asks for the largest possible order of a mixed graph with given diameter and degree parameters. Similarly the degree/geodecity problem concerns the smallest order of a k -geodetic mixed graph with given minimum undirected and directed degrees; this is a generalisation of the classical degree/girth problem. In this paper we present new bounds on the order of mixed graphs with given diameter or geodetic girth and exhibit new examples of directed and mixed geodetic cages. In particular, we show that any k -geodetic mixed graph with excess one must have geodetic girth two and be totally regular, thereby proving an earlier conjecture of the authors.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-022-02535-6