论文标题
稀疏随机图中的大麻的条件，具有固定度序列
A condition for Hamiltonicity in Sparse Random Graphs with a Fixed Degree Sequence
论文作者
论文摘要
我们考虑随机图$ g_ {n，{\ bf d}} $从所有图的集合中随机选择的所有图表均以给定的稀疏度序列$ {\ bf d} $。我们假设$ {\ bf d} $至少具有至少4个，最多只能是电源法，并在其尾巴上再放置一个条件。对于$ k \ ge 2 $定义$β_K（g）= \ max e（a，b） + k（| a | - | b |） - d（a）$，最大值取得了discoint discoint vertex sets $ a，b $。结果表明，确定$ g_ {n，{\ bf d}} $是否包含汉密尔顿周期的问题减少到计算$β_2（g_ {n，{\ bf d}}）$。如果$ k \ ge 2 $和$δ\ ge k+2 $，则确定$ g_ {n，{\ bf d}} $是否包含一个$ k $ -factor降低到计算$β_K（g_ {n，{n，{\ bf d}}）$的问题。
We consider the random graph $G_{n, {\bf d}}$ chosen uniformly at random from the set of all graphs with a given sparse degree sequence ${\bf d}$. We assume ${\bf d}$ has minimum degree at least 4, at most a power law tail, and place one more condition on its tail. For $k\ge 2$ define $β_k(G) = \max e(A, B) + k(|A|-|B|) - d(A)$, with the maximum taken over disjoint vertex sets $A, B$. It is shown that the problem of determining if $G_{n, {\bf d}}$ contains a Hamilton cycle reduces to calculating $β_2(G_{n, {\bf d}})$. If $k\ge 2$ and $δ\ge k+2$, the problem of determining if $G_{n, {\bf d}}$ contains a $k$-factor reduces to calculating $β_k(G_{n, {\bf d}})$.
