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.

Bibliographie

[1] Salii V. N., “Fault tolerance and optimization of discrete systems with specified index and period”, Vestnik TSU. Prilozhenie, 2006, no. 17, 222–225 (in Russian)

[2] Chaudhuri R., Mukherdjea A., “Idempotent Boolean matrices”, Semigroup Forum, 21 (1980), 273–282 | DOI | MR | Zbl

[3] Maximov A. A., Salii V. N., “Indices and periods of fuzzy matrices and graphs”, Theoretical Problems of Computer Science and its Applications, 7, Saratov Univ. Press, Saratov, 2006, 87–95 (in Russian)

[4] Maximov A. A., On the Index and Period of a Fuzzy Matrix, Dep. v VINITI 20.01.05, no. 78-V2005, Saratov, 2005, 11 pp. (in Russian)

[5] Bar-Gnar R. I., Fomichev V. M., “On minimal primitive matrices”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2014, no. 7, 7–9 (in Russian)

[6] Miller W., “The maximum order of an element of a finite symmetric group”, Amer. Math. Monthly, 94 (1987), 497–506 | DOI | MR | Zbl

[7] Barbosa V. C., An Atlas of Edge-Reversal Dynamics, Chapman/CRC, London, 2001, 385 pp. | MR | Zbl

[8] Salii V. N., “A class of finite dynamical systems”, Vestnik TSU. Prilozhenie, 2005, no. 14, 23–26 (in Russian)

[9] Vlasova A. V., “Indices in dynamical system $(B,\delta)$ of binary vectors”, Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 11:3, pt. 1 (2011), 116–122 (in Russian)

[10] Zharkova A. V., “Indices in dynamic system of binary vectors associated with cycles orientations”, Prikladnaya Diskretnaya Matematika, 2012, no. 2(16), 79–85 (in Russian)

[11] Zharkova A. V., “Indices of states in dynamical system of binary vectors associated with palms orientations”, Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 16:4 (2016), 475–484 (in Russian) | DOI | MR | Zbl

[12] Salii V. N., “Minimal primitive extensions of oriented graphs”, Prikladnaya Diskretnaya Matematika, 2008, no. 1, 116–119 (in Russian)