Forcing Number Of Cata-condensed Phenylenes And The Neighbor-scattering Number Of Digraphs

In chemical graph theory, chemical molecules'space topological indices and topolog-ical properties as well as the relations between the chemical molecules'physicochemicalproperties and their topological indices and topological properties are studied. Chemicalgraph theory plays an important role in predicting and compounding new chemical sub-stances and new medicines. The notion of forcing number of a perfect matching M wasintroduced by Harary et. al in 1991. Let G be a graph and let M be a perfect matching(orKekul′e structure) of G. A subset S of M is said to force M if S is in no other perfectmatching. The forcing number ?(M) of M is the cardinality of a smallest subset S thatforces M. The anti-forcing number and anti-Kekule′number are recently introduced byDamir et al. The anti-forcing number is defined as the smallest number of edges thathave to be removed in order that any graph remains with a single Kekule′structure. Sim-ilarly, the anti-Kekule′number is defined as the smallest number of edges that have tobe removed in order that any graph remains connected but without any Kekule′struc-ture. In the second chapter, we show that the anti-Kekule′number of Cata-condensed[h]-phenylenes is 3, the anti-forcing number of a Cata-condensed [h]-phenylene is h, andh2≤?(M)≤h, where h is the number of the hexagons and M is a Kekul′e structure ofthe Cata-condensed [h]-phenylene. Moreover, as an extension of the concept of neighbor-scattering number of graphs, we introduce the notion of neighbor-scattering number ofdigraphs. Let D = (V,A) be a digraph. The open and closed out-neighborhoods of a setS ? V are denoted by N+(S) = {u : vu∈A(D),v∈S} \ S and N+[S] = N+(S) {S},respectively. A vertex subversion strategy of D, S, is a set of vertices of D whose closedout-neighborhood is deleted from D. The survival-subgraph is defined by D/S+. A ver-tex subversion strategy of D, S, is called a cut-strategy of D if the survival-subgraphis strongly disconnected orφ. The neighbor-scattering number S(D) of a digraph D isdefined as S(D) = maxS?V {ω(D/S+) ? |S|, S is cut-strategy of D,ω(D/S+)≥1}, whereω(D/S+) is the number of strongly connected components in the digraph D/S+. In thethird chapter, we first discuss some basic properties of the neighbor-scattering number ofdigraphs, and then we study the neighbor-scattering number of a orientation graph of Knand the directed neighbor-scattering number of Ks,t(s = 3,4).