There are many results on the maximum genus, among which most are written for the existence of values of such embeddings, and few attention has been paid to the estimation of such embeddings and their applications. In...There are many results on the maximum genus, among which most are written for the existence of values of such embeddings, and few attention has been paid to the estimation of such embeddings and their applications. In this paper we study the number of maximum genus embeddings for a graph and find an exponential lower bound for such numbers. Our results show that in general case, a simple connected graph has exponentially many distinct maximum genus embeddings. In particular, a connected cubic graph G of order n always has at least $ (\sqrt 2 )^{m + n + \tfrac{\alpha } {2}} $ distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd components of an optimal tree T. What surprise us most is that such two extremal embeddings (i.e., the maximum genus embeddings and the genus embeddings) are sometimes closely related with each other. In fact, as applications, we show that for a sufficient large natural number n, there are at least $ C2^{\tfrac{n} {4}} $ many genus embeddings for complete graph K n with n ≡ 4, 7, 10 (mod12), where C is a constance depending on the value of n of residue 12. These results improve the bounds obtained by Korzhik and Voss and the methods used here are much simpler and straight.展开更多
Some results about the genus distributions of graphs are known,but little is known about those of digraphs.In this paper,the method of joint trees initiated by Liu is generalized to compute the embedding genus distrib...Some results about the genus distributions of graphs are known,but little is known about those of digraphs.In this paper,the method of joint trees initiated by Liu is generalized to compute the embedding genus distributions of digraphs in orientable surfaces.The genus polynomials for a new kind of 4-regular digraphs called the cross-ladders in orientable surfaces are obtained.These results are close to solving the third problem given by Bonnington et al.展开更多
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 bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less than 2 β(G?1/2 β(G?1 β(G) and not larger than β(G). Furt...The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less than 2 β(G?1/2 β(G?1 β(G) and not larger than β(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.展开更多
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 investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spa...In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T, there exists a sequence of fundamental cycles C 1,C 2,…,C 2g with C 2i?1 ∩ C 2i ≠ /0 for 1 ? i ? g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C 1, C 2,…,C 2γM(G) such that C 2i?1 ∩ C 2i ≠ /0 for 1 ? i ? γM (G), where β(G) and γM (G) are the Betti number and the maximum genus of G, respectively. This implies that it is possible to construct an orientable embedding with large genus of a graph G from an arbitrary spanning tree T (which may have very large number of odd components in G E(T)). This is different from the earlier work of Xuong and Liu, where spanning trees with small odd components are needed. In fact, this makes a common generalization of Xuong, Liu and Fu et al. Furthermore, we show that (1) this result is useful for locating the maximum genus of a graph having a specific edge-cut. Some known results for embedded graphs are also concluded; (2) the maximum genus problem may be reduced to the maximum matching problem. Based on this result and the algorithm of Micali-Vazirani, we present a new efficient algorithm to determine the maximum genus of a graph in $ O((\beta (G))^{\frac{5} {2}} ) $ steps. Our method is straight and quite different from the algorithm of Furst, Gross and McGeoch which depends on a result of Giles where matroid parity method is needed.展开更多
A direct and elementary method is provided in this paper for counting trees with vertex partition instead of recursion, generating function, functional equation, Lagrange inversion, and matrix methods used before.
In this paper a method is given to calculate the explicit expressions of embedding genus distribution for ladder type graphs and cross type graphs. As an example, we refind the genus distri- bution of the graph Jn whi...In this paper a method is given to calculate the explicit expressions of embedding genus distribution for ladder type graphs and cross type graphs. As an example, we refind the genus distri- bution of the graph Jn which is the first class of graphs studied for genus distribution where its genus depends on n.展开更多
We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero...We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero for planar graphs, and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings. In this paper, we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.展开更多
Abstract In this paper, the relationship between non separating independent number and the maximum genus of a 3 regular simplicial graph is presented. A lower bound on the maximum genus of a 3 regular graph involving ...Abstract In this paper, the relationship between non separating independent number and the maximum genus of a 3 regular simplicial graph is presented. A lower bound on the maximum genus of a 3 regular graph involving girth is provided. The lower bound is tight, it improves a bound of Huang and Liu.展开更多
基金the National Natural Science Foundation of China (Grant No. 10671073)Scienceand Technology commission of Shanghai Municipality (Grant No. 07XD14011)Shanghai Leading AcademicDiscipline Project (Grant No. B407)
文摘There are many results on the maximum genus, among which most are written for the existence of values of such embeddings, and few attention has been paid to the estimation of such embeddings and their applications. In this paper we study the number of maximum genus embeddings for a graph and find an exponential lower bound for such numbers. Our results show that in general case, a simple connected graph has exponentially many distinct maximum genus embeddings. In particular, a connected cubic graph G of order n always has at least $ (\sqrt 2 )^{m + n + \tfrac{\alpha } {2}} $ distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd components of an optimal tree T. What surprise us most is that such two extremal embeddings (i.e., the maximum genus embeddings and the genus embeddings) are sometimes closely related with each other. In fact, as applications, we show that for a sufficient large natural number n, there are at least $ C2^{\tfrac{n} {4}} $ many genus embeddings for complete graph K n with n ≡ 4, 7, 10 (mod12), where C is a constance depending on the value of n of residue 12. These results improve the bounds obtained by Korzhik and Voss and the methods used here are much simpler and straight.
基金Beijing Jiaotong University Fund (Grant No.2004SM054)the National Natural Science Foundation of China (Grant No.10571013)
文摘Some results about the genus distributions of graphs are known,but little is known about those of digraphs.In this paper,the method of joint trees initiated by Liu is generalized to compute the embedding genus distributions of digraphs in orientable surfaces.The genus polynomials for a new kind of 4-regular digraphs called the cross-ladders in orientable surfaces are obtained.These results are close to solving the third problem given by Bonnington et al.
基金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.
基金This work was partially supported by the National Natural Science Foundation of China (Grant Nos. 60373030,10751013)
文摘The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less than 2 β(G?1/2 β(G?1 β(G) and not larger than β(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.
基金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 Nos.10271048,10671073)Science and Technology Commission of Shanghai Municipality (Grant No.07XD14011)Shanghai Leading Discipline Project (Project No.B407)
文摘In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T, there exists a sequence of fundamental cycles C 1,C 2,…,C 2g with C 2i?1 ∩ C 2i ≠ /0 for 1 ? i ? g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C 1, C 2,…,C 2γM(G) such that C 2i?1 ∩ C 2i ≠ /0 for 1 ? i ? γM (G), where β(G) and γM (G) are the Betti number and the maximum genus of G, respectively. This implies that it is possible to construct an orientable embedding with large genus of a graph G from an arbitrary spanning tree T (which may have very large number of odd components in G E(T)). This is different from the earlier work of Xuong and Liu, where spanning trees with small odd components are needed. In fact, this makes a common generalization of Xuong, Liu and Fu et al. Furthermore, we show that (1) this result is useful for locating the maximum genus of a graph having a specific edge-cut. Some known results for embedded graphs are also concluded; (2) the maximum genus problem may be reduced to the maximum matching problem. Based on this result and the algorithm of Micali-Vazirani, we present a new efficient algorithm to determine the maximum genus of a graph in $ O((\beta (G))^{\frac{5} {2}} ) $ steps. Our method is straight and quite different from the algorithm of Furst, Gross and McGeoch which depends on a result of Giles where matroid parity method is needed.
基金the National Natural Science Foundation of China (Grant No. 10571013)
文摘A direct and elementary method is provided in this paper for counting trees with vertex partition instead of recursion, generating function, functional equation, Lagrange inversion, and matrix methods used before.
基金supported National Natural Science Foundation of China (Grant Nos. 10571013, 60433050)the State Key Development Program of Basic Research of China (Grant No. 2004CB318004)
文摘In this paper a method is given to calculate the explicit expressions of embedding genus distribution for ladder type graphs and cross type graphs. As an example, we refind the genus distri- bution of the graph Jn which is the first class of graphs studied for genus distribution where its genus depends on n.
文摘We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero for planar graphs, and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings. In this paper, we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.
文摘Abstract In this paper, the relationship between non separating independent number and the maximum genus of a 3 regular simplicial graph is presented. A lower bound on the maximum genus of a 3 regular graph involving girth is provided. The lower bound is tight, it improves a bound of Huang and Liu.
