Perfect matchings in paired domination vertex critical graphs

被引:1
作者
Huang, Shenwei [1 ]
Shan, Erfang [1 ]
Kang, Liying [1 ]
机构
[1] Shanghai Univ, Dept Math, Shanghai 200444, Peoples R China
关键词
Matching; Perfect matching; Factor-critical; Paired domination vertex critical; DIAMETER;
D O I
10.1007/s10878-010-9368-9
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
A vertex subset S of a graph G=(V,E) is a paired dominating set if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by gamma (pr) (G), is the minimum cardinality of a paired dominating set of G. A graph with no isolated vertex is called paired domination vertex critical, or briefly gamma (pr) -critical, if for any vertex v of G that is not adjacent to any vertex of degree one, gamma (pr) (G-v)<gamma (pr) (G). A gamma (pr) -critical graph G is said to be k-gamma (pr) -critical if gamma (pr) (G)=k. In this paper, we firstly show that every 4-gamma (pr) -critical graph of even order has a perfect matching if it is K (1,5)-free and every 4-gamma (pr) -critical graph of odd order is factor-critical if it is K (1,5)-free. Secondly, we show that every 6-gamma (pr) -critical graph of even order has a perfect matching if it is K (1,4)-free.
引用
收藏
页码:507 / 518
页数:12
相关论文
共 15 条
  • [1] Berge C, 1958, ACAD C R SCI PARI IM, V247, P258
  • [2] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
  • [3] Bicritical domination
    Brigham, RC
    Haynes, TW
    Henning, MA
    Rall, DF
    [J]. DISCRETE MATHEMATICS, 2005, 305 (1-3) : 18 - 32
  • [4] VERTEX DOMINATION CRITICAL GRAPHS
    BRIGHAM, RC
    CHINN, PZ
    DUTTON, RD
    [J]. NETWORKS, 1988, 18 (03) : 173 - 179
  • [5] EDWARDS M, 2006, THESIS U VICTORIA
  • [6] VERTEX DOMINATION-CRITICAL GRAPHS
    FULMAN, J
    HANSON, D
    MACGILLIVRAY, G
    [J]. NETWORKS, 1995, 25 (02) : 41 - 43
  • [7] The diameter of total domination vertex critical graphs
    Goddard, W
    Haynes, TW
    Henning, MA
    van der Merwe, LC
    [J]. DISCRETE MATHEMATICS, 2004, 286 (03) : 255 - 261
  • [8] Haynes T.W., 1998, Chapman & Hall/CRC Pure and Applied Mathematics
  • [9] Haynes TW, 1998, NETWORKS, V32, P199, DOI 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO
  • [10] 2-F