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
TypeArticle accepté pour publication ou publié
Journal nameInformation Processing Letters
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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 / KeywordsGraph partition; Dense subgraph; Combinatorial problems
Showing items related by title and author.
Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément; Pontoizeau, Thomas (2019) Article accepté pour publication ou publié