Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorChlebíková, Janka
dc.contributor.authorDallard, Clément
dc.date.accessioned2020-01-22T11:50:55Z
dc.date.available2020-01-22T11:50:55Z
dc.date.issued2020
dc.identifier.issn0020-0190
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20464
dc.language.isoenen
dc.subjectGraph partitionen
dc.subjectDense subgraphen
dc.subjectCombinatorial problemsen
dc.subject.ddc511en
dc.titleGraphs without a partition into two proportionally dense subgraphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenA 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).en
dc.relation.isversionofjnlnameInformation Processing Letters
dc.relation.isversionofjnlvol155en
dc.relation.isversionofjnldate2020-03
dc.relation.isversionofjnlpages105877en
dc.relation.isversionofdoi10.1016/j.ipl.2019.105877en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-01-22T11:45:38Z
hal.person.labIds989
hal.person.labIds499896
hal.person.labIds499896
hal.identifierhal-02448543*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record