Applied Mathematics

Volume 2, Issue 10 (October 2011)

ISSN Print: 2152-7385   ISSN Online: 2152-7393

Google-based Impact Factor: 0.83  Citations  

The Maximum Size of an Edge Cut and Graph Homomorphisms

HTML  Download Download as PDF (Size: 233KB)  PP. 1263-1269  
DOI: 10.4236/am.2011.210176    3,713 Downloads   6,342 Views  


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.

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.

Cited by

No relevant information.

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.