On plane graphs with link component number equal to the nullity
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 G with minimum degree at least 3 is a near-extremal graph if and only if G G is isomorphic to K4 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 K4 K 4 by two graph operations.
link component number nullity near-extremal graphs bicycle space tutte polynomial