Abstract | ||
---|---|---|
A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. It was conjectured that the paired-domination subdivision number is at most
$$ n-1$$
for every connected graph G of order
$$n\ge 3$$
which does not contain isolated vertices. In this paper, we settle the conjecture in the affirmative. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1007/s00373-022-02472-4 | Graphs and Combinatorics |
Keywords | DocType | Volume |
Paired-domination number, Paired-domination subdivision number, 05C69 | Journal | 38 |
Issue | ISSN | Citations |
3 | 0911-0119 | 0 |
PageRank | References | Authors |
0.34 | 5 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zehui Shao | 1 | 119 | 30.98 |
Seyed Mahmoud Sheikholeslami | 2 | 0 | 0.34 |
Mustapha Chellali | 3 | 0 | 0.34 |
Rana Khoeilar | 4 | 0 | 0.34 |
Hossein Karami | 5 | 0 | 0.34 |