Given a graph G and a non trivial partition <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10479_2025_6615_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">$(V_1,V_2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>V</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>V</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of its vertex-set, the satisfaction of a vertex <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10479_2025_6615_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$v\in V_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <msub> <mi>V</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> is the ratio between the size of it’s closed neighborhood in <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10479_2025_6615_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">$V_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> 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.

Partition of graphs with maximum degree ratio

期刊论文
发表日期：

2025年5月7日

查看全文

Valentin Bouquet,
François Delbot,
Christophe Picouleau

摘要

Given a graph G and a non trivial partition $(V_1,V_2)$ $(V_{1}, V_{2})$ of its vertex-set, the satisfaction of a vertex $v\in V_i$ $v \in V_{i}$ is the ratio between the size of it’s closed neighborhood in $V_i$ $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.