On the semitotal domination number of line graphs

DOI10.1016/J.DAM.2018.06.010MaRDI QIDQ1720344zbMATH OpenOpenAlexFDO

Authors Chanjuan Liu, Enqiang Zhu

Publication date 8 February 2019

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

Full work available at URL https://doi.org/10.1016/j.dam.2018.06.010

zbMATH Keywords

upper boundline graphsNP-complete problemsemitotal domination number

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Semitotal domination subdivision numbers of graphs
• Semitotal domination in claw-free cubic graphs
• Semitotal domination in graphs
• Complexity and approximation ratio of semitotal domination in graphs
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width

Cites work

• scientific article; zbMATH DE number 3702724 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A survey of selected recent results on total domination in graphs
• Edge Dominating Sets in Graphs
• Graph theory
• Minimum Edge Dominating Sets
• On domination and independent domination numbers of a graph
• Semitotal domination in claw-free cubic graphs
• Semitotal domination in claw-free cubic graphs
• Semitotal domination in graphs

Cited in

(11)

• Semitotal bondage numbers of graphs
• Line-set domination in graphs
• Semitotal domination subdivision numbers of graphs
• Semitotal domination number of some graph operations
• An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph
• A characterization of graphs with semitotal domination number one-third their order
• Nordhaus-Gaddum-type results on the connected edge domination number
• Mixed domination and 2-independence in trees
• Trees with unique minimum semitotal dominating sets
• Complexity and characterization aspects of edge-related domination for graphs
• Edge weighting functions on the semitotal dominating set of claw-free graphs

This page was built for publication: On the semitotal domination number of line graphs

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