Paired-domination in inflated graphs
The paper studies inflated graphs of graphs. If \(G\) is a graph, then the inflated graph \(G_I\) of \(G\) is defined. It is obtained from \(G\) by replacing each vertex \(x\) of \(G\) by a clique with the number of vertices equal to the degree of \(x\) in \(G\) and replacing each edge between two vertices by an edge joining vertices of these cliques, edges incident with one vertex being replaced by non-adjacent edges. A paired-dominating set of \(G\) is a subset \(S\) of the vertex set of \(G\) such that each vertex of \(G\) is in \(S\) or is adjacent to a vertex of \(S\) and, moreover, the subgraph of \(G\) induced by \(S\) contains a perfect matching. The minimum number of vertices of a paired-dominating set in \(G\) is the paired-domination number \(\gamma_p(G)\) of \(G\). The main result is the inequality \(n(G)\leq \gamma_p(G_I)\leq 4m(G)/[\delta(G)+ 1]\) for each graph \(G\) with \(\delta(G)\geq 2\). Here \(n(G)\), \(m(G)\), \(\delta(G)\) denote the number of vertices, the number of edges and the minimum degree of a vertex in \(G\). At the end of the paper inflated trees are studied. An algorithm for determining a minimum paired-dominating set in such a graph is described; it works in time \(O(n)\).
- Paired-domination in graphs
- Paired domination in graphs
- scientific article; zbMATH DE number 1156597
- Total domination in inflated graphs
- scientific article; zbMATH DE number 2188616
- Paired domination in graphs: a survey and recent results
- k-tuple total domination in inflated graphs
- Paired domination stability in graphs
- Paired domination versus domination and packing number in graphs
- Paired-domination in subdivided star-free graphs
- Graph theory
- scientific article; zbMATH DE number 1185309 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1156597 (Why is no real title available?)
- scientific article; zbMATH DE number 1506502 (Why is no real title available?)
- Inflated graphs with equal independence number and upper irredundance number
- Irredundance in inflated graphs
- Paired-domination
- Paired-domination in graphs
- Paired-domination of trees
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- Distance paired-domination problems on subclasses of chordal graphs
- On restricted edge-connectivity of replacement product graphs
- Vertices in all minimum paired-dominating sets of block graphs
- A proof of a conjecture on the paired-domination subdivision number
- A linear-time algorithm for weighted paired-domination on block graphs
- A linear-time algorithm for paired-domination on circular-arc graphs
- Paired domination in graphs
- scientific article; zbMATH DE number 1156597 (Why is no real title available?)
- scientific article; zbMATH DE number 1506502 (Why is no real title available?)
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
- Linear-time algorithm for paired-domination on distance-hereditary graphs
- Double domination number of inflated graphs
- An optimal algorithm for computing minimum k-hop dominating set of permutation graphs
- Coupon coloring number of inflated graphs
- Total domination in inflated graphs
This page was built for publication: Paired-domination in inflated graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596115)
