Paired-Domination in Claw-Free Cubic Graphs
Paired-Domination in Claw-Free Cubic Graphs
复制标题
DOI：
10.1007/s00373-004-0577-9
复制
发表时间：
2004-11
影响因子：
0.7
通讯作者：
O. Favaron;Michael A. Henning
中科院分区：
文献类型：
--
作者：
O. Favaron;Michael A. Henning
如果 G 的每个顶点都与 S 中的某个顶点相邻，并且如果由 S 导出的子图包含完美匹配，则图中的一组 S 顶点是 G 的成对支配集。 G 的成对支配集的最小基数是 G 的成对支配数，用 γpr(G) 表示。如果G不包含图F作为诱导子图，则称G是无F的。特别是如果F=K1,3或K4−e，那么我们分别说G是无爪或无金刚石。设 G 为 ordern 的连通立方图。我们证明 (i) 如果 G 是 (K1,3,K4−e,C4)-free，则 γpr(G)≤3n/8； (ii) 如果G无爪且无金刚石，则γpr(G)≤2n/5； (iii) 如果G无爪，则γpr(G)≤n/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 minimum cardinality of a paired-dominating set ofGis the paired-domination number ofG, denoted by γpr(G). IfGdoes not contain a graphFas an induced subgraph, thenGis said to beF-free. In particular ifF=K1,3orK4−e, then we say thatGis claw-free or diamond-free, respectively. LetGbe a connected cubic graph of ordern. We show that (i) ifGis (K1,3,K4−e,C4)-free, then γpr(G)≤3n/8; (ii) ifGis claw-free and diamond-free, then γpr(G)≤2n/5; (iii) ifGis claw-free, then γpr(G)≤n/2. In all three cases, the extremal graphs are characterized.