2025/06/13 by Grigoriy Blekherman, Annie Raymond, Blekherman, Grigoriy +5
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2506.12151
Understanding graph density profiles is notoriously challenging. Even for pairs of graphs, complete characterizations are known only in very limited cases, such as edges versus cliques. This paper explores a relaxation of the graph density profile problem by examining the homomorphism density domination exponent C(H1, H2). This is the smallest real number c ≥ 0 such that t(H1, T) ≥ t(H2, T)c for all target graphs T (if such a c exists) where t(H,T) is the homomorphism density from H to T. We demonstrate that infinitely many families of graphs are required to realize C(H1, H2) for all connected graphs H1, H2. We derive the homomorphism density domination exponent for a variety of graph pairs, including paths and cycles. As a couple of typical examples, we obtain exact values when H1 is an even cycle and H2 contains a Hamiltonian cycle, and provide asymptotically sharp bounds when both H1 and H2 are odd cycles.