Applied Mathematics, 2011, 2, 12631269 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 Email: 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 2 11 if1mod2, 22 p p fp p p if there is a graph homomorphism from G onto then , p K .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 [1]. Let G be a graph. For disjoint non empty subsets , YVG, let , Y 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 G , then is called Hcolorable. Sup pose that is Hcolorable. Then every graph homo morphism also induces a map If for any graph homomorphism G V G :VG : eEG EH H . :VG VH , and for any 1, e 2 eEH, we always have 11 21 ee ee , then G is called edgeuniformly Hcolorable. Throughout this paper, we use Kp to denote the com plete graph with p vertices and 21 C to denote an odd cycle with 21p21 , pi VCvi Z and ,.v v 11iii Nv Theorem 1.1 (Erdös [2]) Let p ≥ 2 be an integer and mod 2, mod 2. 11if 0 22 2 11 if 1 22 p p fp p p 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 : q is the graph whose vertices repre
1264 S. H. FAN ET AL. sent the qsubsets of where two vertices are connected if and only if they correspond to disjoint subsets. 0,1,,1 ,p p q Theorem 1.2 Let , be two positive integers with p ≥ 2q. If there is a graph homomorphism from G onto : q , then 2. q bG EG p Let p and q be two positive integers with p ≥ 2q. The circulant graph / q is the graph with vertex set and the neighbors of vertex v are 0,1, 2,VG vq vq v p , 1 p ,1, . ,pq q Theorem 1.3 Let , be two positive integers with p ≥ 2q. If there is a graph homomorphism from G onto / q , then 2. q bG EG p Theorem 1.4 Let , be two positive integers with p ≥ 2q and let p q 22 22 44 ifis even, 221 ,441 ifis odd. 221 pqq p pp q fpq pqq p pp q If G is an edgeuniformly / q colorable, then ,.bGfpqEG A graph G is edgemaximal Hcolorable if G is Hcolorable but for any graph such that GG con tains G as a spanning subgraph with EG EG , G is not Hcolorable. 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 edgemaximal Kpcolorable. 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 edgemaximal / q colorable. In Subsection 3.5, we show a best possible lower bound for when G has a graph homomorphism onto an odd cycle 21 bG C and characterize the graphs reaching the lower bound among all edgemaximal 21 C colorable graphs. There are a lot of researches about graph homomorphism can be found in [37]. 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 , 11 SgSg . 2) For any sets and , if and only if CYDYCD 11 . CgD Lemma 2.2 If , SS is an edge cut of H, then 11 ,DS 1 S is an edge cut of G. Con sequently, 111 ,.DSS Proof. For each 1 S , 1 y S with yEG , by the definition of inverse image, S , and S . Hence, yxy D, and so 1 y D . It follows that 111 ,DSS 1 . Conversely, for each yD , , yx yDSS . We may assume that S and S . Then 1 S and S 1 y . This proves 111 ,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 ,,, k DD D 1 12 ,,, k DD 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 yxyEH . Since is an edge cut cover of H, then i yx y D for some i. It follows that D 1, i y D and so is an edge cut cover of G. By Lemma 2.1 2), i e if and only if D 1 i 1 eD 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 kedge cut at least lcover 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 kedge cut lcover of a graph H is a collection 12 ,,, k DD D , k D 12 of k edge cuts of H such that every edge of H lies in exactly l members of . A kedge cut average lcover of a graph H is a col lection ,,DD 12 , k D,,DD H of edge cuts of H such that 1 k i i DE and 1i iDlEH k. Lemma 2.4 Suppose that is an onto graph homo morphism from G to H and is a k 12 ,,, k DD D edge cut cover of H such that 1 k 1i i lE G . Copyright © 2011 SciRes. AM
S. H. FAN ET AL. 1265 Then . l bG EG k Proof. By Lemma 2, 11 1 12 ,,, k DD 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 l bG EG k follows from 1 1. k i i lEGD kbG Theorem 2.5 If one of the following is true, then . l bG EG k 1) There is a graph homomorphism from G onto H and H has a kedge cut lcover. 2) There is a graph homomorphism from G onto H and H has a kedge cut at least lcover. 3) G is edgeuniformly Hcolorable and H has a kedge cut average lcover. 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 edgemaximal Kpcolorable. Lemma 3.1 Let p ≥ 2 be an integer and let 2 p p , 22 2 pp k lp . Then the graph Kp has a kedge cut lcover. Proof. Let ,:is 2 \ pp XV KXX asubset of Then is an edge cut cover of Kp with . p VK .k 2 p p Since every \, p XV KX has size \X,pp XV K 22 p , and since , 2 p p EK every edge of Kp must be in exactly 22 2 pp k l p 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 . kl vvE G Theorem 3.2 Suppose that there is an onto graph ho momorphism from G to Kp and G is edge maximal Kpcolorable. Then each of the following holds. 1) ,bGfp EG where equality holds only if G is edgeuniformly Kpcolorable. 2) Among all edgemaximal Kpcolorable graph G, bGfpEG if and only if . ps GKK Proof. 1) By Theorem 1.1, bGfpEG. Sup pose that bG . Let fp EG :p VG VK be an arbitrarily given graph homomorphism and let 12 ,,, p VKvvv be labelled such that if 1 i V i v, then 12 . VV V For any subset , p XVK let \ p YVK X and let also de note the induced map Then EG :. p EK 11 ii ii vX vX vV and \YVG X 11 . Since G is an edgemaximal Kpcolorable, 111 ,, p KVG X Y XY is a complete bipartite graph. There are 2 p kp parti tions of VK into two parts ,,1,2,, ii , Yi k such that 01 ii YX . Set ,DXY iii . Label them so that 11 1 12 . k DD D By Lemma 2.2 and Lemma 2.3 and the assumption that ,bGfp EG 1k lEG bGD k and so 11 1 k ki i l kEGkDD lEG k , Copyright © 2011 SciRes. AM
1266 S. H. FAN ET AL. where 22 2 pp k lp . Therefore all the inequalities are equalities and so 11 1 12 . k DD D Let 12 1 2 1,,,,p ii i Xvvvv p vX with , Y \ p VK X and ,DXY . Let 1 \ p Xvv , and p YVK \X , .YDX Then 1D 1D . Since 11 2 11 2 111 1 1 p p ii pii DXY VV V VKV VV and 11 2 11 2 111 , p p pi i ppi i DXY VV V VKV VV it follows from 11 D D that 1 VV, and so 12 p VV Vs for some positive inte ger s, which implies G is edge uniformly Kpcolorable. 2) Suppose that G is an edgemaximal Kpcolorable graph such that .bGfpEG By the proof of 1), there is some positive integer s such that p GK Conversely, suppose that p GK . By Theorem 1.1, . pp s KbKsfp K It remains to show that for any partition , Y of s p KKV , ,. ps XYp KKf Let 12 ,, , VV V denote the partition of s p KKV such that for is an independent set of 1, 2i,, ,p i V p K . Let , Y be an edge cut of p s such that 1) , Y is maximized and subject to 1), 2) : ii iXY0 is minimized, where ii XV and i YYVi . Then we have the following claims: Claim 1. For each i, , 1ip 0. ii XY Otherwise, there is i such that 0. ii XY Let i mX X and i tYY, If m = t, let i XY and \i YYY Then , Y is an edge cut of p K such that ,, YXY and :0:0 iiii iXY iXY 1, contrary to the choice of , Y. Then . Without less of general ity, we may assume mt tm . Let i XY and .\ i YYY Then , Y is an edge cut of p K such that ,, , i,YXYtmYXY con trary to the choice of Y. , Claim 2. :: ii iVXiV Y1. Otherwise, :: ii iVXiV Y2. Choose and set i VX\i XV and . Then i YYV , Y is an edge cut such that 2 ,,:: 1 ,, ii YXYiVXiVY XY m contrary to the choice of , Y. By Claim 1 and Claim 2, we have 22 ,4 ps XY when p is even and 22 1 ,4 ps XY when p is odd, that is, ,. ps KXYfp 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 : q has a pedge cut 2qcover. Proof. For 0,1, ,1ip , let 0,1, 2,,1:and i VXp XqiX and , lii DVV. Then 1. 1 i p Vq By the definition of : q , is an independent sets of i V: q and is an edge cut of size i D 1 1 pp qq q . Then 01 1 ,,, p DD D is an edge cut cover of : q . Since : q has vertices and each of them is of degree p q pq q , :. 2 pq ppq qq EK Since each edge of : q is contained in Copyright © 2011 SciRes. AM
S. H. FAN ET AL. 1267 1 12 2 ppq p qq q ppq qq edges cuts, q:p has a pedge cut 2qcover. 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 [8]). If p ≤ 3q, then the maximum edge cut of :pq is induced by the maximum independent set of :pq and is of size 1. 1 pp qq 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 :pq when p ≤ 3q. Therefore, the bound in Theorem 1.2 is reached by :pq 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) / q has a pedge cut at least 2qcover. 2) / q has a pedge cut average 21 22 121 ppqq pq cover. Proof. For , let 0,1,,1ip ,1,,1 2 ip Vii and let , iii DVV . Then is an edge cut cover of 01 1 ,,, p DD D / q with 1. 22 ipp Dq q 1) Notice that for any edge / q euvK ,,,DDD , e lies in at least 2q members of , then / 01 1 p q has a pedge cut at least 2qcover. 2) Since 121 2 p q pp q EK , 0 / 1 22 21 22 121 p i i pq pp Dqqp ppqq EK pq and so / q has a pedge cut average 21 22 121 ppqq pq 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 edgemaximal graph such that is edge uniformly G G/ q colorable. Then / pq GK and ,.bGfpq EG Proof. Suppose that G is an edgemaximal graph such that G is edgeuniformly / q colorable. Then, / pq GK for some positive integer s. By Theorem 1.4, we have // , s qs pp bKf pKKqEK q . Now we prove that // , s qs pp bKf pKKqEK q . For 0,1, ,1 / q ipVK, let 1 i Vhi , where / : q G VKhV is an onto graph homomorphism from G to / q such that for any edge xy of G, qhxhy pq . By the definition of graph homomorphism, is an independent set. Let i V , Y be an edge cut of / pq K such that 1) , Y is maximized and subject to 1), 2) :0 ii iXY is mi nimized, where ii XV and . ii YYV Claim 1. For each i, 0 ii XY . Proof. Otherwise, there is i such that 0 ii XY . Since for each i vV i , either ii NvX Nv Y or ii NvXNvY . If the former is true, then \, , ii XY XXY, contradicting the choice of ,Y; if the latter is true, then ,\ , ii YY YXY, contradicting the choice of , Y. Assume that 1 m j i ij V and 2 ,,, m jj J let 1 j . 2 p J . Without loss of generality, we can assume that Let C be the cycle with vertex set / 0,1,, 12, q pVK , where i is adjacent to j if and only if p. Let p C distJ be the 1ij mo d hortest path of length of the s C which contains all the elements in J. Then 1. C distJ Claim 1. m 1 C dist Jm. ppose, tot Proof. Suar the contr 1 p C dist Jmy, tha. Let P be a path of C which contains all the elements Copyright © 2011 SciRes. AM
S. H. FAN ET AL. 1268 in endpoints of PJ and assume that 1 j, m j are the. Then there is \.kV J Let \m P m XV V and \. m Jj m T hen pp CC Jdist J dist and ,, XX rad Cl X , a contiction. aim 2. . 2 p m Proof. Suppose, to the cory, that ntra. 2 p m Let P be a path of C which contains all the J d assume that 1 j, m j are the endpoiP. Let elements in an nts of 1\ mp jVC P be such that V 1mm p jj EC . Let 1m XXV and 1m JJ j . Then 1p and 2 CC dist Jdist J ,, XXX , a contradiction. By the above discussion, wean calculate that c // raph , pq pq EKs . pq ss bK 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 ha o cycle 21 C and ch the graphs reaching aracterize the lower bound among all edgemaximal 21 Corable graphs. Theorem Suppose that there is an onto graph ho momorphism from G to 21 col 3.8 C . Then each of the fol lowing holds. 1) 2, 21 p bG EG p where equality holds only if G is edgeuniformly 21 Ccolorable. ong all edgemaxim2) Amal 21 Ccolorable graph G, 2pif an 21 bG EG p only if d 21 . s p GCK Proof. 1) Notice that 21 1)/(2)(2 pp CK , 2 21 p bG EG p follows from Toheorem 1.3. Nw suppose that 2 bG 21p momorphism 1 pEG . Let be an arbitrarily given graph ho 21 :p VG VC and for each 2 iZ , let 1 ii Vv . Set 1 , iii V , foWVr each 21 iZ . Since is a at graph homomorphism, we have 21pi iZ EG W . It follows th 2 0 i i E W may assume that G. We 021 min : ip WWiZ . Then  tion on we h 0 EG W is an edge cut of G, and so by the assumpave G, 2 01 21 p i i EG W W p . It fol 2pbGEG lows that 22 222 pp ii 01 1 ii pW Gp pE W . Hence 0112 2. p pWW WW By the choice of 0 , we must have 01 2p WW W. Let 0 mW . Then for any edge 21p eEC , 1em . Since is armly 1 bitrarily, then forG is edgeuni 2 C colorable. 2) Suppose that G is an edgem21 C aximal color le graph with ab 2 21 bG EG p . Let as in 1). Sin p be de ce G is an edgemaximal i W fined 21 C colorable graph, the subgraph induces byi is a W complete bipartite graph. Since 2p 21pEG, by 1), G is edgeuniformly bG 21 C  colorable, which means, 01 2 WW Where fore, T 01 2p VVV s for some positive integer o s and s21. s K p GC Conversely, suppose 21. s pKGC Note that 2 21m. spK 21p EC Then 2 and so it suffices to show t ubset 21 2pm ps K hat for bC any s 21 s p XKVC and 21 \ ps KCYV , Y , the edge cut of 21p C satisfies 2 ,2pmXY. Let , Y be an edge cut of 21p C such that 1) , Y is maximct to 1 ized and subje), 2) : i iXY mi0 i is minized, where ii XV and . ii YYV ince 12 , ii VV SiI iI , where 121 :is odd p I i and 221 :i p IiZi seven, n iZ is an edge cut with cardinality 2 pm2, the 1 i iI V Then we 2 2 ,,2pm. i iI XY V have the following claims: Claim 1. For each i, 0. ii XY Proof. Otherwise, there is i such that 0 ii XY . Let 11ii sX X and 1ii tYY 1 . If t, let i XY and \i YYY . Then , Y is an edge cut of m G such that ,,YX and Y Copyright © 2011 SciRes. AM
S. H. FAN ET AL. Copyright © 2011 SciRes. AM 1269 $ :0:01 iii i iXY iXY , c the ontrary to choice of , Y. Then t. . Le Withoss o ity, we ma s < tout lf general y assumet i X nd \Y a YY . Then , Y is an ech that dge cut of m G su ,, , i YX YtsY Y X , contrary to the choice of , Y. Claim 2. There is exactlyof con numbe one pair secutive r ,1ii pair of c in 0,1,,2 pwe consider (0 and 2p as a obers nsecutive num, too) such that 1ii X . Proof. By Claim 1 and the structure of 21p C , there exist sompair ofe numbers e consecutiv ,1ii in 0,1,, 2p such that 1ii X Since 2 ,2pmXY, then there is at most one pair of consecutive number ,1i in i 0,1,,2 p such that 1ii Xo and s By Claim 2, Claim 2 follows. 1 and Claim 2 ,2pm XY . 4. References [1] . Murty, “Graph Theory Applications,” American Elsevier, New York, 1976. ted s, Vol. 54, No. [2] P. Erdös, “Problems and Results in Graph Theory and Combinatorial Analysis,” Graph Theory and Rela Topics, Academic Press, New York, 1979. [3] M. O. Albertson and K. L. Gibbons, “Homomorphisms of 3Chromatic Graphs,” Discrete Mathematic 2, 1985, pp. 127132. doi:10.1016/0012365X(85)900731 [4] M. O. Albertson, P. A. Catlin and L. Gibbons, “Homo morphisms of 3Chromatic Graphs II,” Congressus Nu ies B, Vol. 45, No. merantium, Vol. 47, 1985, pp. 1928. [5] P. A. Catlin, “Graph Homomorphisms onto the 5Cycle,” Journal of Combinatorial Theory, Ser 2, 1988, pp. 199211. doi:10.1016/00958956(88)90069X [6] E. R. Scheinerman and Theory,” John Wiley Sons, Inc., New D. H. Ullman, “Fractional Graph York, 1997. l. 153, Combinatorics, Vol. 3, [7] G. G. Gao and X. X. Zhu, “StarExtremal Graphs and the Lexicographic Product,” Discrete Mathematics, Vo 1996, pp. 147156. [8] S. Poljak and Z. Tuza, “Maximum Bipartite Subgraphs of Kneser Graphs,” Graphs and 1987, pp. 191199. doi:10.1007/BF01788540 A. J. Bondy and U. S. R with
