Explore chapters and articles related to this topic
Polynomials and graph homomorphisms
Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022
Delia Garijo, Andrew Goodall, Jaroslav Nešetřil, Guus Regts
A graph homomorphism profile of a graph G collects together as a single invariant of G the number of the H-colorings of G for a family of weighted graphs H. Graph homomorphism profiles play an important role in the recently developed theory of graph limits (see [795]). When restricted to certain families of graphs, such as complete graphs, graph homomorphism profiles may coincide with known polynomial graph invariants, such as the chromatic polynomial. This allows a unifying formulation of seemingly diverse questions such as whether a graph is chromatically unique, Tutte unique or spectrally unique. (See Chapter 6 and Chapter 11 for the topics of graphs uniquely determined, respectively, by their Tutte polynomial and by their chromatic polynomial.) Recently finite model theory has been used for a general construction of polynomial graph invariants from graph homomorphism profiles [561].
Approximate Methods for Calculating Marginals and Likelihoods
Published in Marloes Maathuis, Mathias Drton, Steffen Lauritzen, Martin Wainwright, Handbook of Graphical Models, 2018
A graph G′ $ G^{\prime } $ covers a graph G=(V,E) $ G = (V, E) $ if there exists a graph homomorphism h:G′→G $ h: G^{\prime } \rightarrow G $ such that for all vertices i∈G $ i\in G $ and all j∈h-1(i) $ j\in h^{-1}(i) $ , h maps the neighbors of j, denoted N(j), in G′ $ G^{\prime } $ bijectively to the neighborhood N(i) of i in G.
Rank 2 proximal Cantor systems are residually scrambled
Published in Dynamical Systems, 2018
For two directed graphs, G1 and G2, we say that ϕ: V(G1) → V(G2) is a graph homomorphism if for each (u, v) ∈ E(G1), it follows that (ϕ(u), ϕ(v)) ∈ E(G2). If ϕ is a graph homomorphism, then we write it as ϕ: G1 → G2. The graph homomorphism is edge surjective if { (ϕ(u), ϕ(v))∣(u, v) ∈ E(G1) } = E(G2). For a walk, w, in G1 and a graph homomorphism, ϕ: G1 → G2, we define a walk, ϕ(w), in G2 naturally. We say that a graph homomorphism, ϕ: G1 → G2, is bidirectional if for each (u, v1), (u, v2), (u1, v), (u2, v) ∈ E(G1), it follows that ϕ(v1) = ϕ(v2) and ϕ(u1) = ϕ(u2). A bidirectional edge surjective graph homomorphism is said to be a bidirectional cover.