Isometric Cycle Transversal in Graphs and Networks

One of the fastest growing areas within graph theory is the study of covering and related subset problems such as packing and matching. In fact, there are scores of graph theoretic concepts involving covering and independence. A set S of vertices of a graph G is an isometric cycle transversal of G if every maximal isometric cycle of G contains at least one vertex of S. The minimum number of vertices required to form the isometric cycle transversal of G is called as the isometric cycle transversal number. It is denoted by ict(G). We determine a smallest isometric cycle transversal in certain interconnection networks such as meshes of trees, Butterfly networks. For the relevant graph invariant, some helpful generic bounds are established. We determine exact values of isometric cycle transversal of complete r-partite graphs and Cartesian products of 2 or 3 complete graphs. We also prove the NP-completeness of the isometric cycle transversal of a graph G. The realization results are obtained for the graphs with respect to the number of vertices and ict(G).