Up-embeddability of a graph by order and girth

被引：10

作者：

Chen, Yichao ^{[1
]}

Liu, Yanpei

机构：

[1] Cent S Univ, Sch Biol Sci & Technol, Changsha 410083, Peoples R China

[2] Beijing Jiao Tong Univ, Dept Math, Beijing 100044, Peoples R China

来源：

GRAPHS AND COMBINATORICS | 2007年 / 23卷 / 05期

关键词：

Maximum genus; order; Girth; Up-Embeddable; MAXIMUM GENUS;

D O I：

10.1007/s00373-007-0746-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a connected graph of order n and girth g. If d(G)(u) + d(G)(v) >= n-2g+5 for any two non-adjacent vertices u and v, then G is up-embeddable. Further more, the lower bound is best possible. Similarly the result of k-edge connected simple graph with girth g is also obtained, k = 2,3.

引用

页码：521 / 527

页数：7

共 20 条

[1]

Bondy J.A., 1979, GRAPH THEORY APPL

[2]

Huang Y.Q., 1998, CHINESE J CONTEMP MA, V19, P651

[3]

Huang Y.Q., 1998, MATH APPL, V11, P109

[4] CLASS OF UPPER-EMBEDDABLE GRAPHS [J].

JAEGER, F ;

PAYAN, C ;

XUONG, NH .

JOURNAL OF GRAPH THEORY, 1979, 3 (04) :387-391

[5]

JUNGERMAN M, 1987, T AM MATH SOC, V241, P401

[6]

KHOMENDO NP, 1977, GRAPH THEORY, P85

[7]

Kundu Sukhamay, 1974, J. Combin. Theory, Ser. B, V17, P199

[8]

Liu Y. P., 1995, EMBEDDABILITY GRAPHS

[9]

LIU YP, 1979, SCI SINICA SPECIAL I, V2, P41

[10]

NEBESKY L, 1985, CZECH MATH J, V35, P162

← 1 2 →