Let G be a k（k ≤ 2）-edge connected simple graph with minimal degree ≥ 3 and girth g, r = [g-1/2]. For any edge uv ∈ E（G）, if dG（u） ＋ dG（v） 〉2v（G） - 2（k ＋ 1）（9 - 2r）/（k ＋ 1）（2r - 1）（g - 2r）...Let G be a k（k ≤ 2）-edge connected simple graph with minimal degree ≥ 3 and girth g, r = [g-1/2]. For any edge uv ∈ E（G）, if dG（u） ＋ dG（v） 〉2v（G） - 2（k ＋ 1）（9 - 2r）/（k ＋ 1）（2r - 1）（g - 2r）＋ 2（g - 2r - 1）,then G is up-embeddable. Furthermore, similar results for 3-edge connected simple graphs are also obtained.展开更多
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 ...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.展开更多
It is known[5] that an investigation of the up-embeddability of the 3-regular graphs shows a useful approach to that of the general graph. But as far, very few characterizations of the upembeddability are known on the...It is known[5] that an investigation of the up-embeddability of the 3-regular graphs shows a useful approach to that of the general graph. But as far, very few characterizations of the upembeddability are known on the 3-regular graphs. Let G be a 2-edge connected 3-regular graph.We prove that G is up-embeddable if and only if G can be obtained from the graphs θ, θ or K4by a series of M- or N-extensions. Meanwhile, we also present a new structural characterization of such graph G provided that G is up-embeddable.展开更多
In this paper,we provide a new class of up-embeddable graphs,and obtain a tight lower bound on the maximum genus of a class of 2-connected pseudographs of diameter 2 and of a class of diameter 4 multi-graphs.This exte...In this paper,we provide a new class of up-embeddable graphs,and obtain a tight lower bound on the maximum genus of a class of 2-connected pseudographs of diameter 2 and of a class of diameter 4 multi-graphs.This extends a result of (S)koviera.展开更多
基金Supported by National Natural Science Foundation of China(No.11301171)Hunan youth backbone teachers training Program(H21308)+1 种基金Tianyuan Fund for Mathematics(No.11226284)Hunan Province Natural Science Fund Projects(No.13JJ4079,14JJ7047)
文摘Let G be a k（k ≤ 2）-edge connected simple graph with minimal degree ≥ 3 and girth g, r = [g-1/2]. For any edge uv ∈ E（G）, if dG（u） ＋ dG（v） 〉2v（G） - 2（k ＋ 1）（9 - 2r）/（k ＋ 1）（2r - 1）（g - 2r）＋ 2（g - 2r - 1）,then G is up-embeddable. Furthermore, similar results for 3-edge connected simple graphs are also obtained.
基金supported by National Natural Science Foundation of China (Grant No. 10571013)
文摘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.
文摘It is known[5] that an investigation of the up-embeddability of the 3-regular graphs shows a useful approach to that of the general graph. But as far, very few characterizations of the upembeddability are known on the 3-regular graphs. Let G be a 2-edge connected 3-regular graph.We prove that G is up-embeddable if and only if G can be obtained from the graphs θ, θ or K4by a series of M- or N-extensions. Meanwhile, we also present a new structural characterization of such graph G provided that G is up-embeddable.
基金This work is partially supported by the National Natural Science Foundation of China (Grant No.10571013)
文摘In this paper,we provide a new class of up-embeddable graphs,and obtain a tight lower bound on the maximum genus of a class of 2-connected pseudographs of diameter 2 and of a class of diameter 4 multi-graphs.This extends a result of (S)koviera.
