Independent Domination And Double Total Domination Of Graphs With Small Degree

In the thesis,we mainly discuss some related problems on the independent domination and double total domination of graphs with small degree.Let G be a simple graph and S be a vertex subset of G.If S is an independent set and every vertex out of S is adjacent to a vertex in S,then S is called independent dominating set of G.The independent domination number i(G)of G is the minimum cardinality over all independent dominating sets of G.For two graphs G and F,G is called F-free if it does not contain F as an induced subgraph.On the independent domination numbers of cubic graphs,we prove that every Kl,3-free cubic graph G has i(G)≤1/3|V(G)|.Furthermore,if G is connected,then i(G)=1/3|V(G)| if and only if G ∈H,where H is an infinite cubic family.Also,we show that if G is a{K1,3,K4-,C6+}-free cubic graph without C3□K2-component,then i(G)≤3/10|V(G)|.We construct two classes of K1,3-free cubic graphs,which attach the upper bounds respectively.A vertex subset S of graph G is called a double total dominating set of G if every vertex of G has at least two adjacent vertices in S.The double total domination number γ×2,t(G)of G is the minimum cardinality over all the double total dominating sets in G.Let Pi□Pn denote the Cartesian product of path Pi and path Pn.We determine the values of γ×2,t(Pi□Pn)for i=2,3.Moreover,we give the lower and upper bounds of γ×2,t(Pi□Pn)when i≥4.