A Simple Algorithm to Find Dominating Set of Graphs and Properties of S-Polynomials

Abstract

Problem of finding a minimal dominating set and an independent set for a given graph has been of considerable interest due to its potential applications in various fields of computer science engineering and Chemical Structures. The computation of dominating set of a graph G, has been approached through many techniques. We approach this problem through a simple algorithm applied on the adjacency matrix of a graph G, by using the row sum operations and elimination of the vertices covered by a given vertex using the row elements. We use the dominating set to construct edge polynomials and the corresponding Buchberger-S pair polynomials are obtained.