ON INVERTIBLE GRAPHS AND ITS PERFECTNESS

Abstract

Graph models of a system are applied for wireless sensor networks to solve problems in construction of communication infrastructure. Vertex cover is one of these techniques and it is quite useful when combined with the power of distributed nature of wireless sensor networks. A set S of vertices of a graph G=(V, E) is called a vertex cover, if each edge in E has at least one end point in S . The covering number of a graph is the cardinality of vertex cover of smallest size.  Kulli V.R. and Iyer. R.R introduced  inverse vertex covers in 2012. Our aim is to continue this study to present necessary and sufficient conditions for a graph to possess inverse vertex covers.This paper also relates the perfectness concept in graphs with invertibllity.

 

Keywords: Vertex Cover, Inverse Vertex Cover, Invertible Graphs, Perfect Graphs, Strongly Perfect Graphs.