Cellular Networks Modeled by Distance Hereditary Graphs Are Maximum-Clique Perfect

Abstract

In modern cellular telecommunications systems, the entire service area of a country is divided into cells. Cells are normally thought of as hexagonal grids. One common method used to place transmitters for cellular telephones is to place them at the corner points of each hexagonal grid. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we show that cellular networks modeled by distance-hereditary graphs are maximum-clique perfect. The maximum-clique transversal number and the maximum-clique independence number of a distance hereditary graph can be computed in linear time.