Paired-Domination Subdivision Numbers of Graphs |
| |
Authors: | O Favaron H Karami S M Sheikholeslami |
| |
Institution: | 1.Univ Paris-Sud, LRI,Orsay,France;2.Department of Mathematics,Azarbaijan University of Tarbiat Moallem,Tabriz,Iran |
| |
Abstract: | A paired-dominating set of a graph G = (V, E) with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ
pr
(G), is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number
sd
γpr
(G) 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. In this paper we establish upper bounds
on the paired-domination subdivision number and pose some problems and conjectures. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|