A Generating Theorem for 5-Regular Simple Planar Graphs Ⅰ

摘要

Let ε be the class of all 5-regular simple planar graphs. We will provide a partial solution to generate all graphs in ￡. We shall discuss reducing graphs instead of constructing. We separate ￡ into two subclasses, T and Af, which are complement each other. A graph G ∈ ε_5 belongs to T if and only if G contains an edge that is a part of three distinct triangles of G. Our main result is that every graph in T can be reduced to a smaller graph H in N by repeatedly applying one of Toida's operations, called D-reduction, together with some K-operations. Applying a D-reduction to G is to delete two adjacent vertices {x, y} in G and to add new edges between vertices of degree less than five in G - {x,y} so that the new graph is again in ￡. The K-operations change only edges and will be applied if the new graph is still in ε. An alternating universal circuit in G is a universal circuit C that alternately contains edges from G and its complementary graph G. To flip C means to delete its edges in G from G and to add its edges from G to G. Applying a K-operation to G is to select an alternating universal circuit in G and to flip it. We use our general result that if a connected graph G' in ε is not 3-connected, then G' can be reduced to a smaller graph in ￡ by a combination of D-operations and K-transformations.