Research On Italian Domination Numbers Of Cartesian Product Of Circles And Paths

Domination on graphs is an important research field graph theory.To determine the domination number is NP-complete.It has theorical and application values to study domination on large graphs.This paper mainly studies the Italian domination numbers of Cartesian product graphs of cycles and paths Cn?Pm.For graph G=(V,E),the open neighborhood of the vertex v is N(v)={u ?V|uv ? E}.The function f:V(G)?{0,1,2} satisfies:for each vertex of f(v)=0,there is ?u?N(u)? 2,it is called the Italian Domination functioe of the graph G.The weight of the function isw(f)=?v?N(v)f(v).The smallest weight of the function is called the Italian Domination number of the graph G,and is written as ?I(G).For the upper bounds of the Italian domination number of Cn?Pm,the method of computer construction proof is adopted.Through analysis of the graphic characteristics for Cn?Pm,recursive Italian domination functions are constructed.According to the Italian domination function,the upper bound of the Italian control number can be calculated.For the lower bounds for the Italian Domination number for Cn?Pm,in this paper,a Bagging method is proposed to prove the lower bound of Italian domination numbers.The main idea is to use the upper bounds as the target,and group the rows with a larger weight in the middle for Cn?Pm and their neighboring rows into a group so that it is not greater than the upper bounds.The lower bounds of Cn?P3 and C3?Pm are proved by this method.For the other lower bounds for Cn?Pm(n,m>4),the lower bound of the Italian domination number is proved by the division method.In the end,the exact values of the Italian domination numbers for Cn?P3 and C3?Pm are obtained.For other Cn?Pm,this paper proposes better upper and lower bounds.