2024/03/20 by Zoltán Lóránt Nagy, Nagy, Zoltán Lóránt
Computer Science · Engineering · #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2403.13734
openalex publication_date 2024/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An internal or friendly partition of a vertex set V(G) of a graph G is a partition to two nonempty sets A∪ B such that every vertex has at least as many neighbours in its own class as in the other one. Motivated by Diwan's existence proof on internal partitions of graphs with high girth, we give constructive proofs for the existence of internal partitions in the incidence graph of projective planes and discuss its geometric properties. In addition, we determine exactly the maximum possible difference between the sizes of the neighbor set in its own class and the neighbor set of the other class, that can be attained for all vertices at the same time for the incidence graphs of desarguesian planes of square order.