图的生成树, 基本圈与Betti亏数

Abstract

Abstract:

Let \$G\$ be a graph and \$T\$ be a spanning tree of it. The sign \$ξ(G, T)\$ denotes thenumber of components of \$G＼E(T)\$ with odd number of edges, and it is knownthat the value \$ξ(G)=min[DD(X]T[DD)]ξ(G, T)\$ is defined as Betti deficiency of \$G\$, where min is taken over all spanning trees of \$G\$. In this paper the authors study the characteristic structure of a graph conne ting to its Betti deficiency, and obtain some
new results on the maximum genus of a graph.

Key words: Spanning tree, Betti Deficiency, Upper Embeddability, Maximum Genus

CLC Number:

HUANG Yuan-Qiu, LIU Pan-Pei. Spanning Trees, Basic Cycles and Betti Deficiency of a Graph[J].Acta mathematica scientia,Series A, 2004, 24(4): 496-500.

Trendmd

[1]	Chen Dong; Wang Weifan. The Numbers of Spanning Trees in Some Graphs [J]. Acta mathematica scientia,Series A, 2008, 28(5): 906-913.
[2]	Huang Yuanqiu ;Tang Ling ;Liu Yanpei. Maximum Genus of Graphs Embedded in the Klein Bottle [J]. Acta mathematica scientia,Series A, 2008, 28(3): 403-411.
[3]	HUANG Yuan-Qiu, DIAO Ting-Lei. On the Maximum Genus of an Embedded Graph [J]. Acta mathematica scientia,Series A, 2005, 25(3): 362-366.
[4]	HUANG Yuan-Qiu, LIU Pan-Pei, CHU Yu-Meng. Bidirectional Double Tracings and Maximum Genus [J]. Acta mathematica scientia,Series A, 2004, 4(5): 530-536.
[5]	CHEN Xie-Ban. The Numbers of Spanning Trees in the Cartesian ProductGraphs of Paths or Cycles [J]. Acta mathematica scientia,Series A, 2003, 23(1): 70-76.
[6]	Hyang Yuangqiu, Liu Yanpei. SOME CLASSES OF UPPER EMBEDDABLE GRAPHS [J]. Acta mathematica scientia,Series A, 1997, 17(S1): 154-161.

Spanning Trees, Basic Cycles and Betti Deficiency of a Graph

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 6

Metrics

Comments

Recommended 10