Graphs with Large Italian Domination Number

Teresa W. Haynes, Michael A. Henning, Lutz Volkmann

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

An Italian dominating function on a graph G with vertex set V(G) is a function f: V(G) → { 0 , 1 , 2 } having the property that for every vertex v with f(v) = 0 , at least two neighbors of v are assigned 1 under f or at least one neighbor of v is assigned 2 under f. The weight of an Italian dominating function f is the sum of the values assigned to all the vertices under f. The Italian domination number of G, denoted by γI(G) , is the minimum weight of an Italian dominating of G. It is known that if G is a connected graph of order n≥ 3 , then γI(G)≤34n. Further, if G has minimum degree at least 2, then γI(G)≤23n. In this paper, we characterize the connected graphs achieving equality in these bounds. In addition, we prove Nordhaus–Gaddum inequalities for the Italian domination number.

Original languageEnglish
Pages (from-to)4273-4287
Number of pages15
JournalBulletin of the Malaysian Mathematical Sciences Society
Volume43
Issue number6
DOIs
Publication statusPublished - 1 Nov 2020

Keywords

  • 05C69
  • Domination
  • Italian domination
  • Roman domination
  • Roman { 2 } -domination

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Graphs with Large Italian Domination Number'. Together they form a unique fingerprint.

Cite this