The Maximum Size of an Edge Cut and Graph HomomorphismsReportar como inadecuado




The Maximum Size of an Edge Cut and Graph Homomorphisms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.





Autor: Suohai Fan, Hongjian Lai, Ju Zhou

Fuente: http://www.scirp.org/



DESCARGAR PDF




Documentos relacionados