Some New Results on Global Dominating Sets

A dominating set is called a global dominating set if it is a dominating set of a graph and its complement . A natural question arises: are there any graphs for which it is possible to relate the domination number and the global domination number? We have found an affirmative answer to this question and obtained some graphs having such characteristic. 1. Introduction We begin with finite and undirected simple graph of order . The set of vertices in a graph is called a dominating set if every vertex is either an element of or is adjacent to an element of . A dominating set is a minimal dominating set (MDS) if no proper subset is a dominating set. The minimum cardinality of a dominating set of is called the domination number of which is denoted by and the corresponding dominating set is called a -set of . The open neighborhood of is the set of vertices adjacent to and the closed neighborhood of is the set . The complement of is the graph with vertex set and two vertices are adjacent in if and only if they are not adjacent in . A subset is called a global dominating set in if is a dominating set of both and . The global domination number is the minimum cardinality of a global dominating set in . The concept of global domination in graph was introduced by Sampathkumar [1]. The upper bounds of global domination number are investigated by Brigham and Dutton [2] as well as by Poghosyan and Zverovich [3], while the global domination number of Boolean function graph is studied by Janakiraman et al. [4]. The global domination decision problems are NP-complete as discussed by Carrington [5] and by Carrington and Brigham [6]. The edge addition stable property in the context of global domination and connected global domination for cycle and path is discussed by Kavitha and David [7]. The concept of total global dominating set was introduced by Kulli and Janakiram [8] and they have also characterized total global dominating sets. The wheel is defined to be the join . The vertex corresponding to is known as apex vertex and the vertices corresponding to cycle are known as rim vertices. A shell graph is the graph obtained by taking concurrent chords in a cycle . The vertex at which all the chords are concurrent is called the apex. The shell graph is also called fan that is, . Definition 1.1. The one-point union of cycles of length denoted by is the graph obtained by identifying one vertex of each cycle. The one-point union of cycles is known as friendship graph which is denoted by . Definition 1.2 (see Shee and Ho [9]). Let be a graph and let , be copies of a graph .