Paired-domination in claw-free cubic graphs

被引:64
作者
Favaron, O [1 ]
Henning, MA
机构
[1] Univ Paris 11, Rech Informat Lab, UMR 8623, F-91405 Orsay, France
[2] Univ KwaZulu Natal, Sch Math Stat & Informat Technol, ZA-3209 Scottsville, South Africa
关键词
bounds; claw-free cubic graphs; paired-domination;
D O I
10.1007/s00373-004-0577-9
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by gamma(pr)(G). If G does not contain a graph F as an induced subgraph, then G is said to be F - free. In particular if F = K-1,K-3 or K-4 - e, then we say that G is claw-free or diamond-free, respectively. Let G be a connected cubic graph of order n. We show that ( i) if G is (K-1,K-3, K-4 - e; C-4)-free, then gamma(pr)(G) less than or equal to 3n/8; (ii) if G is claw-free and diamond-free, then gamma(pr)(G) less than or equal to 2n/5; ( iii) if G is claw-free, then gamma(pr)(G) less than or equal to n/2. In all three cases, the extremal graphs are characterized.
引用
收藏
页码:447 / 456
页数:10
相关论文
共 15 条
[1]  
BERGE C, 1958, CR HEBD ACAD SCI, V247, P258
[2]  
Cockayne E. J., 2002, Journal of Combinatorial Mathematics and Combinatorial Computing, V43, P219
[3]   TOTAL DOMINATION IN GRAPHS [J].
COCKAYNE, EJ ;
DAWES, RM ;
HEDETNIEMI, ST .
NETWORKS, 1980, 10 (03) :211-219
[4]   Claw-free graphs - A survey [J].
Faudree, R ;
Flandrin, E ;
Ryjacek, Z .
DISCRETE MATHEMATICS, 1997, 164 (1-3) :87-147
[5]  
Favaron O, 2000, J GRAPH THEOR, V34, P9, DOI 10.1002/(SICI)1097-0118(200005)34:1<9::AID-JGT2>3.0.CO
[6]  
2-O
[7]  
FAVARON O, UNPUB BOUNDS TOTAL D
[8]  
Haynes T. W., 1998, FUNDAMENTALS DOMINAT
[9]  
Haynes T. W., 1998, FUNDAMENTALS DOMINAT
[10]  
Haynes TW, 1998, NETWORKS, V32, P199, DOI 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO