## Domination dot-critical on a harary graph

#### Citation

Mojdeh, D. A., Mirzamani, S. ve Hasni, R. (2009). Domination dot-critical on a harary graph. Maltepe Üniveristesi. s. 141.#### Abstract

A set of vertices S in a graph G is a dominating set if every vertex of G−S is adjacent to some vertex of S. If S has the
smallest possible cardinality of any dominating set of G, then S is called a minimum dominating set-abbreviated MDS. The
cardinality of any MDS for G is called the domination number of G and is denoted by γ(G) [3]. More generally, we say that
a set of vertices A dominates the set B if every vertex of B − A is adjacent to some vertex in A. A vertex v of G is critical if
γ(G − v) < γ(G). A graph G is vertex-critical if every vertex of G is critical. We denote the set of critical vertices of G by
G0
. In [2], Burton et al. introduced a new critical condition for the domination number. A graph is domination dot-critical
(hereafter, just dot-critical) if identifying any two adjacent vertices (i.e., contracting the edge comprising those vertices)
results in a graph with smaller domination number. If identifying any two vertices of G causes the domination number to
decrease, then we say that G is totally dot-critical. For a pair of vertices a, b of G, we denote by G.ab the graph obtained
by indentifying a and b. When we say that G is k-edge-critical, k-vertex-critical, k-dot-critical, or totally-k-dot-critical, we
mean that it has the indicated property and that γ(G) = k, for more, see [1, 2, 5]. Given k ≤ n, place n vertices around a
circle, equally spaced. If k is even, form Hk,n by making each vertex adjacent to the nearest k
2
vertices in each direction
around the circle. If k is odd and n is even, form Hk,n by making each vertex adjacent to the nearest k−1
2
vertices in
each direction and to the diametrically opposite vertex. In each case, Hk,n is k-regular. When k and n are both odd we
construct Hk,n from Hk−1,n by adding an edge between vertices i and i+(n−1)
2
for each 1 ≤ i ≤
(n+1)
2
. The graph Hk,n
in each case is known as Harary graph H that V (G) = {1, 2, · · · , n} ([6]). Domination number in Harary graphs have
been studied in ([4]). In this note, we investigate the critical, dot-critical and totally dot-critical of the first type of Harary
graphs, that is, H2m,n(k = 2m).

#### Source

International Conference of Mathematical Sciences#### Collections

- Makale Koleksiyonu [586]

The following license files are associated with this item: