Let G be a k（k ≤3）-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/（4 k）} of G,if,then G is up-embeddable.
The strong embeddability is a notion of metric geometry, which is an intermediate property lying between coarse embeddability and property A. In this paper, we study the permanence properties of strong embeddability f...The strong embeddability is a notion of metric geometry, which is an intermediate property lying between coarse embeddability and property A. In this paper, we study the permanence properties of strong embeddability for metric spaces. We show that strong embeddability is coarsely invariant and it is closed under taking subspaces, direct products, direct limits and finite unions. Furthermore, we show that a metric space is strongly embeddable if and only if it has weak finite decomposition complexity with respect to strong embeddability.展开更多
The strong embeddability is a notion of metric geometry, which is an intermediate property lying between coarse embeddability and property A. In this paper, the permanence properties of strong embeddability for groups...The strong embeddability is a notion of metric geometry, which is an intermediate property lying between coarse embeddability and property A. In this paper, the permanence properties of strong embeddability for groups acting on metric spaces are studied. The authors show that a finitely generated group acting on a finitely asymptotic dimension metric space by isometries whose K-stabilizers are strongly embeddable is strongly embeddable. Moreover, they prove that the fundamental group of a graph of groups with strongly embeddable vertex groups is also strongly embeddable.展开更多
Combined with the edge-connectivity, this paper investigates the relationship between the edge independence number and upper embeddability. And we obtain the following result:Let G be a k-edge-connected graph with gir...Combined with the edge-connectivity, this paper investigates the relationship between the edge independence number and upper embeddability. And we obtain the following result:Let G be a k-edge-connected graph with girth g. If $$ \alpha '(G) \leqslant ((k - 2)^2 + 2)\left\lfloor {\frac{g} {2}} \right\rfloor + \frac{{1 - ( - 1)^g }} {2}((k - 1)(k - 2) + 1) - 1, $$ where k = 1, 2, 3, and α′(G) denotes the edge independence number of G, then G is upper embeddable and the upper bound is best possible. And it has generalized the relative results.展开更多
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.展开更多
The embedding technique based on an operator appeared in [Liu, Y. P., Scientia Sinica, Special Issue on Math,1 (1979),191-201 (in Chinese)] for determining the maximum non-orientable genus of a graph is developed to o...The embedding technique based on an operator appeared in [Liu, Y. P., Scientia Sinica, Special Issue on Math,1 (1979),191-201 (in Chinese)] for determining the maximum non-orientable genus of a graph is developed to obtain the general theorem which presents a necessary and sufficient condition for a graph to be embeddable into either the orientable or the non-orientable surface of genus k. Furthermore,the greatest lower bound of the lengths of genus ranges of the class of nonplanar graphs which are up-embeddable is also obtained.展开更多
In this paper we mainly prove that let G be a(k+1)-edge-connected simple graph of order n with girth g.Then G is upper embeddable if for any independent set I(G) = {vi | 1 i k2 + 2},k = 0,1,2 and the lower bound is ti...In this paper we mainly prove that let G be a(k+1)-edge-connected simple graph of order n with girth g.Then G is upper embeddable if for any independent set I(G) = {vi | 1 i k2 + 2},k = 0,1,2 and the lower bound is tight.展开更多
This paper discusses the development of Boolean methods in some topics on graph em-beddings which are related to VLSI. They are mainly the general theory of graph embeddability, the orientabilities of a graph and the ...This paper discusses the development of Boolean methods in some topics on graph em-beddings which are related to VLSI. They are mainly the general theory of graph embeddability, the orientabilities of a graph and the rectilinear layout of an electronic circuit.展开更多
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.展开更多
1. Introduction Let κ be a non-negative integer. A κ-bend graph is a plane graph in which every edgeis a broken line consisting of at most κ+ 1 horizontal or vertical segments. A bend is any point which is the inte...1. Introduction Let κ be a non-negative integer. A κ-bend graph is a plane graph in which every edgeis a broken line consisting of at most κ+ 1 horizontal or vertical segments. A bend is any point which is the intersection of a horizontal segment and a verticalsegment of an edge. A planar graph G is κ-rectilinear if it admits a plane embedding Gwhich is a κ-bend graph. In this case G is said to be a κ-embedding of G.展开更多
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.展开更多
基金Supported by the Scientific Research Fund of Hunan Provincial Education Department (Grant No. 11C0541)
文摘Let G be a k（k ≤3）-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/（4 k）} of G,if,then G is up-embeddable.
基金Supported by National Natural Science Foundation of China(Grant No.11231002)
文摘The strong embeddability is a notion of metric geometry, which is an intermediate property lying between coarse embeddability and property A. In this paper, we study the permanence properties of strong embeddability for metric spaces. We show that strong embeddability is coarsely invariant and it is closed under taking subspaces, direct products, direct limits and finite unions. Furthermore, we show that a metric space is strongly embeddable if and only if it has weak finite decomposition complexity with respect to strong embeddability.
基金supported by the National Natural Science Foundation of China(Nos.11231002,11771061)
文摘The strong embeddability is a notion of metric geometry, which is an intermediate property lying between coarse embeddability and property A. In this paper, the permanence properties of strong embeddability for groups acting on metric spaces are studied. The authors show that a finitely generated group acting on a finitely asymptotic dimension metric space by isometries whose K-stabilizers are strongly embeddable is strongly embeddable. Moreover, they prove that the fundamental group of a graph of groups with strongly embeddable vertex groups is also strongly embeddable.
基金supported by National Natural Science Foundation of China (Grant No.10771062) New Century Excellent Talents in University (Grant No.NCET-07-0276)
文摘Combined with the edge-connectivity, this paper investigates the relationship between the edge independence number and upper embeddability. And we obtain the following result:Let G be a k-edge-connected graph with girth g. If $$ \alpha '(G) \leqslant ((k - 2)^2 + 2)\left\lfloor {\frac{g} {2}} \right\rfloor + \frac{{1 - ( - 1)^g }} {2}((k - 1)(k - 2) + 1) - 1, $$ where k = 1, 2, 3, and α′(G) denotes the edge independence number of G, then G is upper embeddable and the upper bound is best possible. And it has generalized the relative results.
基金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.
文摘The embedding technique based on an operator appeared in [Liu, Y. P., Scientia Sinica, Special Issue on Math,1 (1979),191-201 (in Chinese)] for determining the maximum non-orientable genus of a graph is developed to obtain the general theorem which presents a necessary and sufficient condition for a graph to be embeddable into either the orientable or the non-orientable surface of genus k. Furthermore,the greatest lower bound of the lengths of genus ranges of the class of nonplanar graphs which are up-embeddable is also obtained.
文摘In this paper we mainly prove that let G be a(k+1)-edge-connected simple graph of order n with girth g.Then G is upper embeddable if for any independent set I(G) = {vi | 1 i k2 + 2},k = 0,1,2 and the lower bound is tight.
基金the National Natural Science Foundation of China (Grant No. 69973001) .
文摘This paper discusses the development of Boolean methods in some topics on graph em-beddings which are related to VLSI. They are mainly the general theory of graph embeddability, the orientabilities of a graph and the rectilinear layout of an electronic circuit.
基金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.
文摘1. Introduction Let κ be a non-negative integer. A κ-bend graph is a plane graph in which every edgeis a broken line consisting of at most κ+ 1 horizontal or vertical segments. A bend is any point which is the intersection of a horizontal segment and a verticalsegment of an edge. A planar graph G is κ-rectilinear if it admits a plane embedding Gwhich is a κ-bend graph. In this case G is said to be a κ-embedding of G.
文摘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.
