Name
Abstract | ||
|---|---|---|
In this paper, we study connected plane graphs with link component number equal to the nullity and call them near-extremal graphs. We first study near-extremal graphs with minimum degree at least 3 and prove that a connected plane graph G with minimum degree at least 3 is a near-extremal graph if and only if G is isomorphic to K"4, the complete graph with 4 vertices. The result is obtained by studying general graphs using the knowledge of bicycle space and the Tutte polynomial. Then a simple algorithm is given to judge whether a connected plane graph is a near-extremal graph or not. Finally we study the construction of near-extremal graphs and prove that all near-extremal graphs can be constructed from a loop and K"4 by two graph operations. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2011.11.028 | Discrete Applied Mathematics |
Keywords | Field | DocType |
bicycle space,complete graph,general graph,link component number,plane graph,graph operation,connected plane graph,tutte polynomial,study near-extremal graph,near-extremal graph,minimum degree,nullity | Discrete mathematics,Block graph,Indifference graph,Modular decomposition,Combinatorics,Chordal graph,Cograph,Pathwidth,1-planar graph,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
160 | 9 | 0166-218X |
Citations | PageRank | References |
1 | 0.41 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuefeng Lin | 1 | 1 | 0.41 |
| S. D. Noble | 2 | 83 | 9.56 |
| Xian'an Jin | 3 | 13 | 5.27 |
| Wenfang Cheng | 4 | 8 | 2.51 |