DIAMETER OF THE DIRECT PRODUCT OF WIELANDT GRAPH
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A digraph D is primitive if there is a positive integer k such that there is a walk of length k between arbitrary two vertices of D. The exponent of a primitive digraph is the least such k. Wielandt graph Wn of order n is known as the digraph whose exponent is n2 - 2n + 2, which is the maximum of all the exponents of the primitive digraphs of order n. It is known that the diameter of the multiple direct product of a digraph Wn strictly increases according to the multiplicity of the product. And it stops when it attains to the exponent of Wn . In this paper, we nd the diameter of the direct product of Wielandt graphs.
Abstract
A digraph D is primitive if there is a positive integer k such that there is a walk of length k between arbitrary two vertices of D. The exponent of a primitive digraph is the least such k. Wielandt graph Wn of order n is known as the digraph whose exponent is n2 - 2n + 2, which is the maximum of all the exponents of the primitive digraphs of order n. It is known that the diameter of the multiple direct product of a digraph Wn strictly increases according to the multiplicity of the product. And it stops when it attains to the exponent of Wn . In this paper, we nd the diameter of the direct product of Wielandt graphs.
참고문헌 (7)
- 황운재, "The exponent of a digraph and the diameter of its multiple direct product", LINEAR ALGEBRA AND ITS APPLICATIONS, 437(10), pp.2601~2612, ELSEVIER SCIENCE INC
- R. Lamprey, "Primitivity of products of digraphs", Proc.10th Southeastern Conf. on Combinatorics, pp.637~644 (1979)
- M. McAndrew, "On the product of directed graphs", Proc. Amer. Math. Soc, 14, pp.101~108 (1963)
- J. Moon, "On the diameter of a graph", Michigan Math. J, 12, pp.349~351 (1965)
- H. Schneider, "Wielandt's proof of the exponent inequality for primitive non- negative matrices", Linear Algebra Appl, 353, pp.5~10 (2002)
- P. Weischel, "The Kronecker product of graphs", Proc. Amer. Math. Soc, 12, pp.47~52 (1962)
- H. Wielandt, "Unzerleghare, nicht negative Matrizen", Math. Z, 52, pp.642~645 (1950)