Irregular independence and irregular domination

DOI10.1016/J.DAM.2018.07.030MaRDI QIDQ2026322zbMATH OpenOpenAlexWikidataFDO

Authors Peter Borg, Yair Caro, Kurt Fenech

Publication date 19 May 2021

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

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

zbMATH Keywords

irregular dominating setirregular independent set

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)