
handle: 10397/629
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)\).
330, perfect matching, Inflated graphs, Domination, 004, Theoretical Computer Science, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), paired-domination number, Perfect matching, inflated graphs, domination, Computer Science(all)
330, perfect matching, Inflated graphs, Domination, 004, Theoretical Computer Science, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), paired-domination number, Perfect matching, inflated graphs, domination, Computer Science(all)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 23 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
