Periods of $\varphi$-graphs
Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 46-53

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: polygonal graph, primitivity, $\varphi$-graph, index and period of graph.
@article{PDM_2018_3_a4,
     author = {N. A. Artemova},
     title = {Periods of $\varphi$-graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {46--53},
     publisher = {mathdoc},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_3_a4/}
}
TY  - JOUR
AU  - N. A. Artemova
TI  - Periods of $\varphi$-graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 46
EP  - 53
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_3_a4/
LA  - ru
ID  - PDM_2018_3_a4
ER  - 
%0 Journal Article
%A N. A. Artemova
%T Periods of $\varphi$-graphs
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 46-53
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_3_a4/
%G ru
%F PDM_2018_3_a4
N. A. Artemova. Periods of $\varphi$-graphs. Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 46-53. http://geodesic.mathdoc.fr/item/PDM_2018_3_a4/