首页 | 本学科首页   官方微博 | 高级检索  
     


Paired-domination number of claw-free odd-regular graphs
Authors:Wei Yang  Xinhui An  Baoyindureng Wu
Affiliation:1.College of Mathematics and System Sciences,Xinjiang University,Urumqi,People’s Republic of China
Abstract:A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph, denoted by (gamma _{pr}(G)). Let G be a connected ({K_{1,3}, K_{4}-e})-free cubic graph of order n. We show that (gamma _{pr}(G)le frac{10n+6}{27}) if G is (C_{4})-free and that (gamma _{pr}(G)le frac{n}{3}+frac{n+6}{9(lceil frac{3}{4}(g_o+1)rceil +1)}) if G is ({C_{4}, C_{6}, C_{10}, ldots , C_{2g_o}})-free for an odd integer (g_oge 3); the extremal graphs are characterized; we also show that if G is a 2 -connected, (gamma _{pr}(G) = frac{n}{3} ). Furthermore, if G is a connected ((2k+1))-regular ({K_{1,3}, K_4-e})-free graph of order n, then (gamma _{pr}(G)le frac{n}{k+1} ), with equality if and only if (G=L(F)), where (Fcong K_{1, 2k+2}), or k is even and (Fcong K_{k+1,k+2}).
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号