Minimum order of loop networks of given degree and girth
type: Item
instance of: scholarly article
title: Minimum order of loop networks of given degree and girth
zbMATH Open document ID: 0824.05029
DOI: 10.1007/BF01929482
author: Yahya Ould Hamidoune
author: Oriol Serra
author: Anna Lladó
published in: Graphs and Combinatorics
publication date: 1995-11-09T00:00:00Z
review text: Behzad, Chartrand and Wall proposed the conjecture that any regular directed graph of degree \(r\) and girth \(g\) has order \(n\geq r(g- 1)+ 1\). The main result is the following theorem: Let \(X= \text{Cay}(G, S)\) be a connected Abelian Cayley digraph with girth \(g> 3\), degree \(r\), and order \(n\). Then \(n\geq (r+ 1)(g- 1)- 1\) unless \(X\) is a lexicographic product of a family of Cayley digraphs on \(\text{Z}_{n_ i}\), \(1\geq i\geq k\), defined by subsets of the form \(\{x: 1\geq x\geq s_ i\}\), where \(0\geq s_ i\geq n_ i\) and \(n= n_ 1\cdots n_ k\). This bound is best possible.
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 784142
zbMATH Keywords: loop networks
zbMATH Keywords: girth
zbMATH Keywords: Cayley digraph
zbMATH Keywords: bound
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
cites work: Short cycles in directed graphs
cites work: An application of connectivity theory in graphs to factorizations of elements in groups
cites work: On the connectivity of Cayley digraphs
cites work: Q4121925
cites work: Vosperian and superconnected abelian Cayley digraphs
cites work: On small sumsets in an abelian group
cites work: Short cycles in digraphs
cites work: On the Addition of Elements of a Sequence
description: scientific article; zbMATH DE number 784142