Exponents of 2-regular digraphs

DOI10.1016/S0012-365X(99)00144-2MaRDI QIDQ1972142zbMATH OpenOpenAlexWikidataFDO

Authors J. Shen

Publication date 23 October 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00144-2

zbMATH Keywords

exponentprimitive digraphwalk

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

Review text

A digraph \(G\) is said to be primitive if for some positive integer \(k\), there is a walk of length exactly \(k\) from each vertex \(u\) to each vertex \(v\). The smallest such \(k\) in a primitive digraph \(G\) is called the exponent of \(G\). If each vertex of \(G\) has out-degree and in-degree exactly \(r\), then \(G\) is said to be \(r\)-regular. The paper shows that if \(G\) is a primitive 2-regular digraph with \(n\) vertices, then its exponent is not greater than \((n-1)^2/4+ 1\).

Recommendations

• Exponents of a class of two-colored digraphs
• Exponents of a class of two-colored digraphs
• Exponents of two-colored digraphs consisting of two cycles
• The generalized exponent of two primitive digraphs
• Exponents of two-colored digraphs with two cycles
• Exponents of a class of two-colored digraphs with two cycles
• Exponents of two-colored digraphs
• scientific article; zbMATH DE number 6178721
• On the exponents of two-colored digraphs with two cycles†
• On the exponent of a primitive digraph

Cited in

(6)

• Lower bounds for the length of reset words in Eulerian automata
• The vertex exponent of primitive digraph of order n with girth r
• scientific article; zbMATH DE number 1216570 (Why is no real title available?)
• scientific article; zbMATH DE number 1998287 (Why is no real title available?)
• On 2-regular graphs whose girth is one less than the maximum
• scientific article; zbMATH DE number 7488135 (Why is no real title available?)

This page was built for publication: Exponents of 2-regular digraphs

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