Edge Domination in Some Path and Cycle Related Graphs

For a graph , a subset of is called an edge dominating set of if every edge not in is adjacent to some edge in . The edge domination number of is the minimum cardinality taken over all edge dominating sets of . Here, we determine the edge domination number for shadow graphs, middle graphs, and total graphs of paths and cycles. 1. Introduction The domination in graphs is one of the concepts in graph theory which has attracted many researchers to work on it because of its many and varied applications in such fields as linear algebra and optimization, design and analysis of communication networks, and social sciences and military surveillance. Many variants of dominating models are available in the existing literature. For a comprehensive bibliography of papers on the concept of domination, readers are referred to Hedetniemi and Laskar [1]. The present paper is focused on edge domination in graphs. We begin with simple, finite, connected, and undirected 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 (or 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 set is the closed neighborhood of . For any real number , denotes the smallest integer not less than and denotes the greatest integer not greater than . An edge of a graph is said to be incident with the vertex if is an end vertex of . In this case, we also say that is incident with . Two edges and which are incident with a common vertex are said to be adjacent. In a graph , a vertex of degree one is called a pendant vertex, and an edge incident with a pendant vertex is called a pendant edge. A subset is an edge dominating set if each edge in is either in or is adjacent to an edge in . An edge dominating set is called a minimal edge dominating set (or MEDS) if no proper subset of is an edge dominating set. The edge domination number is the minimum cardinality among all minimal edge dominating sets. The concept of edge domination was introduced by Mitchell and Hedetniemi [2] and it is explored by many researchers. Arumugam and Velammal [3] have discussed the edge domination in graphs while the fractional edge domination in graphs is discussed in Arumugam and Jerry [4]. The complementary edge domination in graphs is studied by Kulli and