Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Infinite families of vertex-transitive graphs with prescribed hamilton compression
    Kutnar, Klavdija, 1980- ; Marušič, Dragan ; Razafimahatratra, Andriaherimanana Sarobidy
    Given a graph ▫$X$▫ with a Hamilton cycle ▫$C$▫, the {\em compression factor ▫$\kappa(X,C)$▫ of ▫$C$▫} is the order of the largest cyclic subgroup of ▫$\Aut(C)\cap\Aut(X)$▫, and the {\em Hamilton ... compression ▫$\kappa(X)$▫ of ▫$X$▫ } is the maximum of ▫$\kappa(X,C)$▫ where ▫$C$▫ runs over all Hamilton cycles in ▫$X$▫. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor, Merino and M\"utze in [``The Hamilton compression of highly symmetric graphs'', {\em arXiv preprint} \href{https://arxiv.org/abs/2205.08126}{arXiv: 2205.08126v1} (2022)] whether for every positive integer ▫$k$▫ there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to ▫$k$▫. Since an infinite family of Cayley graphs with Hamilton compression equal to ▫$1$▫ was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products ▫$\mathbb Z_p\rtimes\mathbb Z_k$▫ where ▫$p$▫ is a prime and ▫$k \geq 2$▫ a divisor of ▫$p-1$▫. Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to ▫$1$▫ are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given.
    Vir: Annals of combinatorics. - ISSN 0218-0006 (2024, str. 1-13)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2024
    Jezik - angleški
    COBISS.SI-ID - 199602947

    Povezava(-e):

    https://link.springer.com/article/10.1007/s00026-024-00703-4
    https://doi.org/10.1007/s00026-024-00703-4
    DOI

Vnos na polico