A Note on Internal Partitions: The 5-Regular Case and Beyond

Bärnkopf, Pál and Nagy, Zoltán Lóránt and Paulovics, Zoltán (2024) A Note on Internal Partitions: The 5-Regular Case and Beyond. GRAPHS AND COMBINATORICS, 40 (2). ISSN 0911-0119

Preview

Text s00373-024-02774-9.pdf - Published Version Available under License Creative Commons Attribution. Download (485kB) | Preview

Abstract

An internal or friendly partition of a graph is a partition of the vertex set into two nonempty sets so that every vertex has at least as many neighbours in its own class as in the other one. It has been shown that apart from finitely many counterexamples, every 3, 4 or 6-regular graph has an internal partition. In this note we focus on the 5-regular case and show that among the subgraphs of minimum degree at least 3 of 5-regular graphs, there are some which have small intersection. We also discuss the existence of internal partitions in some families of Cayley graphs, notably we determine all 5-regular Abelian Cayley graphs which do not have an internal partition.

Actions (login required)

Edit Item