Partition of graphs with maximum degree ratio

Abstract: Given a graph

G

and a non trivial partition

(V_{1}, V_{2})

of its vertex-set, the satisfaction of a vertex

v i n V_{i}

is the ratio between the size of it's closed neighborhood in

V_{i}

and the size of its closed neighborhood in

G

. The worst ratio over all the vertices defines the quality of the partition. We define

q (G)

the degree ratio of a graph as the maximum of the worst ratio over all the non trivial partitions. We give bounds and exact values of

q (G)

for some classes of graphs. We also show some complexity results for the associated optimization or decision problems.

This page was built for publication: Partition of graphs with maximum degree ratio