Domination in partitioned graphs with minimum degree two

DOI10.1016/J.DISC.2006.07.024MaRDI QIDQ870974zbMATH OpenOpenAlexFDO

Authors Michael A. Henning, Preben Dahl Vestergaard

Publication date 15 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL http://vbn.aau.dk/ws/files/112711/abstractfil.pdf

zbMATH Keywords

3-subdivisionDominationPartitioned graphs

Mathematics Subject Classification ID

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

Review text

Let \(V_1\) and \(V_2\) be a partition of the vertex set in a graph \(G\). For \(i=1,2\), let \(\gamma_i\) denote the least number of vertices needed in \(G\) to dominate \(V_i\). It is known that if \(G\) has order \(n\) and minimum degree two, then \(\gamma_1+\gamma_2\leq 2n/3\). The contribution of this paper is the complete characterization of those graphs of order \(n\) which are edge minimal with respect to satisfying the conditions of connected, minimum degree at least two, and \(\gamma_1+\gamma_2=2n/3\).

Recommendations

• Domination in partitioned graphs
• Domination in bipartite graphs
• Publication:4489226
• Domination in graphs with minimum degree two
• Total domination in partitioned trees and partitioned graphs with minimum degree two

Cites work

• Bounds related to domination in graphs with minimum degree two
• Domination in graphs with minimum degree two
• Domination in partitioned graphs
• Graphs with large total domination number
• scientific article; zbMATH DE number 1055145 (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?)
• scientific article; zbMATH DE number 2061963 (Why is no real title available?)
• scientific article; zbMATH DE number 1472171 (Why is no real title available?)

Cited in

(12)

• Total domination in partitioned graphs
• Minimal dominating sets of cardinality two in a graph
• Distance domination in partitioned graphs
• Domination in graphs with minimum degree two
• scientific article; zbMATH DE number 1472171 (Why is no real title available?)
• Domination in partitioned graphs
• scientific article; zbMATH DE number 837049 (Why is no real title available?)
• Almost well-dominated bipartite graphs with minimum degree at least two
• Dominator partitions of graphs
• Partitioned graphs and domination related parameters
• Domination number in graphs with minimum degree two
• Total domination in partitioned trees and partitioned graphs with minimum degree two

This page was built for publication: Domination in partitioned graphs with minimum degree two

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