Internal Partitions of Regular Graphs. Issue 1 (25th August 2015) - Ban, Amir; Linial, Nati
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.