Graphs without a partition into two proportionally dense subgraphs

Cristina Bazgan, Janka Chlebikova, Clément Dallard

Research output: Contribution to journalArticlepeer-review

43 Downloads (Pure)


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


  • graph partition
  • dense subgraph


Dive into the research topics of 'Graphs without a partition into two proportionally dense subgraphs'. Together they form a unique fingerprint.

Cite this