Italian domination in the Cartesian product of paths

Hong Gao (), Tingting Feng () and Yuansheng Yang ()
Additional contact information
Hong Gao: Dalian Maritime University
Tingting Feng: Dalian Maritime University
Yuansheng Yang: Dalian University of Technology

Journal of Combinatorial Optimization, 2021, vol. 41, issue 2, No 14, 526-543

Abstract: Abstract In a graph $$G=(V,E)$$ G = ( V , E ) , each vertex $$v\in V$$ v ∈ V is assigned 0, 1 or 2 such that each vertex assigned 0 is adjacent to at least one vertex assigned 2 or two vertices assigned 1. Such an assignment is called an Italian dominating function (IDF) of G. The weight of an IDF f is $$w(f)=\sum _{v\in V}f(v)$$ w ( f ) = ∑ v ∈ V f ( v ) . The Italian domination number of G is $$\gamma _{I}(G)=\min _{f} w(f)$$ γ I ( G ) = min f w ( f ) . In this paper, we investigate the Italian domination number of the Cartesian product of paths, $$P_n\Box P_m$$ P n □ P m . We obtain the exact values of $$\gamma _{I}(P_n\Box P_2)$$ γ I ( P n □ P 2 ) and $$\gamma _{I}(P_n\Box P_3)$$ γ I ( P n □ P 3 ) . Also, we present a bound of $$\gamma _{I}(P_n\Box P_m)$$ γ I ( P n □ P m ) for $$m\ge 4$$ m ≥ 4 , that is $$\frac{mn}{3}+\frac{m+n-4}{9}\le \gamma _{I}(P_{n}\Box P_{m})\le \frac{mn+2m+2n-8}{3}$$ mn 3 + m + n - 4 9 ≤ γ I ( P n □ P m ) ≤ m n + 2 m + 2 n - 8 3 where the lower bound is improved since the general lower bound is $$\frac{mn}{3}$$ mn 3 presented by Chellali et al. (Discrete Appl Math 204:22–28, 2016). By the results of this paper, together with existing results, we give $$P_n\Box P_2$$ P n □ P 2 and $$P_n\Box P_3$$ P n □ P 3 are examples for which $$\gamma _{I}=\gamma _{r2}$$ γ I = γ r 2 where $$\gamma _{r2}$$ γ r 2 is the 2-rainbow domination number. This can partially solve the open problem presented by Brešar et al. (Discrete Appl Math 155:2394–2400, 2007). Finally, Vizing’s conjecture on Italian domination in $$P_n\Box P_m$$ P n □ P m is checked.

Keywords: Italian domination; Cartesian product of graphs; Path; 05C69; 05C15 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00694-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:2:d:10.1007_s10878-020-00694-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00694-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().