 Applied Mathematics, 2011, 2, 1263-1269 doi:10.4236/am.2011.210176 Published Online October 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM The Maximum Size of an Edge Cut and Graph Homomorphisms Suohai Fan1, Hongjian Lai2, Ju Zhou3 1Department of Mat hem at i cs, JiNan University, Guangzhou, China 2Department of Mat hem at i cs, West Virginia University, Morgantown, USA 3Department of Mat hem at i cs, Kutztown University, Kutztown, USA E-mail: zhou@kutztown.edu Received November 2, 2010; revised July 5, 2011; accepted July 12, 2011 Abstract For a graph G, let max: is an edge cut of bGD DG. For graphs G and H, a map :VG VH is a graph homomorphism if for each euvEG , uvEH. In 1979, Erdös proved by prob-abilistic methods that for p ≥ 2 with 11 if0mod2,22 211 if1mod2,22ppfppp if there is a graph homomorphism from G onto then ,pK.bGfp EG In this paper, we obtained the best possible lower bounds of 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. bG Keywords: Maximum Edge Cuts, Graph Homomorphisms 1. Introduction In this paper, the graphs we consider are finite, simple and connected. Undefined notation and terminology will follow those in . Let G be a graph. For disjoint non-empty subsets ,XYVG, let ,XY denote the set of edges of G with one end in X and the other end in Y. For a subset , let SVGSVG\.S An edge cut of G is an edge subset of the form ,SSG for some nonempty proper subset . Define SVt of GmaxbG:is an edgeD D cu. For graphs G and H, a map :VG VH is a graph homomorphism if for each Geuv E , . If there is a graph homomorphism from to  uvEHGH, then is called H-colorable. Sup-pose that is H-colorable. Then every graph homo-morphism also induces a map If for any graph homomorphism GVG:VG :eEG EH H.:VG VH, and for any 1, e2eEH, we always have 1121eeee, then G is called edge-uniformly H-colorable. Throughout this paper, we use Kp to denote the com-plete graph with p vertices and 21pC to denote an odd cycle with 21p21 ,piVCvi Z and ,.v v11iiiNv  Theorem 1.1 (Erdös ) Let p ≥ 2 be an integer and mod 2,mod 2.11if 022 211 if 122ppfppp If there is a graph homomorphism from G onto Kp, then .bGfpEG Let p and q be two positive integers with p ≥ 2q. The Kneser graph :pqK is the graph whose vertices repre- 1264 S. H. FAN ET AL. sent the q-subsets of where two vertices are connected if and only if they correspond to disjoint subsets. 0,1,,1 ,pp qTheorem 1.2 Let , be two positive integers with p ≥ 2q. If there is a graph homomorphism from G onto :pqK, then  2.qbG EGp Let p and q be two positive integers with p ≥ 2q. The circulant graph /pqK is the graph with vertex set and the neighbors of vertex v are 0,1, 2,VGvqvq v p, 1p,1,.,pqqTheorem 1.3 Let , be two positive integers with p ≥ 2q. If there is a graph homomorphism from G onto /pqK, then  2.qbG EGp Theorem 1.4 Let , be two positive integers with p ≥ 2q and let p q 222244 ifis even,221,441ifis odd.221pqq ppp qfpq pqq ppp q If G is an edge-uniformly /pqK-colorable, then ,.bGfpqEG A graph G is edge-maximal H-colorable if G is H-colorable but for any graph such that GG con-tains G as a spanning subgraph with EG EG, G is not H-colorable. In Section 2, we prove an associate Theorem which will be used in the proofs of other theorems. In Subsec-tion 3.1, we give an alternative proof of Theorem 1.1 and characterize the graphs G reaching the lower bound in Theorem 1.1 when G is edge-maximal Kp-colorable. In Subsection 3.2, we show the validity and sharpness of Theorem 1.2. In Subsection 3.3, we show the validity of Theorem 1.3 and Theorem 1.4 and characterize the graphs G reaching the lower bound in Theorem 1.4 when G is edge-maximal /pqK-colorable. In Subsection 3.5, we show a best possible lower bound for when G has a graph homomorphism onto an odd cycle 21bGpC and characterize the graphs reaching the lower bound among all edge-maximal 21pC-colorable graphs. There are a lot of researches about graph homomorphism can be found in [3-7]. 2. An Associate Theorem In this section, we shall prove an associate Theorem which will be used in the proofs of other theorems. Throughout this section, we assume that G and H are two graphs and  is an onto graph homomorphism from G to H. Note that we can also view  as a map from EG to EH such that for each euvEG , euvEHSX. Lemma 2.1 Let g be a function between sets X and Y. Then 1) For any , 11SgSg. 2) For any sets and , if and only if CYDYCD11.gCgD Lemma 2.2 If ,DSS is an edge cut of H, then 11,DS1S is an edge cut of G. Con- sequently, 111,.DSSProof. For each 1xS, 1yS with xyEG, by the definition of inverse image, xS, and yS. Hence, xyxyD, and so 1xyD. It follows that  111,DSS1 . Conversely, for each xyD, ,xyxyDSS. We may assume that xS and yS. Then 1xS and S1y. This proves  111,DSS. Therefore,  111,DSS is an edge cut of G. By Lemma 2.1 1),  111,.DSSLemma 2.3 Suppose that is an edge cut cover of H. Then 12,,,kDD D112,,,kDD D11l is an edge cut cover of G. Moreover, if an edge e of H lies in exactly  members of , then every edge in 1e lies in exactly l members of .Proof. By the definition of graph homomorphism, for each , ex GyExyxyEH. Since is an edge cut cover of H, then ixyxyD for some i. It follows that D1,ixyD and so is an edge cut cover of G. By Lemma 2.1 2), ie if and only if D1i1eDl, and so if an edge e of H lies in ex-actly  members of , then every edge of 1e lies in exactly l members of . Let k, l be two positive integers. A k-edge cut at least l-cover of a graph H is a collection of k edge cuts of H such that every edge of H lies in at least l members of . A k-edge cut l-cover of a graph H is a collection 12,,,kDD D,kD12 of k edge cuts of H such that every edge of H lies in exactly l members of . A k-edge cut average l-cover of a graph H is a col-lection ,,DD12 ,kD,,DDH of edge cuts of H such that 1kiiDE and 1iiDlEHk. Lemma 2.4 Suppose that  is an onto graph homo-morphism from G to H and is a k 12,,,kDD Dedge cut cover of H such that 1k1iiDlEG. Copyright © 2011 SciRes. AM S. H. FAN ET AL. 1265Then  .lbG EGkProof. By Lemma 2,  11 112,,,kDD D   is an edge cut cover of G and for any edge e of H, if e lies in exactly -members of , then every edge of lies in exactly members of . Therefore, l1el  lbG EGk follows from 11.kiilEGD kbGTheorem 2.5 If one of the following is true, then  .lbG EGk 1) There is a graph homomorphism from G onto H and H has a k-edge cut l-cover. 2) There is a graph homomorphism from G onto H and H has a k-edge cut at least l-cover. 3) G is edge-uniformly H-colorable and H has a k-edge cut average l-cover. 3. Main Results 3.1. Graphs with a Graph Homomorphism onto a Complete Graph In this section, we present an alternative proof for Theo-rem 1.1 and determine all graphs G reaching the lower bound in Theorem 1.1 when G is edge-maximal Kp-colorable. Lemma 3.1 Let p ≥ 2 be an integer and let 2pp, 222ppklp. Then the graph Kp has a k-edge cut l-cover. Proof. Let ,:is 2\ppXV KXXa-subset of Then  is an edge cut cover of Kp with .pVK .k2pp Since every \, pXV KX has size \X,ppXV K22p, and since ,2ppEK  every edge of Kp must be in exactly 222ppklp members of . Thus, Theorem 1.3 follows from Theorem 2.5 1) and Lemma 3.1. The lower bound of Theorem 1.1 is best possible, in the sense that there exists a family of graphs such that the lower bound of Theorem 1.1 is reached. Let G and H be two graphs. The composition of G and H, denoted by GH, is the graph obtained from G by replacing each vertex of by Hi, a copy of H, and joining every vertex in Hk to every vertex in Hl if iGvV.klvvE G Theorem 3.2 Suppose that there is an onto graph ho-momorphism from G to Kp and G is edge maximal Kp-colorable. Then each of the following holds. 1) ,bGfp EG where equality holds only if G is edge-uniformly Kp-colorable. 2) Among all edge-maximal Kp-colorable graph G, bGfpEG if and only if .psGKK Proof. 1) By Theorem 1.1,  bGfpEG. Sup-pose that bG . Let fp EG:pVG VK be an arbitrarily given graph homomorphism and let 12,,,ppVKvvv be labelled such that if 1iViv, then 12 .pVV V For any subset ,pXVK let \pYVK X and let  also de-note the induced map Then EG:.pEK11iiiivX vXXvV and \YVG X11. Since G is an edge-maximal Kp-colorable,  111,,pKVGX YXY is a complete bipartite graph. There are 2pkp parti- tions of pVK into two parts ,,1,2,,ii ,XYi k such that 01iiYX. Set ,DXYiii. Label them so that 11 112 .kDD D  By Lemma 2.2 and Lemma 2.3 and the assumption that ,bGfp EG  1klEG bGDk and so  111kkiilkEGkDD lEGk , Copyright © 2011 SciRes. AM 1266 S. H. FAN ET AL. where 222ppklp. Therefore all the inequalities are equalities and so  11 112 .kDD D  Let 12 121,,,,pii iXvvvvpvX with , Y \pVK X and ,DXY. Let 1\pXXvv , and pYVK \X, .YDX Then  1D 1D. Since 11211211111ppiipiiDXYVV VVKV VV and  112112111,pppi ippi iDXYVV VVKV VV  it follows from  11DD that 1pVV, and so 12 pVV Vs for some positive inte-ger s, which implies G is edge uniformly Kp-colorable.2) Suppose that G is an edge-maximal Kp-colorable graph such that  .bGfpEG By the proof of 1), there is some positive integer s such that spGKK Conversely, suppose that spGKK. By Theorem 1.1, .ppsKbKsfp K It remains to show that for any partition ,XY of spKKV, ,.psXYp KKf Let 12,, ,pVV V denote the partition of spKKV such that for is an independent set of 1, 2i,, ,piVspKK. Let ,XY be an edge cut of pKs such that 1) ,XY is maximized and subject to 1), 2) :iiiXY0 is minimized, where iiXXV and iYYVi. Then we have the following claims: Claim 1. For each i, , 1ip 0.iiXY Otherwise, there is i such that 0.iiXY Let imX X and itYY, If m = t, let iXXY and \iYYY Then ,XY is an edge cut of spKK such that ,,XYXY and :0:0iiiiiXY iXY 1, contrary to the choice of ,XY. Then . Without less of general-ity, we may assume mttm. Let iXXY and .\ iYYY Then ,XY is an edge cut of spKK such that X,, ,i,YXYtmYXY con-trary to the choice of XY. ,Claim 2. ::iiiVXiV Y1. Otherwise, ::iiiVXiV Y2. Choose and set iVX\iXXV and . Then iYYV,XY is an edge cut such that 2,,:: 1,,iiXYXYiVXiVYXYm contrary to the choice of ,XY. By Claim 1 and Claim 2, we have 22,4psXY  when p is even and 221,4psXY  when p is odd, that is, ,.psKXYfp EK 3.2. Graphs with a Graph Homomorphism onto a Kneser Graph In this section, we shall show the validity and sharpness of Theorem 1.2. Theorem 3.3 Let p and q be two positive integers with p ≥ 2q. Then :pqK has a p-edge cut 2q-cover. Proof. For 0,1, ,1ip, let 0,1, 2,,1:andiVXp XqiX  and ,liiDVV. Then 1.1ipVq By the definition of :pqK, is an independent sets of iV:pqK and is an edge cut of size iD11ppqqq. Then 01 1,,,pDD D is an edge cut cover of :pqK. Since :pqK has vertices and each of them is of degree pqpqq, :.2pqppqqqEK Since each edge of :pqK is contained in Copyright © 2011 SciRes. AM S. H. FAN ET AL. 12671122ppqpqq qppqqq    edges cuts, q:pK has a p-edge cut 2q-cover. Proof of Theorem 1.2 Theorem 1.2 follows from Theorem 2.5 and Theorem 3.3. Theorem 3.4 (Poljak and Tuza, Theorem 2 in ). If p ≤ 3q, then the maximum edge cut of :pqK is induced by the maximum independent set of :pqK and is of size 1.1ppqqq Theorem 3.5 The bound in Theorem 1.2 is best possible.Proof. By Theorem 3.4, the edge cuts we choose in the proof of Theorem 4.1 are the maximum edge cuts of :pqK when p ≤ 3q. Therefore, the bound in Theorem 1.2 is reached by :pqK when p ≤ 3q. 3.3. Graphs with a Graph Homomorphism onto a Circulant Graph In this section, we verify the validity and sharpness of Theorem 1.3 and Theorem 1.4. Theorem 3.6 Let p and q be two positive integers with p ≥ 2q. Then the following hold. 1) /pqK has a p-edge cut at least 2q-cover. 2) /pqK has a p-edge cut average 2122121ppqqpq -cover. Proof. For , let 0,1,,1ip,1,,12ipVii and let ,iiiDVV. Then is an edge cut cover of 01 1,,,pDD D/pqK with 1.22ippDqq 1) Notice that for any edge /pqeuvK,,,DDD, e lies in at least 2q members of , then /01 1ppqK has a p-edge cut at least 2q-cover.2) Since 1212pqpp qEK , 0/1222122121piipqppDqqpppqqEKpq  and so /pqK has a p-edge cut average 2122121ppqqpq -cover. Proof of Theorem 1.3 Theorem 1.3 follows from Theorem 2.5 and Theorem 3.6 1). Proof of Theorem 1.4 Theorem 1.4 follows from Theorem 2.5 and Theorem 3.6 2). Theorem 3.7 Let be an edge-maximal graph such that is edge uniformly GG/pqK-colorable. Then /spqKGK and ,.bGfpq EG Proof. Suppose that G is an edge-maximal graph such that G is edge-uniformly /pqK-colorable. Then, /spqKGK for some positive integer s. By Theorem 1.4, we have //,sqsppbKf pKKqEKq. Now we prove that //,sqsppbKf pKKqEKq. For 0,1, ,1/pqipVK, let 1iVhi, where /:pqG VKhV is an onto graph homomorphism from G to /pqK such that for any edge xy of G, qhxhy pq. By the definition of graph homomorphism, is an independent set. Let iV,XY be an edge cut of /spqKK such that 1) ,XY is maximized and subject to 1), 2) :0iiiXY is mi-nimized, where iiXXV and .iiYYVClaim 1. For each i, 0iiXY .Proof. Otherwise, there is i such that 0iiXY. Since for each ivVi, either iiNvX Nv Y or iiNvXNvY. If the former is true, then \, ,iiXXY XXY, contradicting the choice of X,Y; if the latter is true, then ,\ ,iiXYY YXY, contradicting the choice of ,XY.Assume that 1mjiijXV and 2,,,mjj Jlet 1j. 2pJ. Without loss of generality, we can assume that Let pC be the cycle with vertex set /0,1,, 12,pqpVK , where i is adjacent to j if and only if  p. Let pCdistJ be the 1ij mo dhortest path of length of the spC which contains all the elements in J. Then 1.CdistJ Claim 1. m1Cdist Jm.ppose, tot Proof. Suar the contr1pCdist Jmy, tha. Let P be a path of pC which contains all the elements Copyright © 2011 SciRes. AM S. H. FAN ET AL. 1268 in endpoints of PJ and assume that 1j, mj are the. Then there is \.kV J Let \mPjmXXV V and \.mJJj m T henppCCJdist J distand ,,XXX radClX, a contiction. aim 2. .2pm Proof. Suppose, to the cory, that ntra.2pm Let P be a path of pC which contains all the J d assume that 1j, mj are the endpoiP. Let elements inan nts of 1\mpjVC P be such that V1mm pjj EC. Let 1mXXV and 1mJJ j. Then  1p and 2CCdist Jdist J,,XXXX, a contradiction. By the above discussion, wean calculate that c //raph,pqpq EKs .pq ssbK fKK 3.4. Graphs with a Graph Homomorphism onto an Odd Cycle for s a g homomorphism onto an dd In this section, we will show a best possible lower boundbG when G hao cycle 21pC and ch the graphs reaching aracterizethe lower bound among all edge-maximal 21pCorable graphs. Theorem Suppose that there is an onto graph ho-momorphism from G to 21-col 3.8 pC. Then each of the fol-lowing holds. 1)  2,21pbG EGp where equality holds only if G is edge-uniformly 21pC-colorable. ong all edge-maxim2) Amal 21pC-colorable graph G, 2pif an21bG EGp only if d 21 .spGCKProof. 1) Notice that 21 1)/(2)(2pppCK,  221pbG EGp follows from Toheorem 1.3. Nw suppose that  2bG 21pmomorphism 1pEG . Let be an arbitrarily given graph ho-21:pVG VC and for each 2piZ, let 1iiVv. Set 1,iiiV, foWVr each 21piZ. Since  is a at graph homomorphism, we have 21piiZEG W. It follows th20piiE Wmay assume that G. We 021min :ipWWiZ. Then - tion on we h0EG W is an edgecut of G, and so by the assumpave G, 20121piiEG W Wp. It fol-2pbGEG lows that  22222ppii011iipW GppE W. Hence 01122.ppWW WW By the choice of 0X, we must have 01 2pWW W. Let 0mW. Then for any edge 21peEC, 1em. Since  is armly 1bitrarily, then forG is edge-uni2pC-colorable.2) Suppose that G is an edge-m21pCaximal -color- le graph with ab221bG EGp. Letas in 1). Sinp be de- ce G is an edge-maximal iWfined 21pC-colorable graph, the subgraph induces byi is a Wcomplete bipartite graph. Since 2p21pEG, by 1), G is edge-uniformly bG 21pC- colorable, which means, 01 2pWW Where-fore, T01 2pVVV s  for some positive integer o s and s21.sKpGC Conversely, suppose 21.spKGC Note that 221m.spK21pEC Then 2 and so it suffices to show tubset 21 2pmpsK hat for bCany s21 spXKVC  and 21 \psKCYV,XYX , the edge cut  of 21psKC satisfies 2,2pmXY. Let ,XY be an edge cut of 21psKC such that 1) ,XY is maximct to 1 ized and subje), 2) :iiXY mi0i is minized, where iiXXV and .iiYYVince 12,iiVV SiI iI , where 121:is oddpI i and 221:ipIiZiseven, n iZis an edge cut with cardinality 2 pm2, the1iiIV Then we22,,2pm.iiIXY V have the following claims: Claim 1. For each i, 0.iiXY Proof. Otherwise, there is i such that 0iiXY . Let 11iisX X and 1iitYY1. If st, let iXXY and \iYYY. Then ,XY is an edge cut of mG such that ,,YX and YXCopyright © 2011 SciRes. AM S. H. FAN ET AL. Copyright © 2011 SciRes. AM 1269\$:0:01iii iiXY iXY  , c the ontrary tochoice of ,XY. Then st. . LeWithoss oity, we ma s < tout lf general-y assumet iXX nd \Y aiYYY. Then ,XY is an ech that  dge cut of mG su ,, ,iXYX YtsY Y X, contrary to the choice of ,XY. Claim 2. There is exactlyof con numbe one pair secutiver ,1iipair of c in 0,1,,2 pwe consider (0 and2p as a obers nsecutive num, too) such that 1iiXX. Proof. By Claim 1 and the structure of 21psKC, there exist sompair ofe numbers e consecutiv,1ii in 0,1,, 2p such that 1iiXX Since 2,2pmXY, then there is at most one pair of consecutive number ,1i in i0,1,,2 p such that 1iiXXo  and sBy Claim 2, Claim 2 follows. 1 and Claim2,2pm XY . 4. References  . Murty, “Graph TheoryApplications,” American Elsevier, New York, 1976. ted-s, Vol. 54, No.  P. Erdös, “Problems and Results in Graph Theory and Combinatorial Analysis,” Graph Theory and RelaTopics, Academic Press, New York, 1979.  M. O. Albertson and K. L. Gibbons, “Homomorphisms of 3-Chromatic Graphs,” Discrete Mathematic2, 1985, pp. 127-132. doi:10.1016/0012-365X(85)90073-1  M. O. Albertson, P. A. Catlin and L. Gibbons, “Homo-morphisms of 3-Chromatic Graphs II,” Congressus Nu-ies B, Vol. 45, No. merantium, Vol. 47, 1985, pp. 19-28.  P. A. Catlin, “Graph Homomorphisms onto the 5-Cycle,” Journal of Combinatorial Theory, Ser2, 1988, pp. 199-211. doi:10.1016/0095-8956(88)90069-X  E. R. Scheinerman and Theory,” John Wiley Sons, Inc., New D. H. Ullman, “Fractional Graph York, 1997. l. 153, Combinatorics, Vol. 3,  G. G. Gao and X. X. Zhu, “Star-Extremal Graphs and the Lexicographic Product,” Discrete Mathematics, Vo1996, pp. 147-156.  S. Poljak and Z. Tuza, “Maximum Bipartite Subgraphs of Kneser Graphs,” Graphs and1987, pp. 191-199. doi:10.1007/BF01788540 A. J. Bondy and U. S. R with