Skip to content
Back to outputs

Graphs without a partition into two proportionally dense subgraphs

Research output: Contribution to journalArticle

Standard

Graphs without a partition into two proportionally dense subgraphs. / Bazgan, Cristina; Chlebikova, Janka; Dallard, Clément.

In: Information Processing Letters, 31.10.2019.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Bibtex

@article{5d1b0ef7d1ba4fb2935d64c6d152a8ed,
title = "Graphs without a partition into two proportionally dense subgraphs",
abstract = "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].",
keywords = "graph partition, dense subgraph",
author = "Cristina Bazgan and Janka Chlebikova and Cl{\'e}ment Dallard",
year = "2019",
month = "10",
day = "31",
doi = "10.1016/j.ipl.2019.105877",
language = "English",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Graphs without a partition into two proportionally dense subgraphs

AU - Bazgan, Cristina

AU - Chlebikova, Janka

AU - Dallard, Clément

PY - 2019/10/31

Y1 - 2019/10/31

N2 - 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].

AB - 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].

KW - graph partition

KW - dense subgraph

U2 - 10.1016/j.ipl.2019.105877

DO - 10.1016/j.ipl.2019.105877

M3 - Article

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

ER -

ID: 15777843