Thumbnail

Graphs without a partition into two proportionally dense subgraphs

Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément (2020), Graphs without a partition into two proportionally dense subgraphs, Information Processing Letters, 155, p. 105877. 10.1016/j.ipl.2019.105877

View/Open
Type
Article accepté pour publication ou publié
Date
2020
Journal name
Information Processing Letters
Volume
155
Publisher
Elsevier
Pages
105877
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chlebíková, Janka
School of Computing [Portsmouth]
Dallard, Clément
School of Computing [Portsmouth]
Abstract (EN)
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. (2018).
Subjects / Keywords
Graph partition; Dense subgraph; Combinatorial problems