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.
展开▼
机译:没有隔离顶点的图G =(V,E)的成对主导集合是其诱导子图具有完美匹配的主导顶点集合。 G的配对支配数,用γ pr sub>(G)表示,是G的配对支配集的最小基数。配对支配细分数sd γpr sub >(G)是必须细分的最小边数(G中的每个边最多可以细分一次),以增加配对对数。在本文中,我们确定了配对支配细分数的上限,并提出了一些问题和猜想。
展开▼