Finding kcommunity structures in special graph classes
BP2STS
Published in:
 Discrete Applied Mathematics.  Elsevier BV.  2024, vol. 359, p. 159175
English
For an integer k ≥ 2, a kcommunity 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 give a necessary and sufficient condition for a forest on n vertices to admit a kcommunity structure. Furthermore, we provide an O(k^2 · n^2)time algorithm that computes such a kcommunity structure in a forest, if it exists. These results extend a result of Bazgan et al., 2018. We also show that if communities are allowed to have size one, then every forest with n ≥ k ≥ 2 vertices admits a kcommunity structure that can be found in time O(k^2 · n^2). We then consider threshold graphs and show that every connected threshold graph admits a 2community structure if and only if it is not isomorphic to a star; also if such a 2community structure exists, we explain how to obtain it in linear time. We further describe an infinite family of disconnected threshold graphs, containing exactly one isolated vertex, that do not admit any 2community structure. Finally, we present a new infinite family of connected graphs that may contain an even or an odd number of vertices without 2community structures, even if communities are allowed to have size one.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science and technology

License

CC BY

Open access status

hybrid

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/329097
Statistics
Document views: 7
File downloads: