Exponents of 2-coloring of symmetric digraphs |
| |
Authors: | Yanling Shao Yubin Gao |
| |
Institution: | Department of Mathematics, North University of China, Taiyuan, Shanxi 030051, PR China |
| |
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. |
| |
Keywords: | 15A18 05C15 |
本文献已被 ScienceDirect 等数据库收录! |
|