On the upper generalized exponents of ministrong digraphs (Q5949536)
From MaRDI portal
scientific article; zbMATH DE number 1675987
Language | Label | Description | Also known as |
---|---|---|---|
English | On the upper generalized exponents of ministrong digraphs |
scientific article; zbMATH DE number 1675987 |
Statements
On the upper generalized exponents of ministrong digraphs (English)
0 references
28 August 2002
0 references
A digraph \(G\) is primitive if there exists a positive integer \(k\) such that there is a walk of length \(k\) from \(u\) to \(v\) for each ordered pair of not necessarily distinct nodes \(u\) and \(v\). The smallest such \(k\) is called the exponent of \(G\). A strong digraph \(D\) is ministrong or minimally strong if each digraph obtained from \(D\) by the removal of an arc is not strong. The set of all \(k\)-upper primitive ministrong digraphs of order \(n\) is denoted by \(U(n,k)\). The paper gives the maximum values for the \(k\)th upper generalized exponents of digraphs in \(U(n,k)\) with \(1\leq k\leq n\) and of the non-primitive digraphs in \(U(n,k)\) with \(2\leq k\leq n\), and characterizes completely the extreme digraphs, i.e., those digraphs whose \(k\)th upper generalized exponents achieve the corresponding maximum values.
0 references
ministrong digraphs
0 references
generalized exponents
0 references
extreme digraphs
0 references
0 references