2025/07/24 by Hak, Artem, Kozerenko, Sergiy, Serdiuk, Andrii
#05C07 #05C99 #68T20 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.18776
We address the problem proposed by Chartrand, Erdős and Oellermann (1988) about the existence of regular K3-irregular graphs. We first establish bounds on the K3-degrees of such graphs and use them to prove that there are no such graphs with regularities at most 7. For the regularity 8, we narrow down the bounds on the order of such graphs to six possible values. We then present an explicit example of a 9-regular K3-irregular graph. Finally, we discuss an evolutionary algorithm developed to discover more examples of r-regular K3-irregular graphs for consecutive values r ∈ \9, …, 30\.