In this article the rooted planar near-4-regular Eulerian trails are enum erated and an explicit form ula for such m aps is presented. Further, the rooted near-4-regular Eulerian m aps on the torus are counted in an...In this article the rooted planar near-4-regular Eulerian trails are enum erated and an explicit form ula for such m aps is presented. Further, the rooted near-4-regular Eulerian m aps on the torus are counted in an exact w ay.展开更多
It is proved that every 3 connected loopless multigraph has maximum genus at least one third of its cycle rank plus one if its cycle rank is not less than ten, and if its cycle rank is less than ten,it is upper emb...It is proved that every 3 connected loopless multigraph has maximum genus at least one third of its cycle rank plus one if its cycle rank is not less than ten, and if its cycle rank is less than ten,it is upper embeddable.This lower bound is tight.There are infinitely many 3 connected loopless multigraphs attaining this bound.展开更多
The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous kn...The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous known results. Thus, a picture of the lower bounds on the maximum genus of loopless multigraphs is presented.展开更多
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.展开更多
In this article the C n graphs are introduced, by which a characterization of the embeddability of a graph on either an orientable surface or a non orientable surface is provided.
It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of th...It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of the independence number as well as the girth of a graph, and thus use the formulation in [2] to translate this result to lower bound on the maximum genus. Meantime it is shown that both of the bounds are best possible.展开更多
Define the density d(G) of a graph G as (ε(G))/(v(G)). A polynomialalgorithm for finding the densest subgraph of a graph is provided. Some results related to thedensity of the densest subgraph of a graph are obtained...Define the density d(G) of a graph G as (ε(G))/(v(G)). A polynomialalgorithm for finding the densest subgraph of a graph is provided. Some results related to thedensity of the densest subgraph of a graph are obtained as well.展开更多
文摘In this article the rooted planar near-4-regular Eulerian trails are enum erated and an explicit form ula for such m aps is presented. Further, the rooted near-4-regular Eulerian m aps on the torus are counted in an exact w ay.
文摘It is proved that every 3 connected loopless multigraph has maximum genus at least one third of its cycle rank plus one if its cycle rank is not less than ten, and if its cycle rank is less than ten,it is upper embeddable.This lower bound is tight.There are infinitely many 3 connected loopless multigraphs attaining this bound.
文摘The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous known results. Thus, a picture of the lower bounds on the maximum genus of loopless multigraphs is presented.
文摘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.
文摘In this article the C n graphs are introduced, by which a characterization of the embeddability of a graph on either an orientable surface or a non orientable surface is provided.
基金National Natural Science Foundation of China!(No.19801013).
文摘It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of the independence number as well as the girth of a graph, and thus use the formulation in [2] to translate this result to lower bound on the maximum genus. Meantime it is shown that both of the bounds are best possible.
基金This research is supported by the National Natural Science Foundation of China under Grant No.10161008.Partially supported by the Natural Sciences Foundation of Inner Mongolia Autonomous Region(No.20000901-01)
文摘Define the density d(G) of a graph G as (ε(G))/(v(G)). A polynomialalgorithm for finding the densest subgraph of a graph is provided. Some results related to thedensity of the densest subgraph of a graph are obtained as well.
