Primitive digraphs with smallest large exponent |
| |
Authors: | G MacGillivray S Nasserasr P van den Driessche |
| |
Institution: | a Department of Mathematics and Statistics, University of Victoria, Victoria, British Columbia, Canada V8W 3P4 b Department of Computer Science, University of Victoria, Victoria, British Columbia, Canada V8W 3P6 |
| |
Abstract: | A primitive digraph D on n vertices has large exponent if its exponent, γ(D), satisfies αn?γ(D)?wn, where αn=⌊wn/2⌋+2 and wn=(n-1)2+1. It is shown that the minimum number of arcs in a primitive digraph D on n?5 vertices with exponent equal to αn is either n+1 or n+2. Explicit constructions are given for fixed n even and odd, for a primitive digraph on n vertices with exponent αn and n+2 arcs. These constructions extend to digraphs with some exponents between αn and wn. A necessary and sufficient condition is presented for the existence of a primitive digraph on n vertices with exponent αn and n+1 arcs. Together with some number theoretic results, this gives an algorithm that determines for fixed n whether the minimum number of arcs is n+1 or n+2. |
| |
Keywords: | 05C20 05C50 |
本文献已被 ScienceDirect 等数据库收录! |
|