| Autor: |
Bouquet, Valentin, Delbot, François, Picouleau, Christophe |
| Rok vydání: |
2020 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
Given a graph $G$ and a non trivial partition $(V_1,V_2)$ of its vertex-set, the satisfaction of a vertex $v\in 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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
