Counting graph homomorphisms involving complete graphs

MaRDI QIDQ4636243zbMATH OpenFDO

Authors Jeffrey Beyerl, C. Sharpe

Publication date 23 April 2018

Full work available at URL https://arxiv.org/abs/1903.06766

zbMATH Keywords

graph homomorphismsedgesvertices

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30)

Abstract: In the branch of mathematics known as graph theory, graphs are considered as a set of points, called vertices, with connections between these points, called edges. The purpose of this paper is to study mappings between two graphs that have certain desirable properties, called graph homomorphisms, and the probability of such a mapping occurring. By using notions from graph theory and combinatorics, in this paper we prove several new theorems that place bounds on this probability for certain common classes of graphs such as Kn, and show that isolated vertices may safely be ignored.

Recommendations

• scientific article; zbMATH DE number 861321
• Extremal graphs for homomorphisms
• The bipartite swapping trick on graph homomorphisms
• scientific article; zbMATH DE number 929713
• scientific article; zbMATH DE number 3258853

Cited in

(6)

• Counting Subgraphs via Homomorphisms
• Countable homogeneous multipartite graphs
• scientific article; zbMATH DE number 6691415 (Why is no real title available?)
• Enumeration of simple complete topological graphs
• Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
• On counting homomorphisms to directed acyclic graphs

This page was built for publication: Counting graph homomorphisms involving complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636243)