Search Results

1 - 2 of 2 items

  • Author: Joanna Cyman x
Clear All Modify Search
On Accurate Domination in Graphs

Abstract

A dominating set of a graph G is a subset DVG such that every vertex not in D is adjacent to at least one vertex in D. The cardinality of a smallest dominating set of G, denoted by γ(G), is the domination number of G. The accurate domination number of G, denoted by γ a(G), is the cardinality of a smallest set D that is a dominating set of G and no |D|-element subset of VG \ D is a dominating set of G. We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees G for which γ a(G) = γ(G) are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.

Open access
Total Domination Versus Paired-Domination in Regular Graphs

Abstract

A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the minimum cardinalities of a total dominating set and paired-dominating set are the total domination number, γt(G), and the paired-domination number, γpr(G), respectively. For k ≥ 2, let G be a connected k-regular graph. It is known [Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012) 435–447] that γpr(G)/γt(G) ≤ (2k)/(k+1). In the special case when k = 2, we observe that γpr(G)/γt(G) ≤ 4/3, with equality if and only if GC 5. When k = 3, we show that γpr(G)/γt(G) ≤ 3/2, with equality if and only if G is the Petersen graph. More generally for k ≥ 2, if G has girth at least 5 and satisfies γpr(G)/γt(G) = (2k)/(k + 1), then we show that G is a diameter-2 Moore graph. As a consequence of this result, we prove that for k ≥ 2 and k ≠ 57, if G has girth at least 5, then γpr(G)/γt(G) ≤ (2k)/(k +1), with equality if and only if k = 2 and GC 5 or k = 3 and G is the Petersen graph.

Open access