The Maximum Size of an Edge Cut and Graph HomomorphismsReport as inadecuate




The Maximum Size of an Edge Cut and Graph Homomorphisms - Download this document for free, or read online. Document in PDF available to download.

For a graph G, let bG=max﹛|D|: Dis an edge cut of G﹜ . For graphs G and H, a map Ψ: VG→VH is a graph homomorphism if for each e=uv∈EG, ΨuΨv∈EH. In 1979, Erdös proved by probabilistic methods that for p ≥ 2 with if there is a graph homomorphism from G onto Kp then bG≥fp|EG| In this paper, we obtained the best possible lower bounds of bG 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.

KEYWORDS

Maximum Edge Cuts, Graph Homomorphisms

Cite this paper

S. Fan, H. Lai and J. Zhou -The Maximum Size of an Edge Cut and Graph Homomorphisms,- Applied Mathematics, Vol. 2 No. 10, 2011, pp. 1263-1269. doi: 10.4236-am.2011.210176.





Author: Suohai Fan, Hongjian Lai, Ju Zhou

Source: http://www.scirp.org/



DOWNLOAD PDF




Related documents