On three outer-independent domination related parameters in graphs

DOI10.1016/J.DAM.2021.01.027zbMATH Open1459.05243arXiv1812.10946OpenAlexW2907170473MaRDI QIDQ2656960FDOQ2656960

Authors: Doost Ali Mojdeh, Iztok Peterin, B. Samadi, Ismael G. Yero 

Publication date: 17 March 2021

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

Abstract: Let $G$ be a graph and let $SsubseteqV(G)$. The set $S$ is a double outer-independent dominating set of $G$ if $|N[v]capD|geq2$, for all $vinV(G)$, and $V(G)setminusS$ is independent. Similarly, $S$ is a $2$-outer-independent dominating set, if every vertex from $V(G)setminusS$ has at least two neighbors in $S$ and $V(G)setminusS$ is independent. Finally, $S$ is a total outer-independent dominating set if every vertex from $V(G)$ has a neighbor in $S$ and the complement of $S$ is an independent set. The double, total or $2$-outer-independent domination number of $G$ is the smallest possible cardinality of any double, total or $2$-outer-independent dominating set of $G$, respectively. In this paper, the $2$-outer-independent, the total outer-independent and the double outer-independent domination numbers of graphs are investigated. We prove some Nordhaus-Gaddum type inequalities, derive their computational complexity and present several bounds for them.

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

Recommendations

• Double outer-independent domination in graphs.
• Double outer-independent domination number of graphs
• On trees with double domination number equal to 2-domination number plus one
• Outer-2-independent domination in graphs
• Remarks on the outer-independent double Italian domination number

zbMATH Keywords

total outer-independent dominationNordhaus-Gaddum inequalitydouble outer-independent domination2-outer-independent domination

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Total domination in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A survey of Nordhaus-Gaddum type relations
• On Complementary Graphs
• Title not available (Why is that?)
• Independence, clique size and maximum degree
• Double outer-independent domination in graphs.
• A lower bound on the double outer-independent domination number of a tree

Cited In (9)

• Outer-2-independent domination in graphs
• Covering Italian domination in graphs
• Double outer-independent domination number of graphs
• Relating the outer-independent total Roman domination number with some classical parameters of graphs
• On the total version of the covering Italian domination problem
• New bounds on the double total domination number of graphs
• A note on total co-independent domination in trees
• Title not available (Why is that?)
• Double outer-independent domination in graphs.

This page was built for publication: On three outer-independent domination related parameters in graphs

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