# Search Results

###### On Accurate Domination in Graphs

## Abstract

A dominating set of a graph *G* is a subset *D* ⊆ *V _{G}* 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

*V*\

_{G}*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.

###### 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*) ≤ (2

*k*)

*/*(

*k*+1). In the special case when

*k*= 2, we observe that γ

_{pr}(

*G*)

*/*γ

*(*

_{t}*G*) ≤ 4

*/*3, with equality if and only if

*G*≅

*C*

_{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*) = (2

*k*)

*/*(

*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*) ≤ (2

*k*)

*/*(

*k*+1), with equality if and only if

*k*= 2 and

*G*≅

*C*

_{5}or

*k*= 3 and

*G*is the Petersen graph.