کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4602749 1336936 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Primitive digraphs with smallest large exponent
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
Primitive digraphs with smallest large exponent
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 428, Issue 7, 1 April 2008, Pages 1740-1752