论文标题
循环性，可连接性和周长
Cyclability, Connectivity and Circumference
论文作者
论文摘要
在图$ g $中，如果有一个循环包含某种顺序的周期，则据说顶点$ s \ subseteq v（g）$的子集可自行车。如果$ k \ geq 2 $顶点是可行的，则$ g $ te $ k $ cyclable。如果任何$ k $ \ textit {ordered}的顶点以该顺序存在一个共同的周期，则该图被称为$ k $ ordore。我们表明，当$ k \ leq \ sqrt {n+3} $，$ k $ -creclable图也具有圆周$ c（g）\ geq 2k $，这是最好的。此外，当$ k \ leq \ frac {3n} {4} -1 $，$ c（g）\ geq k+2 $，对于$ k $订购的图形，我们显示$ c（g）\ geq \ geq \ min \ min \ {n，2k \ \} $。我们还概括了Byer等人的结果。在Nonhamiltonian $ k $连接的图中的最大边缘数，并表明如果$ g $是$ k $连接的订单$ n \ geq 2（k^2+k）$，则使用$ | e（g）| > \ binom {n-k} {2} + k^2 $，然后该图为汉密尔顿，而且极端图是唯一的。
In a graph $G$, a subset of vertices $S \subseteq V(G)$ is said to be cyclable if there is a cycle containing the vertices in some order. $G$ is said to be $k$-cyclable if any subset of $k \geq 2$ vertices is cyclable. If any $k$ \textit{ordered} vertices are present in a common cycle in that order, then the graph is said to be $k$-ordered. We show that when $k \leq \sqrt{n+3}$, $k$-cyclable graphs also have circumference $c(G) \geq 2k$, and that this is best possible. Furthermore when $k \leq \frac{3n}{4} -1$, $c(G) \geq k+2$, and for $k$-ordered graphs we show $c(G) \geq \min\{n,2k\}$. We also generalize a result by Byer et al. on the maximum number of edges in nonhamiltonian $k$-connected graphs, and show that if $G$ is a $k$-connected graph of order $n \geq 2(k^2+k)$ with $|E(G)| > \binom{n-k}{2} + k^2$, then the graph is hamiltonian, and moreover the extremal graphs are unique.
