双向2重迹与图的最大亏格

Abstract

Abstract:

Let G be a connected graph and L be a bidirectional double tracing of G. The authors first introduce a new invarint of G, which is called the retracing number and denoted by ε(G). The definition of ε(G) is given as follows: ε(G)=min〖DD(X〗L〖DD)〗 ε(G, L), where ε(G, L) is the number of retracings in L, and the minimum ranges over all bidirectional double tracings of G. Then, for a connected 3regular graph G the authors prove that ε(G) is closely related to the maximum genus γ\-M(G) of G, namely ε(G), equals to the value 2γ\-M(G)-β(G) where β(G) is the rank number of G. Also the authors provide an instructural characterization on thegraph G according to the value ε(G). Thus these may be viewed as some generalizations of Thomassen C's results.

Key words: Bidirectional double tracing, Retracing number, Betti , deficiency number, Upper embeddable, Maximum genus

CLC Number:

05C75

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.

Trendmd

[1]	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.
[2]	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.
[3]	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.
[4]	Hyang Yuangqiu, Liu Yanpei. SOME CLASSES OF UPPER EMBEDDABLE GRAPHS [J]. Acta mathematica scientia,Series A, 1997, 17(S1): 154-161.

Bidirectional Double Tracings and Maximum Genus

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 4

Metrics

Comments

Recommended 10