2020/05/04 by Hong Gao, Jiahuan Huang, Gao, Hong +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2005.01318
openalex publication_date 2020/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a graph G=(V,E), each vertex v∈ V is labelled with 0, 1 or 2 such that each vertex labelled with 0 is adjacent to at least one vertex labelled 2 or two vertices labelled 1. Such kind of labelling is called an Italian dominating function (IDF) of G. The weight of an IDF f is w(f)=∑v∈ Vf(v). The Italian domination number of G is γI(G)=minf w(f). Gao et al. (2019) have determined the value of γI(P(n,3)). In this article, we focus on the study of the Italian domination number of generalized Petersen graphs P(n, k), k≠3. We determine the values of γI(P(n, 1)), γI(P(n, 2)) and γI(P(n, k)) for k≥4, k≡2,3(\bmod5) and n≡0(\bmod5). For other P(n,k), we present a bound of γI(P(n, k)). With the obtained results, we partially solve the open problem presented by Brešar et al. (2007) by giving P(n,1) is an example for which γI=γr2 and characterizing P(n,2) for which γI(P(n,2))=γr2(P(n,2)). Moreover, our results imply P(n,1) (n≡0(\bmod 4)) is Italian, P(n,1) (n\not≡0(\bmod 4)) and P(n,2) are not Italian.