错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Paired versus double domination in forbidden graph classes

  • Michael A. Henning,
  • Paras Maniya,
  • Dinabandhu Pradhan

摘要

A set D of vertices in a graph G is a dominating set of G if every vertex not in D has a neighbor in D, where two vertices are neighbors if they are adjacent. If the dominating set D of G has the additional property that the subgraph induced by D contains a perfect matching (not necessarily as an induced subgraph), then D is a paired dominating set of G. The paired domination number of G, denoted by \(\gamma _{pr}(G)\) γ pr ( G ) , is the minimum cardinality of a paired dominating set of G. A set \(D \subseteq V(G)\) D V ( G ) is a double dominating set of G if every vertex in \(V(G)\setminus D\) V ( G ) \ D has at least two neighbors in D, and every vertex in D has a neighbor in D. The double domination number of G, denoted by \(\gamma _{\times 2}(G)\) γ × 2 ( G ) , is the minimum cardinality of a double dominating set of G. Chellali and Haynes (Util Math 67:161–171, (2005)) showed that if G is a claw-free graph without isolated vertices, then the paired domination number of G is at most the double domination number of G. In this paper, we show that if G is a H-free graph for some \(H\in \{P_5, 2K_2\cup K_1, \text {fork}\}\) H { P 5 , 2 K 2 K 1 , fork } without isolated vertices, then \(\gamma _{pr}(G) \le \gamma _{\times 2}(G)\) γ pr ( G ) γ × 2 ( G ) .