Font Size: a A A

Upper Minus Total Domination Of Regular Graphs

Posted on:2009-04-17Degree:MasterType:Thesis
Country:ChinaCandidate:J G WuFull Text:PDF
GTID:2120360245973687Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
Within the last more than thirty years,concurrent with the growth of domination ingraphs is one of the fastest growing areas within graph theory.With researching deeply,many different types of domination parameters have sprung up rapidly.Dominating functionin graph is the natural variation of domination.Thus,it is possible to study domination interms of functional properties.Nowadays,the study on dominating functions is a new andchallenging research field in domination theory.As almost all decision problems of dominating functions are NP-complete for general graphs,it is interesting to investigate bounds ofthose and characterize the structure of graphs,which is useful to design their approximationalgorithms.Harris introduced upper minus total domination in reference[21].A three-valued function f defined on the vertices of a graph G=(V,E),f→{-1,0,1},is a minus total dominating function(MTDF),if,every v∈V,f[v]≥1(f[v]=(?)(N(v))=∑v∈N(v)f(v)).An MTDF f is minimal if there does not exist an MTDF g:V(G)→{-1,0,1},f≠g,for whichg(v)≤f(v)for every v∈V(G).The weight of an MTDF is w(f)=∑v∈N(G)f(v).The upper minus total dominationГt-(G)=max{w(f)| f is minimal minus total dominating function ofG}.In this paper,we mainly investigate upper minus total dominating functions in regulargraphs,and the corresponding results are the following two parts:In the first part,we firstly introduce upper bounds onГt-(G) of 3-regular graph and 5-regular graph.Also,we establish an upper bound onГt-(G)of the k-regular graph(k is an odd)and characterize the extremal graphs attaining the upper bound.In the second part,we firstly introduce upper bounds onГt-(G)of 2-regular graph and4-regular graph.Also,we study upper bound onГt-(G)of 6-regular graph.And give theconjecture of upper bound onГt-(G)of the k-regular graph (k is an even).
Keywords/Search Tags:k-regular graphs, upper minus total domination, domination number
PDF Full Text Request
Related items