Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4602733 | Linear Algebra and its Applications | 2008 | 13 Pages |
Abstract
A 2-coloring (G1,G2) of a digraph is 2-primitive if there exist nonnegative integers h and k with h+k>0 such that for each ordered pair (u,v) of vertices there exists an (h,k)-walk in (G1,G2) from u to v. The exponent of (G1,G2) is the minimum value of h+k taken over all such h and k. In this paper, we consider 2-colorings of strongly connected symmetric digraphs with loops, establish necessary and sufficient conditions for these to be 2-primitive and determine an upper bound on their exponents. We also characterize the 2-colored digraphs that attain the upper bound and the exponent set for this family of digraphs on n vertices.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory