Skip to content

Graphs without a partition into two proportionally dense subgraphs

Research output: Contribution to journalArticle

A proportionally dense subgraph (PDS) is an induced subgraph of a graph such that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the rest of the graph. In this paper, we study a partition of a graph into two proportionally dense subgraphs, namely a 2-PDS partition, with and without additional constraint of connectivity of the subgraphs. We present two infinite classes of graphs: one with graphs without a 2-PDS partition, and another with graphs that only admit a disconnected 2-PDS partition. These results answer some questions proposed by Bazgan et al. [Algorithmica 80(6)(2018), 1890–1908].
Original languageEnglish
Article number105877
Number of pages5
JournalInformation Processing Letters
Early online date31 Oct 2019
Publication statusPublished - Mar 2020


  • Graphs without a partition

    Accepted author manuscript (Post-print), 214 KB, PDF document

    Due to publisher’s copyright restrictions, this document is not freely available to download from this website until: 31/10/20

    Licence: CC BY-NC-ND

Related information

Relations Get citation (various referencing formats)

ID: 15777843