主题
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 定理

使用 探索

参考文献

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.

在 中引用

Ore 图

请引用为

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

主题分类