ON EXPONENTS OF PRIMITIVE GRAPHS

Saib Suwilo

ICMSA
Vol 1, No 1 (2005): ICMSA 2005

A connected gaph G is primitive provided there exists a positive integerk such that for each pair of vertices u and v in G there is a walk of lengtht that connects u and v. The smallest of such positive integers k is calledthe exponent of G and is denoted by exp(G). In this paper, we give a newbound on exponent of primitive graphs G in terms of the length of thesmallest cycle of G. We show that the new bound is sharp andgeneralizes the bounds given by Shao and Liu et. al.Keywords: primitive graphs; exponents.