Graph Theory Research

Abstract: We construct the d-regular graph with the maximum number of k-cycles for k = 5, 6.

Using a M ̈obius inversion relation between graph homomorphism numbers and injective homomorphism numbers, we reframe the problem as a continuous optimization problem on the eigenvalues of G by leveraging the fact that the number of closed walks of length k is tr(Ak ).
For k = 5 and d > 3, we show G is a collection of disjoint Kd+1 graphs. For d = 3, disjoint Petersen graphs emerge. For k = 6 and d large enough, G consists of copies of Kd,d.

Additionally, we introduce and give formulas for non-backtracking homomorphism numbers and backtracking homomorphism numbers, respectively. Moreover, we find the d-regular graph on n vertices with the most non-backtracking closed walks of length k by considering an optimization problem on the non-backtracking spectrum of G. We also solve the same problem, but for backtracking closed walks. A corollary gives a formula for the number of 4-cycles and 5-cycles of any graph in terms of its spectrum, regardless of regularity.
We conjecture that for odd k and sufficiently large d, the optimal G is a collection of Kd+1, while for even k with sufficiently large d, the optimal G consists of Kd,d.