|国家预印本平台
首页|Colorful Hamilton cycles in random graphs

Colorful Hamilton cycles in random graphs

Colorful Hamilton cycles in random graphs

来源:Arxiv_logoArxiv
英文摘要

Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C=\{c_1,c_2,\ldots,c_r\}$, we define the Hamilton cycle color profile $hcp(G)$ to be the set of vectors $(m_1,m_2,\ldots,m_r)\in [0,n]^r$ such that there exists a Hamilton cycle that is the concatenation of $r$ paths $P_1,P_2,\ldots,P_r$, where $P_i$ contains $m_i$ edges of color $c_i$. We study $hcp(G_{n,p})$ when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when $hcp(G_{n,p})=\{(m_1,m_2,\ldots,m_r)\in [0,n]^r: m_1+m_2+\cdots+m_r=n\}$.

Mihir Hasabnis、Alan Frieze、Debsoumya Chakraborti

10.1137/21M1403291

数学

Mihir Hasabnis,Alan Frieze,Debsoumya Chakraborti.Colorful Hamilton cycles in random graphs[EB/OL].(2021-03-05)[2025-08-02].https://arxiv.org/abs/2103.03916.点此复制

评论