(k,l)-Regular Maximal Planar Graph

In the literature [2], S.Karimis introduced the conception of the(k,l)—regular maximal planar graph, when he discussed hydrocarbon. A graph is (k, l)-regular if each vertex has degree either k or l. A simple graph G with n vertices and e edges is (k,l) -regular maximal planar graph, if it is (k, l)-regular and such that the number of edges are max-mum satisfies ε = 3n - 6. Based on the studies from S.Karimis and Dragan Stevanovic, we reach the essentice condition for the existence of the (k,l)—regular maximal planar graph, then we reach the construction of the existing possible (k, l) —regular maximal planar graph. In this thesis, we not only completely answer the two questions from S.Karimis, but also study the existence and construction of the (k,l)— regular maximal planar graph on n ≤ 12 vertices.Some terminology, notation and basic results on the planar graph are given in chapter 1. In chapter 2, this thesis study existence and construction of the r—regular maximal planar graph, then we obtain that there exist only the order 2 of 0-regular, the order 3 of 2-regular, the order 4 of 3-regular, the order 6 of 4-regular, the order 12 of 5-regular maximal planar graph. In charter 3, we main discuss existence and construction of the (k, l)— regular maximal planar graph on n > 12 vertices, then we obtain that there exist the (3,6),(4,6),(5,6)—regular maximal planar graphs. In charter 4, finally, the thesis analyses and discusses whether or not there is the (k, l)—regular maximal planar graph on n < 12 vertices, then reaches the conditions for the existence of the (k,l)—regular maximal planar graphs on n < 12 vertices. The main results are listed as following:If G is a (3,4)—regular maximal planar graph on n vertices, then n = 5.If G is a (3,5)-regular maximal planar graph on n vertices, then n = 8.If G is a (3,6)-regular maximal planar graph on n vertices, then n > 5, and also n ≡ 0(mod2).If G is a (3,7)-regular maximal planar graph on n vertices, thenn = 12.There exists no (3, l)-regular maximal planar graph on n vertices(l≥8).When the order n = 7,8,9,10, there exist the (4,5)-regular maximal planar graph.