排序方式: 共有3条查询结果,搜索用时 0 毫秒
1
1.
探索Euler生成子图边数的一种方法 总被引:4,自引:0,他引:4
关于超欧拉图的欧拉生成子图(spanning eulerian subgraph)的边数问题,P,A.Catlin、HongJian Lai、Zhi-Hong Chen等人提出若干问题。本文给出了探索超欧拉图的欧拉生成子图边数的一种方法。 相似文献
2.
Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch-bonds of G are got. 相似文献
3.
《国际计算机数学杂志》2012,89(8):1662-1672
Motivated by the Chinese Postman Problem, Boesch, Suffel, and Tindell [The spanning subgraphs of Eulerian graphs, J. Graph Theory 1 (1977), pp. 79–84] proposed the supereulerian graph problem which seeks the characterization of graphs with a spanning Eulerian subgraph. Pulleyblank [A note on graphs spanned by Eulerian graphs, J. Graph Theory 3 (1979), pp. 309–310] showed that the supereulerian problem, even within planar graphs, is NP-complete. In this paper, we settle an open problem raised by An and Xiong on characterization of supereulerian graphs with small matching numbers. A well-known theorem by Chvátal and Erdös [A note on Hamilton circuits, Discrete Math. 2 (1972), pp. 111–135] states that if G satisfies α(G)≤κ(G), then G is hamiltonian. Flandrin and Li in 1989 showed that every 3-connected claw-free graph G with α(G)≤2 κ(G) is hamiltonian. Our characterization is also applied to show that every 2-connected claw-free graph G with α(G)≤3 is hamiltonian, with only one well-characterized exceptional class. 相似文献
1