Vertices in all minimum paired-dominating sets of block graphs

DOI10.1007/S10878-011-9375-5MaRDI QIDQ1928534zbMATH OpenOpenAlexWikidataFDO

Authors Lei Chen, Zhenbing Zeng, Changhong Lu

Publication date 3 January 2013

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

algorithmblock graphdominationpaired-dominationtree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Abstract: Let $G=(V,E)$ be a simple graph without isolated vertices. A set $SsubseteqV$ is a paired-dominating set if every vertex in $V-S$ has at least one neighbor in $S$ and the subgraph induced by $S$ contains a perfect matching. In this paper, we present a linear-time algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-dominating sets.

Recommendations

• Graphs with unique minimum paired-dominating set.
• Vertices contained in all or in no minimum paired-dominating set of a tree
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• A linear-time algorithm for weighted paired-domination on block graphs
• Labelling algorithms for paired-domination problems in block and interval graphs

Cites work

• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• Graphs with large paired-domination number
• Graphs with unique minimum paired-dominating set.
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• scientific article; zbMATH DE number 1185309 (Why is no real title available?)
• Labelling algorithms for paired-domination problems in block and interval graphs
• Paired-domination in claw-free cubic graphs
• Paired-domination in generalized claw-free graphs
• Paired-domination in graphs
• Paired-domination in inflated graphs
• Paired-domination of trees
• Vertices contained in all or in no minimum paired-dominating set of a tree
• Vertices contained in all or in no minimum total dominating set of a tree
• Vertices contained in every minimum dominating set of a tree

Cited in

(3)

• A linear-time algorithm for weighted paired-domination on block graphs
• Graphs with unique minimum paired-dominating set.
• Block graphs with unique minimum dominating sets

This page was built for publication: Vertices in all minimum paired-dominating sets of block graphs

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