Irregular independence and irregular domination

DOI10.1016/J.DAM.2018.07.030zbMATH Open1464.05281arXiv1706.06820OpenAlexW2964067183WikidataQ129232305 ScholiaQ129232305MaRDI QIDQ2026322FDOQ2026322

Authors: Peter Borg, Yair Caro, Kurt Fenech 

Publication date: 19 May 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: If $A$ is an independent set of a graph $G$ such that the vertices in $A$ have different degrees, then we call $A$ an irregular independent set of $G$. If $D$ is a dominating set of $G$ such that the vertices that are not in $D$ have different numbers of neighbours in $D$, then we call $D$ an irregular dominating set of $G$. The size of a largest irregular independent set of $G$ and the size of a smallest irregular dominating set of $G$ are denoted by $alph{a}_{ir}(G)$ and $gamm{a}_{ir}(G)$, respectively. We initiate the investigation of these two graph parameters. For each of them, we obtain sharp bounds in terms of basic graph parameters such as the order, the size, the minimum degree and the maximum degree, and we obtain Nordhaus-Gaddum-type bounds. We also establish sharp bounds relating the two parameters. Furthermore, we characterize the graphs $G$ with $alph{a}_{ir}(G)=1$, we determine those that are planar, and we determine those that are outerplanar.

Full work available at URL: https://arxiv.org/abs/1706.06820

Recommendations

• Independent dominating sets in regular graphs
• Independent domination in regular graphs
• Extremely irregular graphs
• The size of maximally irregular graphs and maximally irregular triangle-free graphs
• scientific article; zbMATH DE number 850313

zbMATH Keywords

irregular dominating setirregular independent set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Lower bounds for constant degree independent sets
• Regular independent sets
• Fair domination in graphs
• \([1,2]\)-sets in graphs
• On Complementary Graphs
• Connected fair domination in graphs
• Locating-dominating sets and identifying codes in graphs of girth at least 5

Cited In (2)

• Irregular Domination Trees and Forests
• Irregular domination graphs

This page was built for publication: Irregular independence and irregular domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2026322)