[PDF][PDF] Upper paired domination versus upper domination

H Alizadeh, D Gözüpek - Discrete Mathematics & …, 2021 - dmtcs.episciences.org
Discrete Mathematics & Theoretical Computer Science, 2021dmtcs.episciences.org
A paired dominating set P is a dominating set with the additional property that P has a
perfect matching. While the maximum cardinality of a minimal dominating set in a graph G is
called the upper domination number of G, denoted by Γ (G), the maximum cardinality of a
minimal paired dominating set in G is called the upper paired domination number of G,
denoted by Γpr (G). By Henning and Pradhan (2019), we know that Γpr (G)≤ 2Γ (G) for any
graph G without isolated vertices. We focus on the graphs satisfying the equality Γpr (G)= 2Γ …
A paired dominating set P is a dominating set with the additional property that P has a perfect matching. While the maximum cardinality of a minimal dominating set in a graph G is called the upper domination number of G, denoted by Γ (G), the maximum cardinality of a minimal paired dominating set in G is called the upper paired domination number of G, denoted by Γpr (G). By Henning and Pradhan (2019), we know that Γpr (G)≤ 2Γ (G) for any graph G without isolated vertices. We focus on the graphs satisfying the equality Γpr (G)= 2Γ (G). We give characterizations for two special graph classes: bipartite and unicyclic graphs with Γpr (G)= 2Γ (G) by using the results of Ulatowski (2015). Besides, we study the graphs with Γpr (G)= 2Γ (G) and a restricted girth. In this context, we provide two characterizations: one for graphs with Γpr (G)= 2Γ (G) and girth at least 6 and the other for C3-free cactus graphs with Γpr (G)= 2Γ (G). We also pose the characterization of the general case of C3-free graphs with Γpr (G)= 2Γ (G) as an open question.
dmtcs.episciences.org
以上显示的是最相近的搜索结果。 查看全部搜索结果