论文标题
最高程度比的图形分区
Partition of graphs with maximum degree ratio
论文作者
论文摘要
给定其顶点集的图形$ g $和一个非琐碎分区$（v_1，v_2）$，在v_i $中，顶点$ v \的满意度是其关闭邻居的大小与$ v_i $的封闭社区的大小与$ g $ In $ g $的封闭社区的大小之间的比例。所有顶点的最差比例定义了分区的质量。我们将图形的度比定义为所有非微不足道分区的最大比率的度比。我们给出某些图形类别的$ q（g）$的界限和精确值。我们还为相关的优化或决策问题显示了一些复杂性结果。
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.
