RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2015 Issue 8, Pages 113–114 (Mi pdma202)

This article is cited in 2 papers

Applied Theory of Coding, Automata and Graphs

Primitiveness conditions for systems of two graphs

Y. E. Avezovaa, V. M. Fomichevbc

a National Engineering Physics Institute "MEPhI", Moscow
b Financial University under the Government of the Russian Federation, Moscow
c "Security Code", Moscow

Abstract: Some sufficient conditions for primitiveness of two $n$-vertex digraphs system are obtained in the case when there are no acyclic vertices in one of this two graphs, particularly when it contains a Hamiltonian cycle. Also, an exponent estimate for the two digraphs system is obtained in terms of the exponent of their product. The results can be used for evaluation of the mixing properties of iterative functions based on the transformation branching into two given transformations.

Keywords: primitive graph, exponent of graph, Hamiltonian cycle.

UDC: 519.6

DOI: 10.17223/2226308X/8/43



© Steklov Math. Inst. of RAS, 2024