Vertices in all minimum paired-dominating sets of block graphs

2009/08/20 by Lei Chen, Chen, Lei, Changhong Lü +3
Computer Science · #05C69 #05C85 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.0908.2883

openalex publication_date 2009/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G=(V,E) be a simple graph without isolated vertices. A set S⊆ V 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.

Related

• Labelling Algorithms for Paired-domination Problems in Block and Interval Graphs
• A Linear-Time Algorithm for the Weighted Paired-Domination Problem on Block Graphs
• Linear-Time Algorithms for the Paired-Domination Problem in Interval Graphs and Circular-Arc Graphs
• Paired domination in graphs with minimum degree four
• The Paired Domination Number of Cubic Graphs