主题
Search

Ore 图


Ore 图是满足 Ore 定理,即图 G 使得对于所有非邻接顶点的子集,非邻接顶点的度数之和大于或等于节点数 n。令 V(G)顶点集E(G)G边集,令 |V(G)| 表示 G顶点计数,用 d(v) 表示顶点 v顶点度,用 (u,v) 表示一对顶点。那么,图 G 为 Ore 图的条件可以写成

 (u,v) not in E(G)=>d(u)+d(v)>=|V(G)|

(Ore 1960;Bondy 1971)。请注意,Skiena(1990,第 197 页)和 Pemmaraju 与 Skiena(2003,第 301 页)陈述了此结果的较弱版本,将“大于或等于”替换为“大于”。

OreGraphs

Ore 定理指出,Ore 图始终是哈密顿图。此外,对于此类图,可以在多项式时间内构造哈密顿环(Bondy 和 Chvátal 1976;Skiena 1990,第 197 页)。满足 Ore 准则(使用“空真”约定,因此包括完全图 K_n)的 n=1, 2, ... 个图的数量为 1, 1, 1, 3, 5, 21, 68, 503, 4942, 128361, ... (OEIS A264683),其中前几个图示如上所示。

HamiltonianNonOreGraph

每个满足 Ore 准则的图都是哈密顿图,但并非每个哈密顿图都满足该准则。不满足 Ore 准则的 n=1, 2, ... 个顶点的简单哈密顿图的数量为 0, 0, 0, 0, 3, 27, 315, 5693, 172141, 9176757, ... (OEIS A264684),其中前几个图示如上所示。


另请参阅

哈密顿环, 哈密顿图, Ore 定理

使用 Wolfram|Alpha 探索

参考文献

Bondy, J. A. "Pancyclic Graphs I." J. Combin. Th. 11, 80-84, 1971.Bondy, J. A. and Chvátal, V. "A Method in Graph Theory." Disc. Math. 15, 111-136, 1976.Meyniel, M. "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté." J. Combin. Th. 14, 137-147, 1973.Ore, O. "A Note on Hamiltonian Circuits." Amer. Math. Monthly 67, 55, 1960.Palmer, E. M. "The Hidden Algorithm of Ore's Theorem on Hamiltonian Cycles." Computers Math. Appl. 34, 113-119, 1997.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences A264683 and A264684 in "The On-Line Encyclopedia of Integer Sequences."Woodall, D. R. "Sufficient Conditions for Circuits in Graphs." Proc. London Math. Soc. 24: 739-755, 1972.

在 Wolfram|Alpha 中引用

Ore 图

请引用为

Weisstein, Eric W. "Ore 图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/OreGraph.html

主题分类