k-Extensibility and Weakly k-Extensibility in Generalized Petersen Graphs

Abstract

Let G be a simple graph. Let k be a positive integer. G is said to be k- extendable if every independent set of cardinality k is contained in a maximum independent set of G. A graph is weakly k- extendable if any non-maximal independent set of cardinality k is contained in a maximal independent set of G. Every k- extendable is weakly k- extendable but not the converse. Thus weakly k- extendable graph is a class of graphs wider than the class of k-extendable graphs. k-extendable and weakly k- extendable have been studied in [1, 2,3,4,6]. Characterization of graphs with β0 (G) = (n - 3), β0 (G) = (n - 2), and which is trivially extendable has been done in [5]. In this paper, we derive the some results on k-extensibility and weakly k-extensibility in generalized Petersen graphs. “Detection of emerging communities in a social network proves helpful to trace the growth of certain interests or interest groups. There are many community detection algorithms in the literature. However, they have the limitations of being too loose or they are not scalable – i.e., inextensible to large social networks. In this paper, we define a new property for the generalized Petersen Graphs namely k-Extensibility, which helps to find and visualize such communities.”