Paired-Domination in Subdivided Star-Free Graphs |
| |
Authors: | Paul Dorbec Sylvain Gravier |
| |
Institution: | 1. LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405, Talence, France 2. ERTé “Maths à modeler”, Institut Fourier, BP 74, 100 rue des maths, 38402, St. Martin d’Hères Cedex, France
|
| |
Abstract: | 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 paired-domination number of G, denoted by γ
pr(G), is the minimum cardinality of a paired-dominating set of G. In Dorbec P, Gravier S, Henning MA, J Comb Optim 14(1):1–7, 2007], the authors gave tight bounds for paired-dominating
sets of generalized claw-free graphs. Yet, the critical cases are not claws but subdivided stars. We here give a bound for
graphs containing no induced subdivided stars, depending on the size of the star. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|