Characterizations of Italian graphs and Sicilian graphs

Abstract

In this work we deal with three variants of domination in graphs, these are Italian domination (or Roman {2}-domination), {2}-domination and 2-domination. We define Sicilian graphs as those graphs for which the Italian domination and the {2}-domination numbers coincide. Sicilian graphs constitute a superclass of Italian graphs (introduced by Klostermeyer and MacGillivray [J. Comb. Math. Comb. Comput. 108 (2019) 125–146]). First, we give a characterization of Italian graphs in terms of the existence of a special Roman {2}-dominating function. Then, we focus on web graphs for which their {2}-domination number was recently found (Cheng et al., Discrete Math. Algorithms App. 12 (2020) 2050055), and we study Sicilian web graphs. We explore also Sicilian co-bipartite graphs. As a by-product, we find the 2-domination number for web graphs and co-bipartite graphs. Finally, we show necessary conditions for non-Italian graphs to be Sicilian as well as characterize Sicilian graphs within some relevant graph classes such as quasi-threshold graphs and cographs.