TITLE:
The Maximum Size of an Edge Cut and Graph Homomorphisms
AUTHORS:
Suohai Fan, Hongjian Lai, Ju Zhou
KEYWORDS:
Maximum Edge Cuts, Graph Homomorphisms
JOURNAL NAME:
Applied Mathematics,
Vol.2 No.10,
October
14,
2011
ABSTRACT: For a graph G, let b(G)=max﹛|D|: Dis an edge cut of G﹜ . For graphs G and H, a map Ψ: V(G)→V(H) is a graph homomorphism if for each e=uv∈E(G), Ψ(u)Ψ(v)∈E(H). In 1979, Erdös proved by probabilistic methods that for p ≥ 2 with
if there is a graph homomorphism from G onto Kp then b(G)≥f(p)|E(G)| In this paper, we obtained the best possible lower bounds of b(G) for graphs G with a graph homomorphism onto a Kneser graph or a circulant graph and we characterized the graphs G reaching the lower bounds when G is an edge maximal graph with a graph homomorphism onto a complete graph, or onto an odd cycle.