Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T05:53:48.981Z Has data issue: false hasContentIssue false

Domination inequalities and dominating graphs

Published online by Cambridge University Press:  19 September 2024

DAVID CONLON
Affiliation:
Department of Mathematics, California Institute of Technology, Pasadena, CA 91125, U.S.A. e-mail:dconlon@caltech.edu
JOONKYUNG LEE
Affiliation:
Department of Mathematics, Yonsei University, Yonsei-ro 50, Seoul, South Korea. e-mail:joonkyunglee@yonsei.ac.kr
Rights & Permissions [Opens in a new window]

Abstract

We say that a graph H dominates another graph H′ if the number of homomorphisms from H′ to any graph G is dominated, in an appropriate sense, by the number of homomorphisms from H to G. We study the family of dominating graphs, those graphs with the property that they dominate all of their subgraphs. It has long been known that even-length paths are dominating in this sense and a result of Hatami implies that all weakly norming graphs are dominating. In a previous paper, we showed that every finite reflection group gives rise to a family of weakly norming, and hence dominating, graphs. Here we revisit this connection to show that there is a much broader class of dominating graphs.

Information

Type
Research Article
Copyright
© The Author(s), 2024. Published by Cambridge University Press on behalf of Cambridge Philosophical Society
Figure 0

Fig. 1.The graph $C_6^+$, which is dominating but not weakly norming.

Figure 1

Fig. 2.Different choices for $J_0$ in $C_6^+$.

Figure 2

Fig. 3.Relocations of the inner star $K_{1,3}$ and the outer cycle $C_6$ in $C_6^+$.

Figure 3

Fig. 4.Examples of $H_A^+$.