Periods of p-raphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 41. DOI: 10.17223/20710410/41/5

A connected graph with n ^ 3 vertices obtained from the circuit C_n by reorienting some of its arcs is called a polygonal graph. We consider a bijection р between the set of sinks and the set of sources of a polygonal graph G. We attach to G all arcs of type vр(v) where v is a sink. The resulting strongly connected graph is called a р-graph. When we compute successive powers of a binary Boolean matrix A, the sequence starts to repeat itself at some moment, i.e. we get A^m+1 = A¹ for some l ^ m. The number ind(A) = l - 1 is called an index, and the value p(A) = ((m + 1) - l) is the period of the matrix A. For the graph G with adjacency matrix A, let ind(G) = ind(A) and p(G) = p(A) (index and period of the graph). We calculate the values of periods of all not isomorphic р-graphs with a number of vertices up to nine and the maximal periods of р-graphs with a number of vertices up to seventeen. We prove the theorem that allows to compute the period of any p-graph. Namely, the period of a p-graph is equal to the greatest common divisor of the lengths of its circuits. The value of the maximal period for n-vertex p-graph with even n equals n/2 + 1, and the maximal period of a p-graph with an odd n is less than |_n/2j +1. From the theorem for the maximal values of the periods, we obtain some corollaries. Particularly, according to Corollary 1, among the all n-vertex p-graphs with even n, p-graphs obtained from the polygonal graphs with one sink and one source have the maximal period.