Finding k-community structures in special graph classes
share
For a fixed integer k≥ 2, a k-community structure in an undirected graph is a partition of its vertex set into k sets (called communities), each of size at least two, such that every vertex of the graph has proportionally at least as many neighbours in its own community as in any other community. In this paper, we present a necessary and sufficient condition for a forest F to admit a k-community structure, for any integer k≥ 2. Furthermore, if such a k-community exists, it can be found in polynomial time. This generalises a result of Bazgan et al. (2018), who showed that all trees of size at least four, except stars, admit a 2-community that can be found in polynomial time. We also show that, if communities are allowed to have size one, then every forest with at least k≥ 2 vertices admits a k-community structure that can be found in polynomial time. We then consider threshold graphs and show that every such connected graph admits a 2-community structure if and only if it is not isomorphic to a star; also, if such a 2-community structure exists, it can be found in polynomial time. Finally, we introduce a new infinite family of connected graphs that do not admit any 2-community structure (even if communities are allowed to have size one). Such a family was presented in Bazgan et al. (2020), but its graphs all contained an even number of vertices. The graphs in our new family may contain an even or an odd number of vertices.
READ FULL TEXT