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.展开更多
In this paper we prove that the generalized permutation graph G（n, k） is upper embeddable if it has at most two odd subcycles, and that the maximum genus of G（n, k） is more than 「β（G（n,k））/3」 in most cases.
Let G be a 3 edge connected graph (possibly with multiple edges or loops), and let γ M(G) and β(G) be the maximum genus and the Betti number of G, respectively. Then γ M(G)≥β(G)/3 can be proved and this...Let G be a 3 edge connected graph (possibly with multiple edges or loops), and let γ M(G) and β(G) be the maximum genus and the Betti number of G, respectively. Then γ M(G)≥β(G)/3 can be proved and this answers a question posed by Chen, et al. in 1996.F FIRST OR展开更多
基金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.
基金The NSF (10671073) of Chinathe Scientific Fund (03080045) of the Gathered Talents by Nantong UniversityNSF (07KJB110090) of Jiangsu University.
文摘In this paper we prove that the generalized permutation graph G（n, k） is upper embeddable if it has at most two odd subcycles, and that the maximum genus of G（n, k） is more than 「β（G（n,k））/3」 in most cases.
文摘Let G be a 3 edge connected graph (possibly with multiple edges or loops), and let γ M(G) and β(G) be the maximum genus and the Betti number of G, respectively. Then γ M(G)≥β(G)/3 can be proved and this answers a question posed by Chen, et al. in 1996.F FIRST OR
