Block graphs with unique minimum dominating sets

DOI10.1016/S0012-365X(01)00196-0MaRDI QIDQ5948982zbMATH OpenOpenAlexFDO

Authors Miranca Fischermann

Publication date 29 March 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(01)00196-0

zbMATH Keywords

block graphcharacterizationsdominationunique dominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Review text

The author presents different characterizations of block graphs with unique minimum dominating sets. This is an interesting and non-trivial extension of a 1994 theorem by \textit{G. Gunther, B. Hartnell, L. R. Markus}, and \textit{D. Rall} [Congr. Numerantium 101, 55-63 (1994; Zbl 0836.05045)] for trees. One of the conditions leads to a linear time algorithm to check whether there exists a unique dominating set in a block graph.

Recommendations

• Graphs with unique minimum paired-dominating set.
• scientific article; zbMATH DE number 841590
• Vertices in all minimum paired-dominating sets of block graphs
• Maximum graphs with a unique minimum dominating set
• scientific article; zbMATH DE number 1416465

Cited in

(13)

• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• Unique minimum semipaired dominating sets in trees
• On accurate domination in graphs
• Unique irredundance, domination and independent domination in graphs
• The number of blocks of a graph with given minimum degree
• On unique minimum dominating sets in some repeated Cartesian products
• scientific article; zbMATH DE number 841590 (Why is no real title available?)
• More on the unimodality of domination polynomial of a graph
• Graphs with equal domination and certified domination numbers
• Graphs with unique minimum specified domination sets
• Some rainbow problems in graphs have complexity equivalent to satisfiability problems
• On unique minimum dominating sets in some Cartesian product graphs
• A characterization of block graphs

This page was built for publication: Block graphs with unique minimum dominating sets

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