Internal Partitions of Regular Graphs

2013/07/19 by Amir Ban, Ban, Amir, Nati Linial +1 · 3 citations
Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1307.5246

openalex publication_date 2013/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An internal partition of an n-vertex graph G=(V,E) is a partition of V such that every vertex has at least as many neighbors in its own part as in the other part. It has been conjectured that every d-regular graph with n>N(d) vertices has an internal partition. Here we prove this for d=6. The case d=n-4 is of particular interest and leads to interesting new open problems on cubic graphs. We also provide new lower bounds on N(d) and find new families of graphs with no internal partitions. Weighted versions of these problems are considered as well.

Cited by

• On the Ban-Linial Conjecture
• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
• Bisection width, max-cut and internal partitions of 5-regular graphs

Related

• A note on internal partitions: the 5-regular case and beyond
• Asymptotically Almost Every 2r-regular Graph has an Internal Partition
• On the path partition number of 6-regular graphs
• Packing subdivisions into regular graphs
• Bisection width, max-cut and internal partitions of 5-regular graphs