TRANSITION GRAPHS OF ITERATIONS OF INITIAL (2, 2)-AUTOMATA

Автор(и)

  • V. М. Skochko

DOI:

https://doi.org/10.24144/2616-7700.2017.2(31).129-136

Анотація

The iterations of an automaton A naturally produces a sequence of nite graphs GA(n) which describe the transitions in A(n) = A ◦ A ◦ . . . ◦ A (n times). We consider combinatorial properties of the graphs GA(n) for initial invertible automata with two states over the binary alphabet. We compute the chromatic number and girth of the graphs GA(n) and show that all of them are imbalance graphic.

Посилання

  1. Albertson M. O. The irregularity of a graph // Ars Comb. 46. – 1997. – 46. – P. 219-225
  2. Bartholdi, L., Grigorchuk, R. On the spectrum of Hecke type operators related to some fractal groups // Proc. Steklov Inst. Math. – 2000. – 231. – P. 1–41.
  3. Bondarenko I. Growth of Schreier graphs of automaton groups // Math. Ann. – 2012. – 354.– P. 765–785.
  4. Bondarenko I., D’Angeli D., Nagnibeda T. Ends of Schreier graphs and cut-points of limit spaces of self-similar groups // Journal of Fractal Geometry – 2017. – Number 4. – P. 369-424.
  5. Grigorchuk R.I., Linnell P., Schick T., Zuk A. On a question of Atiyah // C. R. Acad. Sci. Paris S´er. I Math. – 2000. — 331, N9. – P. 663–668.
  6. Grigorchuk R., Nekrashevych V., Sushchanskii V. Automata, dynamical systems and groups // Tr. Mat. Inst. Steklova – 2000. – 231. – P. 134–214.
  7. Harary, F. Graph Theory — Boston: Addison-Wesley, 1969
  8. Kozerenko S., Skochko V. On graphs with graphic imbalance sequences // Algebra Discrete Math. – 2014. – 18, 1. – P. 97–108.
  9. Nekrashevych, V. Self-similar groups — Mathematical Surveys and Monographs, vol.117, American Mathematical Society, Providence, 2005.
  10. Skochko V. The growth function of initial invertible 2-state automata over a binary alphabet
  11. // Bulletin of Taras Shevchenko National University of Kyiv. Series Physics & Mathematics – 2017. – 2. – P. 9–14.

##submission.downloads##

Опубліковано

2017-12-21

Як цитувати

Skochko V. М. (2017). TRANSITION GRAPHS OF ITERATIONS OF INITIAL (2, 2)-AUTOMATA. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 2(31), 129–136. https://doi.org/10.24144/2616-7700.2017.2(31).129-136

Номер

Том 2 № 31 (2017)

Розділ

Статті

Ліцензія

Авторське право (c) 2019 V. М. Skochko

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.