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 gen-eral 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 2~1/2m+n+ α2 distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd compo-nents 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 suffcient large natural number n, there are at least C2 n4 dmeapneyn dgienngu os ne mthbee vdadliuneg soffonrocf ormespidleutee 1g2r.a pThh eKsen rwesiuthlt sn i m≡p r4o,v 7e, 1th0e ( mbooudn1d2)s, owbthaeirnee dC b iys Ka ocroznhsikta anncde Voss and the methods used here are much simpler and straight.展开更多
In this paper, the problem of construction of exponentially many minimum genus crouchdings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to constru...In this paper, the problem of construction of exponentially many minimum genus crouchdings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding （or rotation） schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K12s＋8 in orientable surfaces, which show that there are at least 10/5 × （200/9）^s distinct minimum genus embeddings for K12s＋8 in orientable surfaces. We have also proved that K12s＋8 has at least 10/3× （200/9）^s distinct minimum genus embeddings in non-orientable surfaces.展开更多
In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentia...In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentially many current graphs by the theory of graceful labellings of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding（or rotation） scheme of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to these three approaches, we can construct exponentially many distinct genus embeddings of complete graph K12s＋3, which show that there are at least1/2× （200/9）s distinct genus embeddings for K12s＋3.展开更多
A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonsep...A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonseparating independent set containing Z(G)vertices is called the maximum nonseparating independent set.In this paper,we firstly give an upper bound for Z(G)of regular graphs and determine Z(G)for some types of circular graphs.Secondly,we show a relationship between Z(G)and the maximum genus M(G)of a general graph.Finally,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.展开更多
基金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 gen-eral 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 2~1/2m+n+ α2 distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd compo-nents 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 suffcient large natural number n, there are at least C2 n4 dmeapneyn dgienngu os ne mthbee vdadliuneg soffonrocf ormespidleutee 1g2r.a pThh eKsen rwesiuthlt sn i m≡p r4o,v 7e, 1th0e ( mbooudn1d2)s, owbthaeirnee dC b iys Ka ocroznhsikta anncde Voss and the methods used here are much simpler and straight.
基金Supported by NSFC(Grant Nos.10771225,11171114)the Scientific Research Pro jects of State Ethnic Affairs Commission(Grant No.14ZYZ016)
文摘In this paper, the problem of construction of exponentially many minimum genus crouchdings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding （or rotation） schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K12s＋8 in orientable surfaces, which show that there are at least 10/5 × （200/9）^s distinct minimum genus embeddings for K12s＋8 in orientable surfaces. We have also proved that K12s＋8 has at least 10/3× （200/9）^s distinct minimum genus embeddings in non-orientable surfaces.
基金Supported by the National Natural Science Foundation of China(No.10771225,11171114)
文摘In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentially many current graphs by the theory of graceful labellings of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding（or rotation） scheme of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to these three approaches, we can construct exponentially many distinct genus embeddings of complete graph K12s＋3, which show that there are at least1/2× （200/9）s distinct genus embeddings for K12s＋3.
基金supported by the National Natural Science Foundation of China(Nos.11171114,11401576,61662066,62072296)Science and Technology Commission of Shanghai Municipality(No.13dz2260400)。
文摘A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonseparating independent set containing Z(G)vertices is called the maximum nonseparating independent set.In this paper,we firstly give an upper bound for Z(G)of regular graphs and determine Z(G)for some types of circular graphs.Secondly,we show a relationship between Z(G)and the maximum genus M(G)of a general graph.Finally,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.
