Issue |
RAIRO-Oper. Res.
Volume 59, Number 1, January-February 2025
|
|
---|---|---|
Page(s) | 239 - 249 | |
DOI | https://doi.org/10.1051/ro/2024218 | |
Published online | 16 January 2025 |
Characterizations of Italian graphs and Sicilian graphs
1
Universidad Nacional de Rosario, Rosario, Argentina
2
CONICET, Rosario, Argentina
* Corresponding author: aferrari@fceia.unr.edu.ar
Received:
16
April
2024
Accepted:
6
December
2024
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.
Mathematics Subject Classification: 05C69 / 05C75 / 05C85
Key words: Italian domination / {2}-domination / 2-domination / quasi-threshold graphs / cographs
© The authors. Published by EDP Sciences, ROADEF, SMAI 2025
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.