×

Minimum order of loop networks of given degree and girth. (English) Zbl 0824.05029

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.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C35 Extremal problems in graph theory
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI

References:

[1] Cacceta, L., Häggkvist, R.: On minimal digraphs of given girth, Proc. of the Ninth Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg 181–187 (1978)
[2] Chvatál, V., Szemerédi, E.: Short Cycles in Directed Graphs. J. Comb. Theory, Ser. B35, 323–327 (1983) · Zbl 0545.05038 · doi:10.1016/0095-8956(83)90059-X
[3] Hamidoune, Y.O.: An application of connectivity theory in graphs to factorization of elements in groups. Europ. J. Comb.2, 349–355 (1981) · Zbl 0473.05032
[4] Hamidoune, Y.O.: On the connectivity of Cayley graphs. Europ. J. Comb.5, 309–312 (1984) · Zbl 0561.05028
[5] Hamidoune, Y.O.: Sur les atomes d’un graphe orienté. C.R. Acad. Sc. Paris A 1253–1256 (1977) · Zbl 0352.05035
[6] Hamidoune, Y.O., Llado, A.S., Serra, O.: Vosperian and superconnected Abelian Cayley digraphs. Graphs and Combinatorics7, 143–152 (1991) · Zbl 0736.05047 · doi:10.1007/BF01788139
[7] Kemperman, J.H.B.: On small sums in abelian groups. Acta Math.103, 63–88 (1960) · Zbl 0108.25704 · doi:10.1007/BF02546525
[8] Nishimura, T.: Short Cycles in Digraphs. Discrete Math.72, 295–298 (1988) · Zbl 0659.05049 · doi:10.1016/0012-365X(88)90219-1
[9] Shepherdson, J.C.: On the addition of elements of a subsequence. J. Lond. Math. Soc.22, 85–88 (1947) · Zbl 0029.34402 · doi:10.1112/jlms/s1-22.2.85
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.