2025/05/03 by Csilla Bujtás, Bujtás, Csilla, Michael A. Henning +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2505.01815
A set S of vertices in a graph G is a paired dominating set if every vertex of G is adjacent to a vertex in S and the subgraph induced by S admits a perfect matching. The minimum cardinality of a paired dominating set of G is the paired domination number \gpr(G) of G. We show that if G is a graph of order~n and δ(G) ≥ 4, then \gpr(G) ≤ (10)/(17)n < 0.5883 n.