Abstract | ||
---|---|---|
This paper is devoted to the lower bounds on the maximum genus of graphs. A simple statement of our results in this paper can be expressed in the following form: Let G be a k-edge-connected graph with minimum degree @d, for each positive integer k(=<3), there exists a non-decreasing function f(@d) such that the maximum genus @c"M(G) of G satisfies the relation @c"M(G)>=f(@d)@b(G), and furthermore that lim"@d"->"~f(@d)=1/2, where @b(G)=|E(G)|-|V(G)|+1 is the cycle rank of G. The result shows that lower bounds of the maximum genus of graphs with any given connectivity become larger and larger as their minimum degree increases, and complements recent results of several authors. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1016/j.disc.2005.01.003 | Discrete Mathematics |
Keywords | Field | DocType |
05c,maximum genus,betti deficiency,minimal degree,connectivity,satisfiability,connected graph,lower bound | Integer,Discrete mathematics,Graph,Combinatorics,Upper and lower bounds,Connectivity,Cycle rank,Mathematics | Journal |
Volume | Issue | ISSN |
300 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
1 | 0.39 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuanqiu Huang | 1 | 22 | 8.90 |
Tinglei Zhao | 2 | 6 | 0.99 |