On The Perfect Path System And Anti-kekulé Number Problem Of Polyomino Graphs

A polyomino graph is a 2-connected finite plane graph such that each interior face is surrounded by a regular square of side length 1.In chemical graph theory,a perfect matching of a graph is also called a Kekule structure.Let G be a connected graph,set S is an edge subset of G.If the subgraph G-S is connected and has no perfect matching,then S is called an anti-Kekule set of G.The size of the anti-Kekule set that contains the minimum number of edges of G is called the anti-Kekule number of G,denoted by ak(G).The concept of the anti-Kekule number of the graph was first proposed by D.Vukicevic et al.by studying benzenoid systems in 2007.In this paper,we study the anti-Kekule number problem of polyomino graphs,which is divided into four chapters.In chapter 1,we mainly introduce some basic concepts of graph theory,notation,the research background and progress of the anti-Kekule number problem of the graph.Finally,the main results obtained in this paper are summarized.In Chapter 2,we obtain that for a non-normal polyomino graph P,ak(P)=1 if and only if P has a fixed double edge.When P with fixed single edges but has no fixed double edges,ak(P)=2.For a normal polyomino graph with at least two squares,the lower and upper bounds of the anti-Kekule number are 2 and 4,respectively,and they are tight.In Chapter 3,by transforming a polyomino graph into a trapezoidal system.Using the properties of the monotone path and perfect path system of the trapezoidal system,we obtain an equivalent characterization of normal polyomino graph whose anti-Kekule number is 2 and 3.Finally,an algorithm for finding a smallest anti-Kekule set of normal polyomino graphs with n vertices is given,and its time complexity is O(n3).In Chapter 4,it is a summary of the results obtained in this paper and the subsequent prospects,pointing out the direction and main content of further research in the future.