ISSN 0253-2778

CN 34-1054/N

Open AccessOpen Access JUSTC Mathematics 13 May 2022

Pancyclicity of randomly perturbed digraph

Funds:  The study was supported by the National Natural Science Foundation of China (12071453) and the National Key R&D Program of China (2020YFA0713100).
Cite this:
https://doi.org/10.52396/JUSTC-2021-0208
More Information
  • Author Bio:

    Zelin Ren is currently a master student under the supervision of Prof. Xinmin Hou at the University of Science and Technology of China. His research mainly focuses on random graphs

    Xinmin Hou received his Ph.D. from Dalian University of Technology. He is currently a Professor at the University of Science and Technology of China. His research interests focus on graph theory, combinatorial optimization and cyberspace security

  • Corresponding author: E-mail: xmhou@ustc.edu.cn
  • Received Date: 18 September 2021
  • Accepted Date: 31 January 2022
  • Available Online: 13 May 2022
  • Dirac’s theorem states that if a graph G on n vertices has a minimum degree of at least $\displaystyle \frac{n}{2}$, then G contains a Hamiltonian cycle. Bohman et al. introduced the random perturbed graph model and proved that for any constant $ \alpha > 0 $ and a graph H with a minimum degree of at least $ \alpha n $, there exists a constant C depending on α such that for any $p \geqslant \dfrac{C}{n}$, $H \cup {G_{n,p}}$ is asymptotically almost surely (a.a.s.) Hamiltonian. In this study, the random perturbed digraph model is considered, and we show that for all $\alpha = \omega \left( {{{\left( {\dfrac{{\log n}}{n}} \right)}^{{\textstyle{1 \over 4}}}}} \right)$ and $d \in \{ 1,2\}$, the union of a digraph on n vertices with a minimum degree of at least $ \alpha n $ and a random d-regular digraph on n vertices is a.a.s. pancyclic. Moreover, a polynomial-time algorithm is proposed to find cycles of any length in such a digraph.
    Minimum degree conditons on Hamilton cycles.
    Dirac’s theorem states that if a graph G on n vertices has a minimum degree of at least $\displaystyle \frac{n}{2}$, then G contains a Hamiltonian cycle. Bohman et al. introduced the random perturbed graph model and proved that for any constant $ \alpha > 0 $ and a graph H with a minimum degree of at least $ \alpha n $, there exists a constant C depending on α such that for any $p \geqslant \dfrac{C}{n}$, $H \cup {G_{n,p}}$ is asymptotically almost surely (a.a.s.) Hamiltonian. In this study, the random perturbed digraph model is considered, and we show that for all $\alpha = \omega \left( {{{\left( {\dfrac{{\log n}}{n}} \right)}^{{\textstyle{1 \over 4}}}}} \right)$ and $d \in \{ 1,2\}$, the union of a digraph on n vertices with a minimum degree of at least $ \alpha n $ and a random d-regular digraph on n vertices is a.a.s. pancyclic. Moreover, a polynomial-time algorithm is proposed to find cycles of any length in such a digraph.
    • If the minimal degree condition is satisfied, then by perturbing the digraph with a random 1-regular graph, the resulting digraph is a.a.s. pancyclic.
    • Moreover, we give a polynomial algorithm to find cycles of all possible lengths in such perturbed digraph.

  • loading
  • [1]
    Dirac G A. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 1952, s3-2 (1): 69–81. doi: 10.1112/plms/s3-2.1.69
    [2]
    Korsunov A D. Solution of a problem of Erdös and Rényi on Hamiltonian cycles in undirected graphs. Metody Diskret. Analiz., 1977, 31: 17–56.
    [3]
    Bohman T, Frieze A, Martin R. How many random edges make a dense graph Hamiltonian? Random Structures Algorithms, 2003, 22 (1): 33–42. doi: 10.1002/rsa.10070
    [4]
    Krivelevich M, Kwan M, Sudakov B. Cycles and matchings in randomly perturbed digraphs and hypergraphs. Combinatorics, Probability and Computing, 2016, 25 (6): 909–927. doi: 10.1017/S0963548316000079
    [5]
    Hahn-Klimroth M, Maesaka G S, Mogge Y, et al. Random perturbation of sparse graphs. The Electronic Journal of Combinatorics, 2021, 28 (2): P2.26. doi: 10.37236/9510
    [6]
    Bedenknecht W, Han J, Kohayakawa Y, et al. Powers of tight Hamilton cycles in randomly perturbed hypergraphs. Random Structures & Algorithms, 2019, 55 (4): 795–807. doi: 10.1002/rsa.20885
    [7]
    Han J, Zhao Y. Hamiltonicity in randomly perturbed hypergraphs. Journal of Combinatorial Theory, Series B, 2020, 144: 14–31. doi: 10.1016/j.jctb.2019.12.005
    [8]
    Chang Y L, Han J, Thoma L. On powers of tight Hamilton cycles in randomly perturbed hypergraphs. https://doi.org/10.48550/ arXiv.2007.11775.
    [9]
    Condon P, Espuny Díaz A, Girão A, et al. Hamiltonicity of random subgraphs of the hypercube. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Philadelphia, PA: SIAM, 2021.
    [10]
    Dudek A, Reiher C, Ruciński A, et al. Powers of Hamiltonian cycles in randomly augmented graphs. Random Structures & Algorithms, 2020, 56 (1): 122–141. doi: 10.1002/rsa.20870
    [11]
    Böttcher J, Montgomery R, Parczyk O, et al. Embedding spanning bounded degree graphs in randomly perturbed graphs. Mathematika, 2020, 66 (2): 422–447. doi: 10.1112/mtk.12005
    [12]
    Balogh J, Treglown A, Wagner A Z. Tilings in randomly perturbed dense graphs. Combinatorics, Probability and Computing, 2019, 28 (2): 159–176. doi: 10.1017/S0963548318000366
    [13]
    Han J, Morris P, Treglown A. Tilings in randomly perturbed graphs: Bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu. Random Structures & Algorithms, 2021, 58 (3): 480–516. doi: 10.1002/rsa.20981
    [14]
    Espuny Díaz A, Girão A, Hamiltonicity of graphs perturbed by a random regular graph. https://doi.org/10.48550/arXiv.2101.06689.
    [15]
    Cooper C, Frieze A, Molloy M. Hamilton cycles in random regular digraphs. Combinatorics, Probability and Computing, 1994, 3 (1): 39–49. doi: 10.1017/S096354830000095X
    [16]
    Bollobás B. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1980, 1 (4): 311–316. doi: 10.1016/S0195-6698(80)80030-8
    [17]
    Wormald N C. Models of random regular graphs. In: Surveys in Combinatorics. Cambridge, UK: Cambridge University Press, 1999.
  • 加载中

Catalog

    [1]
    Dirac G A. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 1952, s3-2 (1): 69–81. doi: 10.1112/plms/s3-2.1.69
    [2]
    Korsunov A D. Solution of a problem of Erdös and Rényi on Hamiltonian cycles in undirected graphs. Metody Diskret. Analiz., 1977, 31: 17–56.
    [3]
    Bohman T, Frieze A, Martin R. How many random edges make a dense graph Hamiltonian? Random Structures Algorithms, 2003, 22 (1): 33–42. doi: 10.1002/rsa.10070
    [4]
    Krivelevich M, Kwan M, Sudakov B. Cycles and matchings in randomly perturbed digraphs and hypergraphs. Combinatorics, Probability and Computing, 2016, 25 (6): 909–927. doi: 10.1017/S0963548316000079
    [5]
    Hahn-Klimroth M, Maesaka G S, Mogge Y, et al. Random perturbation of sparse graphs. The Electronic Journal of Combinatorics, 2021, 28 (2): P2.26. doi: 10.37236/9510
    [6]
    Bedenknecht W, Han J, Kohayakawa Y, et al. Powers of tight Hamilton cycles in randomly perturbed hypergraphs. Random Structures & Algorithms, 2019, 55 (4): 795–807. doi: 10.1002/rsa.20885
    [7]
    Han J, Zhao Y. Hamiltonicity in randomly perturbed hypergraphs. Journal of Combinatorial Theory, Series B, 2020, 144: 14–31. doi: 10.1016/j.jctb.2019.12.005
    [8]
    Chang Y L, Han J, Thoma L. On powers of tight Hamilton cycles in randomly perturbed hypergraphs. https://doi.org/10.48550/ arXiv.2007.11775.
    [9]
    Condon P, Espuny Díaz A, Girão A, et al. Hamiltonicity of random subgraphs of the hypercube. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Philadelphia, PA: SIAM, 2021.
    [10]
    Dudek A, Reiher C, Ruciński A, et al. Powers of Hamiltonian cycles in randomly augmented graphs. Random Structures & Algorithms, 2020, 56 (1): 122–141. doi: 10.1002/rsa.20870
    [11]
    Böttcher J, Montgomery R, Parczyk O, et al. Embedding spanning bounded degree graphs in randomly perturbed graphs. Mathematika, 2020, 66 (2): 422–447. doi: 10.1112/mtk.12005
    [12]
    Balogh J, Treglown A, Wagner A Z. Tilings in randomly perturbed dense graphs. Combinatorics, Probability and Computing, 2019, 28 (2): 159–176. doi: 10.1017/S0963548318000366
    [13]
    Han J, Morris P, Treglown A. Tilings in randomly perturbed graphs: Bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu. Random Structures & Algorithms, 2021, 58 (3): 480–516. doi: 10.1002/rsa.20981
    [14]
    Espuny Díaz A, Girão A, Hamiltonicity of graphs perturbed by a random regular graph. https://doi.org/10.48550/arXiv.2101.06689.
    [15]
    Cooper C, Frieze A, Molloy M. Hamilton cycles in random regular digraphs. Combinatorics, Probability and Computing, 1994, 3 (1): 39–49. doi: 10.1017/S096354830000095X
    [16]
    Bollobás B. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1980, 1 (4): 311–316. doi: 10.1016/S0195-6698(80)80030-8
    [17]
    Wormald N C. Models of random regular graphs. In: Surveys in Combinatorics. Cambridge, UK: Cambridge University Press, 1999.

    Article Metrics

    Article views (285) PDF downloads(1409)
    Proportional views

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return