| Let G=(V,E)be a graph.An independent set I of G is a subset of vertices no two of which are connected by an edge.Denote by I(G)the set of all independent sets of G(including empty sets).The independence polynomial of G is I(G;λ)=(?)λ|I|.A subset of vertices of G is called a dissociation set D if it induces a subgraph with vertex degree at most 1.Let D(G)be the set of all dissociation sets of G(including empty sets).The dissociation polynomial of G is DG(λ)=(?)λ|D|.In the last decades,the following extremal problem has attracted a lot of attention:Which graph has the maximum number of independent sets among all d-regular graphs of the same size?In 2017,Davies et al.introduceed a new technique called the occupancy method,which uses probabilistic methods to transform the global structure problem of a graph to a local problem and obtains the extrema value and extremal graphs using the dual theory in linear programming.Davies et al.used this method to give tight upper bounds on the independent polynomials and matching polynomials of d-regular graphs.Inspired by their work,in this paper,we study the problems of counting the numbers of independent sets and dissociation sets and charactering the corresponding extremal graphs of 3-regular graphs.These results will be given in Chapters 3 and 4,respectively.Cartesian product C3□K2 is commonly called the triangular-prism,denoted by GP 3,1).In Chapter 3,we proved by the occupancy method that for any 3-regular claw-free graph and for λ∈(0,15/41],with equality holding in both cases if and only if G(?)n/6·GP(3,1).In Chapter 4,we used the occupancy method to the dissociation set nproblem,and proved that for any 3-regular graph and for λ∈(0,1],with equality if and only if G(?)n/4·K4. |
