Name
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)$$źpr(G). Let G be a connected $$\\{K_{1,3}, K_{4}-e\\}$${K1,3,K4-e}-free cubic graph of order n. We show that $$\\gamma _{pr}(G)\\le \\frac{10n+6}{27}$$źpr(G)≤10n+627 if G is $$C_{4}$$C4-free and that $$\\gamma _{pr}(G)\\le \\frac{n}{3}+\\frac{n+6}{9(\\lceil \\frac{3}{4}(g_o+1)\\rceil +1)}$$źpr(G)≤n3+n+69(ź34(go+1)ź+1) if G is $$\\{C_{4}, C_{6}, C_{10}, \\ldots , C_{2g_o}\\}$${C4,C6,C10,ź,C2go}-free for an odd integer $$g_o\\ge 3$$goź3; the extremal graphs are characterized; we also show that if G is a 2 -connected, $$\\gamma _{pr}(G) = \\frac{n}{3} $$źpr(G)=n3. Furthermore, if G is a connected $$(2k+1)$$(2k+1)-regular $$\\{K_{1,3}, K_4-e\\}$${K1,3,K4-e}-free graph of order n, then $$\\gamma _{pr}(G)\\le \\frac{n}{k+1} $$źpr(G)≤nk+1, with equality if and only if $$G=L(F)$$G=L(F), where $$F\\cong K_{1, 2k+2}$$FźK1,2k+2, or k is even and $$F\\cong K_{k+1,k+2}$$FźKk+1,k+2. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s10878-016-0033-9 | J. Comb. Optim. |
Keywords | Field | DocType |
Claw-free graphs,Cubic graphs,Domination,Paired-domination number,Regular graphs | Integer,Discrete mathematics,Graph,Combinatorics,Dominating set,Vertex (geometry),Cubic graph,Induced subgraph,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
33 | 4 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wei Yang | 1 | 1 | 1.37 |
| Xinhui An | 2 | 18 | 5.55 |
| Baoyindureng Wu | 3 | 99 | 24.68 |