Periods of $\varphi$-graphs

N. A. Artemova

Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 46-53

Résumé

A connected graph with $n\ge3$ vertices obtained from the circuit $C_n$ by reorienting some of its arcs is called a polygonal graph. We consider a bijection $\varphi$ between the set of sinks and the set of sources of a polygonal graph $G$. We attach to $G$ all arcs of type $v\varphi(v)$ where $v$ is a sink. The resulting strongly connected graph is called a $\varphi$-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^l$ for some $l\le m$. The number $\mathrm{ind}(A)=l-1$ is called an index, and the value $\mathrm p(A)=((m+1)-l)$ is the period of the matrix $A$. For the graph $G$ with adjacency matrix $A$, let $\mathrm{ind}(G)=\mathrm{ind}(A)$ and $\mathrm p(G)=\mathrm p(A)$ (index and period of the graph). We calculate the values of periods of all not isomorphic $\varphi$-graphs with a number of vertices up to nine and the maximal periods of $\varphi$-graphs with a number of vertices up to seventeen. We prove the theorem that allows to compute the period of any $\varphi$-graph. Namely, the period of a $\varphi$-graph is equal to the greatest common divisor of the lengths of its circuits. The value of the maximal period for $n$-vertex $\varphi$-graph with even $n$ equals $n/2+1$, and the maximal period of a $\varphi$-graph with an odd $n$ is less than $\lfloor n/2\rfloor+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 $\varphi$-graphs with even $n$, $\varphi$-graphs obtained from the polygonal graphs with one sink and one source have the maximal period.

Détail

Keywords: polygonal graph, primitivity, $\varphi$-graph, index and period of graph.