Domination dot-critical on a harary graph
Küçük Resim Yok
Tarih
2009
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Maltepe Üniversitesi
Erişim Hakkı
CC0 1.0 Universal
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/openAccess
Özet
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).
Açıklama
Anahtar Kelimeler
Kaynak
International Conference of Mathematical Sciences
WoS Q Değeri
Scopus Q Değeri
Cilt
Sayı
Künye
Mojdeh, D. A., Mirzamani, S. ve Hasni, R. (2009). Domination dot-critical on a harary graph. Maltepe Üniveristesi. s. 141.
