We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A proof of a conjecture on the paired-domination subdivision number.
- Authors
Shao, Zehui; Sheikholeslami, Seyed Mahmoud; Chellali, Mustapha; Khoeilar, Rana; Karami, Hossein
- 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 ≥ 3 which does not contain isolated vertices. In this paper, we settle the conjecture in the affirmative.
- Subjects
LOGICAL prediction; DOMINATING set; GRAPH connectivity; CHARTS, diagrams, etc.
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02472-4