Partition of graphs with maximum degree ratio
The authors in this work are concerned with the important problem of partitioning the vertex set of a graph subject to certain constraints. Their problem is related to the degree ratio. First, the authors define what they mean by the satisfaction number of a vertex $v$ in $V_i$. This parameter is defined as the ratio of the size of the closed neighborhood of a vertex $v$ in one of the two partitions $V_1$ and $V_2$, say $v$ is in $V_i$ to the size of the closed neighborhood of $v$ in the whole of $G$. The degree ratio is then defined as the ratio of the largest worst ratio over all nontrivial partitions. The worst ratio over all the vertices then reveals the quality of the partition. In this article, the authors compute this degree ratio parameter for certain classes of graphs. They also derive certain NP completeness results for the family of regular graphs.
- Contagion
- Decomposing C₄-free graphs under degree constraints
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Graph theory
- scientific article; zbMATH DE number 944226 (Why is no real title available?)
- Internal partitions of regular graphs
- On partitions of \(K_{2, 3}\)-free graphs under degree constraints
- On stable cutsets in line graphs
- Recognizing decomposable graphs
- Satisfactory graph partition, variants, and generalizations
This page was built for publication: Partition of graphs with maximum degree ratio
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6945271)
