Counting graph homomorphisms involving complete graphs

zbMATH Open1388.05090arXiv1903.06766MaRDI QIDQ4636243FDOQ4636243

Authors: Jeffrey Beyerl, C. Sharpe 

Publication date: 23 April 2018

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.

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

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

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)

Cited In (6)

• Counting Subgraphs via Homomorphisms
• Countable homogeneous multipartite graphs
• Enumeration of simple complete topological graphs
• Title not available (Why is that?)
• 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)