The Maximum Size of an Edge Cut and Graph Homomorphisms

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 *K*_{p} 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.

For a graph

Cite this paper

nullS. 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.

nullS. Fan, H. Lai and J. Zhou, "The Maximum Size of an Edge Cut and Graph Homomorphisms,"

References

[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

[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