Loading [MathJax]/jax/output/SVG/jax.js

ISSN 0253-2778

CN 34-1054/N

open
Open AccessOpen Access JUSTC Mathematics Article 12 May 2022

Pancyclicity of randomly perturbed digraph

Cite this: JUSTC, 2022, 52(5): 2
https://doi.org/10.52396/JUSTC-2021-0208
CSTR: 32290.14.JUSTC-2021-0208
Funds: The study was supported by the National Natural Science Foundation of China (12071453) and the National Key R&D Program of China (2020YFA0713100).
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:

    Xinmin Hou, E-mail: xmhou@ustc.edu.cn

  • Received Date: September 17, 2021
  • Accepted Date: January 30, 2022
  • Available Online: May 12, 2022
  • Dirac’s theorem states that if a graph G on n vertices has a minimum degree of at least n2, then G contains a Hamiltonian cycle. Bohman et al. introduced the random perturbed graph model and proved that for any constant α>0 and a graph H with a minimum degree of at least αn, there exists a constant C depending on α such that for any pCn, HGn,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 α=ω((lognn)14) and d{1,2}, the union of a digraph on n vertices with a minimum degree of at least α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.

    • 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.

Catalog

    {{if article.pdfAccess}}
    {{if article.articleBusiness.pdfLink && article.articleBusiness.pdfLink != ''}} {{else}} {{/if}}PDF
    {{/if}}
    XML
    [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 (333) PDF downloads (1512)

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return