EDGE DOMINATION IN SOME BRICK PRODUCT GRAPHS

U. V. C. Kumar, R. Murali, A. Girisha

[PDF]

Abstract

Let G = (V;E) be a simple connected and undirected graph. A set F of edges in G is called an edge dominating set if every edge e in E - F is adjacent to at least one edge in F. The edge domination number 0 (G) of G is the minimum cardinality of an edge dominating set of G. The shadow graph of G, denoted D₂(G) is the graph constructed from G by taking two copies of G, say G itself and G^' and joining each vertex u' in G' to the neighbors of the corresponding vertex u 0 in G'. Let D be the set of all distinct pairs of vertices in G and let D_s (called the distance set) be a subset of D. The distance graph of G, denoted by D(G;D_s) is the graph having the same vertex set as that of G and two vertices u and v are adjacent in D(G;D_s) whenever d(u; v) ₂ Ds. In this paper, we determine the edge domination number of the shadow distance graph of the brick product graph C(2n; m; r).

Keywords

Dominating set, Brick product graph, Edge domination number, Minimal edge dominating set, Shadow distance graph.