The Face Pair Of Planar Graph

Graph theory is one of the most important branches of applied mathematics. Its wide application accelerates its development. Especially in the recent years, with the occurrence and development of computer technology, graph theory has made great progress and obtained wonderful achievement.A classic question in graph theory has been the search for cages, that is, minimal v-regular graphs with a given girth. Considerable effort has yielded only a handful of precise results. Harary and Kovacs have introduced the notion of cages for girth pair, where one seeks minimal v-regular graphs with given odd and even girths. A sequence of articles has resulted in some exact results when the even girth is four, and a few other isolated results. What we propose in the present work is to look only at planar graphs and consider only odd and even faces rather than odd and even cycles.Let G be a plane graph and let v, ω and ε be integers bigger than 2. We say that (ω,ε) is the face pair of G if ω and ε are the lengths respectively of shortest odd and even faces of G. In this case we say G is an (ω,ε)-graph. If G is v-regular graph, that is if every vertex of G has degree v, we say that G is an (v, ω, ε)-graph. The number of vertices in a smallest (v,ω, ε)-graph will be denoted by f(v, ω, ε). By the Euler formula, there only possible cases are(3,3, ε), (3, 5, ε), (3, ω, 4), (4, 3, ε) and (5, 3, ε)Connie M. Campbell gave the results for (3, 3, ε) and (3, ω, 4). We corrected the one for (3, 3, ε) and gave the results for the rest three cases, i.e. (3, 5, ε), (4, 3, ε) and (5, 3, ε).In this thesis, an algorithm for constructing small (v, ω, ε)-graphs is given, and it is used to improve the upper bounds of f(v, ω, ε). The Euler formula is used to prove the lower bounds of f(v, ω, ε). As a result, the precise values of f(y, ω, ε)are obtained, and this finished the research on the problem of the smallest regular planar graph with given face pairs.