23 March 2021 in RAIRO - Operations Research
For a graphG =(V(G),E(G)), an Italian dominating function (ID function)f:V(G) → {0,1,2} has the property that for every vertexv∈V(G) withf(v) = 0, eithervis adjacent to a vertex assigned 2 underforvis adjacent to least two vertices assigned 1 underf. The weight of an ID function is ∑v∈V(G)f(v). The Italian domination number is the minimum weight taken over all ID functions ofG. In this paper, we initiate the study of a variant of ID functions. A restrained Italian dominating function (RID function)fofGis an ID function ofGfor which the subgraph induced by {v ∈V(G) |f(v) = 0} has no isolated vertices, and the restrained Italian domination numberγrI(G) is the minimum weight taken over all RID functions ofG. We first prove that the problem of computing this parameter is NP-hard, even when restricted to bipartite graphs and chordal graphs as well as planar graphs with maximum degree five. We prove that γrI(T) for a treeTof ordern≥ 3 different from the double starS2,2can be bounded from below by (n+ 3)/2. Moreover, all extremal trees for this lower bound are characterized in this paper. We also give some sharp bounds on this parameter for general graphs and give the characterizations of graphsGwith small or largeγrI(G).
9 August 2021 in Bulletin of the Iranian Mathematical Society
1 December 2021 in Discrete Applied Mathematics
4 April 2024 in Bulletin of the Malaysian Mathematical Sciences Society
27 August 2020 in Discrete Mathematics & Theoretical Computer Science
The packing number of a graph $G$ is the maximum number of closed neighborhoods of vertices in $G$ with pairwise empty intersections. Similarly, the open packing number of $G$ is the maximum number of open neighborhoods in $G$ with pairwise empty intersections. We consider the packing and open packing numbers on graph products. In particular we give a complete solution with respect to some properties of factors in the case of lexicographic and rooted products. For Cartesian, strong and direct products, we present several lower and upper bounds on these parameters.Comment: 18 pages, 29 references
7 May 2019 in Discrete Applied Mathematics