ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • On orders of automorphisms of vertex-transitive graphs
    Potočnik, Primož, 1971- ; Toledo, Micael, matematik ; Verret, Gabriel
    In this paper we investigate orders, longest cycles and the number of cycles of automorphisms of finite vertex-transitive graphs. In particular, we show that the order of every automorphism of a ... connected vertex-transitive graph with ▫$n$▫ vertices and of valence ▫$d$▫, ▫$d\le 4$▫, is at most ▫$c_d n$▫ where ▫$c_3=1$▫ and ▫$c_4 = 9$▫. Whether such a constant ▫$c_d$▫ exists for valencies larger than ▫$4$▫ remains an unanswered question. Further, we prove that every automorphism ▫$g$▫ of a finite connected ▫$3$▫-valent vertex-transitive graph ▫$\Gamma$▫, ▫$\Gamma \not\cong K_{3,3}$▫, has a regular orbit, that is, an orbit of ▫$\langle g \rangle$▫ of length equal to the order of ▫$g$▫. Moreover, we prove that in this case either ▫$\Gamma$▫ belongs to a well understood family of exceptional graphs or at least ▫$5/12$▫ of the vertices of ▫$\Gamma$▫ belong to a regular orbit of ▫$g$▫. Finally, we give an upper bound on the number of orbits of a cyclic group of automorphisms ▫$C$▫ of a connected ▫$3$▫-valent vertex-transitive graph ▫$\Gamma$▫ in terms of the number of vertices of ▫$\Gamma$▫ and the length of a longest orbit of ▫$C$▫.
    Source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 166, May 2024, str. 123-153)
    Type of material - article, component part ; adult, serious
    Publish date - 2024
    Language - english
    COBISS.SI-ID - 182607619

    Link(s):

    https://www.sciencedirect.com/science/article/pii/S0095895624000029
    DiRROS - Digital repository of Slovenian research organizations
    Repository of the University of Ljubljana – RUL
    DOI

Shelf entry