Share This Article:

The Maximum Size of an Edge Cut and Graph Homomorphisms

Abstract Full-Text HTML Download Download as PDF (Size:233KB) PP. 1263-1269
DOI: 10.4236/am.2011.210176    3,588 Downloads   6,262 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.

Conflicts of Interest

The authors declare no conflicts of interest.

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.


[1] A. J. Bondy and U. S. R. Murty, “Graph Theory with Applications,” American Elsevier, New York, 1976.
[2] P. Erd?s, “Problems and Results in Graph Theory and Combinatorial Analysis,” Graph Theory and RelatedTopics, Academic Press, New York, 1979.
[3] M. O. Albertson and K. L. Gibbons, “Ho-momorphisms of 3-Chromatic Graphs,” Discrete Mathe-matics, Vol. 54, No. 2, 1985, pp. 127-132. doi:10.1016/0012-365X(85)90073-1
[4] M. O. Albert-son, P. A. Catlin and L. Gibbons, “Homomorphisms of 3-Chromatic Graphs II,” Congressus Numerantium, Vol. 47, 1985, pp. 19-28.
[5] P. A. Catlin, “Graph Homo-morphisms onto the 5-Cycle,” Journal of Combinatorial Theory, Series B, Vol. 45, No. 2, 1988, pp. 199-211. doi:10.1016/0095-8956(88)90069-X
[6] E. R. Schei-nerman and D. H. Ullman, “Fractional Graph Theory,” John Wiley Sons, Inc., New York, 1997.
[7] G. G. Gao and X. X. Zhu, “Star-Extremal Graphs and the Lexico-graphic Product,” Discrete Mathematics, Vol. 153, 1996, pp. 147-156.
[8] S. Poljak and Z. Tuza, “Maximum Bi-partite Subgraphs of Kneser Graphs,” Graphs and Com-binatorics, Vol. 3, 1987, pp. 191-199. doi:10.1007/BF01788540

comments powered by Disqus

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.