Study On The Global Forcing Number And Anti-Kekule Number Of Some Classes Of Graphs

Let G be a graph, M a perfect matching of G. A forcing set of M is a subset S of M which is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M which corresponds to the innate degree of freedom in chemical literature. The forcing number gets the attention of chemists and graph theorists. Recently, the idea of "forcing" for the perfect matchings has been extended and some new relevant concepts have been proposed including the global forcing number and anti-Kekule number.A global forcing set of G is a subset of edges that can distinguish all perfect matchings of G completely, i.e., no two different perfect matchings of G coincide on it. The smallest cardinality of global forcing sets of G is called the global forcing number of G. Different from a forcing set, a global forcing set is defined globally in a graph, i.e., without reference to a particular perfect matching. Vukicevic and Sedlar established a bound on the global forcing number of the triangular grid with equal number of vertices in each row and column. Afterward, Vukicevic and Doslic obtained the global forcing number of the grid graphs. Doslic proved that the global forcing number of a cata-condensed hexagonal system is equal to the number of its hexagons. In this thesis, we study the global forcing numbers of boron-nitrogen fullerene graphs, catafused coronoids, C20, C24, normal hexagonal systems and the Cartesian product of a cycle and a path.An anti-Kekule set of a connected graph G is an edge subset S such that G-S is connected and has no perfect matchings. The smallest cardinality of anti-Kekule sets of G is called the anti-Kekule number of G. This concept originated from the study of hexagonal systems. Vukicevic and Trinajstic showed that the anti-Kekule number of benzenoid parallelograms is2and the anti-Kekule number of cata-condensed hexag-onal systems is either2or3. Veljan and Vukicevic obtained that the anti-Kekule numbers of the infinite triangular, rectangular and hexagonal grids are9.6and4, respectively. Yang et al. proved that the anti-Kekule number of fullerene graphs is4. In this thesis, we will consider the anti-Kekule number of all hexagonal systems.There are five chapters in this thesis. In Chapter one, we first introduce some basic concepts, terminologies and notations. Then we introduce the background and the development of the global forcing number and anti-Kekule number of graphs, respectively. At last, we outline the main results obtained in the following chapters.In Chapter two, we shall characterize global forcing sets of a general graph, and then as applications, we get the global forcing numbers of three kinds of chemical graphs. We establish a sharp lower bound on the global forcing number of a boron-nitrogen fullerene graph by showing that any two adjacent faces of it form a nice subgraph. For a catafused coronoid with n hexagons, Doslic showed that its global forcing number is n. We prove that its global forcing number is either n or n-1, correcting Doslic's result. Finally, with the aid of computers, we obtain that the global forcing numbers of C20and C24are7and8respectively.In Chapter three, we consider the global forcing number of hexagonal systems. We obtain explicit formulas for the global forcing numbers of two kinds of hexagonal systems:Bp,q and Z(k,l). Then we introduce perfect path systems of hexagonal systems. By giving a criterion to determine whether two adjacent hexagons of a normal hexagonal system form its nice subgraph, we derive a sharp lower bound on the global forcing number of normal hexagonal systems. Finally, by showing some properties of dividable hexagonal systems, we obtain a formula for the global forcing number of dividable hexagonal systems and design a linear algorithm for finding a minimum global forcing set of a dividable hexagonal system.In Chapter four, we consider the global forcing number of the Cartesian product of a cycle and a path Cm×Pk. By discussing the relationship between the quadrangles on each layer and the nice cycle of Cm×Pk, we obtain the global forcing numbers of C2m+1×P2k and C4×Pk. For C2m×Pk (m>2), an upper bound and a lower bound on its global forcing number are derived.In Chapter five, we study the anti-Kekule number of hexagonal systems. We show that for a hexagonal system with more than one hexagon, its anti-Kekule number is 0if and only if it has no perfect matchings; its anti-Kekule number is1if and only if it has a fixed double edge. For the other cases, its anti-Kekule number is either2or3. We give a characterization for a normal hexagonal system whose anti-Kekule number is2, and present an O(n2) algorithm for finding a minimum anti-Kekule set in a normal hexagonal system, where n is the number of its vertices.