Upper paired-domination in claw-free graphs
Upper paired-domination in claw-free graphs
复制标题
DOI：
10.1007/s10878-009-9275-0
复制
发表时间：
2011-08
影响因子：
1
通讯作者：
Paul Dorbec;Michael A. Henning
中科院分区：
文献类型：
--
作者：
Paul Dorbec;Michael A. Henning
图G中的顶点集S是G的成对控制集，如果G的每个顶点都与S中的某个顶点相邻，如果S诱导的子图包含完美匹配。G的最小成对控制集的最大基数是G的上成对控制数，记为Γpr（G）.本文给出了连通无爪图G的Γpr（G）在给定最小度δ时，根据G的顶点数n的界.证明了当δ=1且n ≥3时，Γpr（G）≤ 4 n/5，当δ=2且n ≥6时，Γpr（G）≤ 3 n/4，当δ≥3时，Γpr（G）≤2n/3.所有这些界限都很清晰。进一步，当n ≥6时，刻画了图G达到上界Γpr（G）= 4 n/5，而当n ≥9时，刻画了图G达到上界Γpr（G）= 3 n/4，且δ=2.
A setSof vertices in a graphGis a paired-dominating set ofGif every vertex ofGis adjacent to some vertex inSand if the subgraph induced byScontains a perfect matching. The maximum cardinality of a minimal paired-dominating set ofGis the upper paired-domination number ofG, denoted by Γpr(G). We establish bounds on Γpr(G) for connected claw-free graphsGin terms of the numbernof vertices inGwith given minimum degreeδ. We show that Γpr(G)≤4n/5 ifδ=1 andn≥3, Γpr(G)≤3n/4 ifδ=2 andn≥6, and Γpr(G)≤2n/3 ifδ≥3. All these bounds are sharp. Further, ifn≥6 the graphsGachieving the bound Γpr(G)=4n/5 are characterized, while forn≥9 the graphsGwithδ=2 achieving the bound Γpr(G)=3n/4 are characterized.