On three outer-independent domination related parameters in graphs

DOI10.1016/J.DAM.2021.01.027MaRDI QIDQ2656960zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

2-outer-independent dominationdouble outer-independent dominationNordhaus-Gaddum inequalitytotal outer-independent domination

Mathematics Subject Classification ID

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

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.

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

Cites work

• A lower bound on the double outer-independent domination number of a tree
• A survey of Nordhaus-Gaddum type relations
• Double outer-independent domination in graphs.
• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Independence, clique size and maximum degree
• On Complementary Graphs
• Total domination in graphs

Cited in

(12)

• New bounds on the double total domination number of graphs
• Relating the outer-independent total Roman domination number with some classical parameters of graphs
• Covering Italian domination in graphs
• Outer-2-independent domination in graphs
• Double outer-independent domination in graphs.
• scientific article; zbMATH DE number 2170481 (Why is no real title available?)
• Double outer-independent domination number of graphs
• On the total version of the covering Italian domination problem
• A note on total co-independent domination in trees
• Closed formulas for 2-domination and 2-outer-independent domination numbers of rooted product graphs
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)

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)