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
JournalInformation Processing Letters
Publication statusAccepted for publication - 4 Oct 2019


  • Graphs without a partition

    Rights statement: The embargo end date of 2050 is a temporary measure until we know the publication date. Once we know the publication date the full text of this article will be able to view shortly afterwards.

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

    Due to publisher’s copyright restrictions, this document is not freely available to download from this website until: 1/01/50

    Licence: CC BY-NC-ND

Related information

Relations Get citation (various referencing formats)

ID: 15777843