English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For a fixed integer $k\ge 2$, a $k$-community structure in an undirectedgraph is a partition of its vertex set into $k$ sets called communities, eachof size at least two, such that every vertex of the graph has proportionally atleast as many neighbours in its own community as in any other community. Inthis paper, we give a necessary and sufficient condition for a forest on $n$vertices to admit a $k$-community structure. Furthermore, we provide an$O(n^{2})$-time algorithm that computes such a $k$-community structure in aforest, if it exists. These results extend a result of [Bazgan et al.,Structural and algorithmic properties of $2$-community structure, Algorithmica,80(6):1890-1908, 2018]. We also show that if communities are allowed to havesize one, then every forest with $n \geq k\geq 2$ vertices admits a$k$-community structure that can be found in time $O(n^{2})$. We then considerthreshold graphs and show that every connected threshold graph admits a$2$-community structure if and only if it is not isomorphic to a star; also ifsuch a $2$-community structure exists, we explain how to obtain it in lineartime. We further describe two infinite families of disconnected thresholdgraphs, containing exactly one isolated vertex, that do not admit any$2$-community structure. Finally, we present a new infinite family of connectedgraphs that may contain an even or an odd number of vertices without$2$-community structures, even if communities are allowed to have size one.

Finding $k$-community structures in special graph classes