Up-embeddability via girth and the degree-sum of adjacent vertices |
| |
Authors: | GuangHua Dong and YanPei Liu |
| |
Institution: | (1) Department of Mathematics, Beijing Jiaotong University, Beijing, 100044, China;(2) Department of Mathematics, School of Science, Tianjin Polytechnic University, Tianjin, 300160, China |
| |
Abstract: | Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d
G
(u) + d
G
(v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d
G
(u) + d
G
(v) ⩾ n − 2g + 3 (resp. d
G
(u) + d
G
(v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight.
This work was supported by National Natural Science Foundation of China (Grant No. 10571013) |
| |
Keywords: | maximum genus up-embeddable order girth |
本文献已被 SpringerLink 等数据库收录! |
|