Complexity of k-rainbow independent domination and some results on the lexicographic product of graphs

DOI10.1016/J.AMC.2018.12.009MaRDI QIDQ2008916zbMATH OpenOpenAlexWikidataFDO

Authors Simon Brezovnik, Tadeja Kraner Šumenjak

Publication date 26 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2018.12.009

zbMATH Keywords

algorithmcomplexitydominationlexicographic productNP-completeness

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Rainbow domination in the lexicographic product of graphs
• General upper bounds on independent \(k\)-rainbow domination
• Rainbow domination on trees
• Independent rainbow domination of graphs
• On the \(k\)-rainbow domination in graphs with bounded tree-width

Cites work

• \(k\)-domination and \(k\)-independence in graphs: A survey
• A proof of the conjecture regarding the sum of domination number and average eccentricity
• Algorithmic aspects of the \(k\)-domination problem in graphs
• Associative graph products and their independence, domination and coloring numbers
• Further results regarding the sum of domination number and average eccentricity
• Handbook of product graphs
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Independent domination in graphs: A survey and recent results
• On k-rainbow independent domination in graphs
• On the 2-rainbow domination in graphs
• On the ratio of the domination number and the independent domination number in graphs
• On the super domination number of lexicographic product graphs
• Rainbow domination in graphs
• Rainbow domination in the lexicographic product of graphs
• Rainbow domination on trees
• Some bounds on the p-domination number in trees
• Some remarks on lower bounds on the p-domination number in trees

Cited in

(13)

• Total domination in generalized prisms and a new domination invariant
• Independent rainbow domination of graphs
• Rainbow domination in the lexicographic product of graphs
• Rainbow domination in graphs
• On the \(k\)-rainbow domination in graphs with bounded tree-width
• A new upper bound on the independent 2-rainbow domination number in trees
• Complexity of 2-rainbow total domination problem
• Independent k -rainbow bondage number of graphs
• The 2-rainbow domination number of Cartesian bundles over cycles
• 2-rainbow independent domination in complementary prisms
• The 2-rainbow domination number of Cartesian product of cycles
• Double domination in lexicographic product graphs
• Rainbow domination on trees

This page was built for publication: Complexity of \(k\)-rainbow independent domination and some results on the lexicographic product of graphs

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