The Domination Number And Independence Number Of Graphs

Let G=(V(G),E(G))is a simple graph,where V(G)=n and E(G)=m.The total dominating set of G without isolated vertex is a vertex set D of G such that each vertex of graph G is adjacent to at least one vertex of D.The total dom-ination number is the minimum cardinality of a total dominating set,we denote it as ?t(G).Let d1,d2,…,dn is the non-decreasing sequence of G,the annihilation number a(G)of G,is the largest integer k such that the sum of the k vertices' degree is at most m,that is,?i=1k di?m.A set S of vertices is called an annihilation set if ?v?Sd(v)?m.S is an optimal annihilation set if |S|=a(G).A set I of vertices of G is an independent set of G if any two vertices in I are nonadjacent.The maximum order of an independent set of G is the independence number a(G).A matching of a graph G is an edge set M such that any two edges in M are nonadjacent.The matching number ?'(G)is the maximum number of edges in a matching of graph G.A fractional matching of a graph G is a function f from E(G)to the interval[0,1]such that ?e?T(v)f(e)? 1 for each vertex v,where?(v)denotes the set of edges incident to v.The fractional matching number ?(G)is the maximum of ?e?E(G)f(e)over all fractional matchings f.The thesis consists of four chapters,we mainly focus on studying the rela-tionship between the total domination number and annihilation number,and the relationship between the independence number and fractional matching number.In chapter 1,we mainly introduce the background and the significance of the research subject,give some basic symbols and concepts involved in this paper,ex-pound the research status of the relevant fields,and list our main results in this paper.In chapter 2,we discuss the Henning's Conjecture.Henning et al.put forward a conjecture about the total domination number and the annihilation number in 2013:If G is a connected nontrivial graph,then ?t(G)? a(G)+1.We study the total domination number and the annihilation number of the Tree-like graph.We prove the conjecture is also true for Tree-like graph.Thus,the existing results are generalized.In chapter 3,we discuss the relationship between the independence number and fractional matching number in random graphs.Since matching is a special case of fractional matching,?(G)??'(G)for every graph G,the results that are correct for matching number are also true for fractional matching number.Considering the relationship between the independence number and fractional matching number in random graphs,our results are not restricted to the maximum degree or consid-er whether there are triangles in graphs,we only need to consider the probability of each edge appears.In this chapter,we main prove that:Let G=G(n,p),if 0<p<1-e-20/4n+13,then a.s.13/?(G)+?(G)? n(G),and ?(G)+18/13(G)?n(G).In chapter 4,we indicate some problems that can be studied further.