Internal Partitions of Regular Graphs. Issue 1 (25th August 2015)

• Record Type: Journal Article
• Authors: Ban, Amir; Linial, Nati
• Is Part Of: Journal of graph theory. Volume 83:Issue 1(2016)
• Page Start: 5
• Page End: 18
• Publication Date: 2015-08-25
• Subjects: partition -- internal -- external -- regular -- cubic; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21909
• Languages: English
• ISSNs: 0364-9024

Abstract

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.