 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 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 H-colorable. Sup- pose that is H-colorable. 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 edge-uniformly H-colorable. 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 q-subsets 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 edge-uniformly / q -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 / 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 edge-maximal 21 C -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 , 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 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 ,,, 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 k-edge cut average l-cover 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 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 2 p p , 22 2 pp k lp . Then the graph Kp has a k-edge cut l-cover. Proof. Let ,:is 2 \ pp XV KXX a-subset 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 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 . 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 edge-maximal Kp-colorable, 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 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 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 p-edge cut 2q-cover. 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 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 [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 p-edge cut at least 2q-cover. 2) / q has a p-edge 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 p-edge cut at least 2q-cover. 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 p-edge 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 edge-maximal graph such that is edge uniformly G G/ q -colorable. Then / pq GK and ,.bGfpq EG Proof. Suppose that G is an edge-maximal graph such that G is edge-uniformly / 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 edge-maximal 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 edge-uniformly 21 C-colorable. ong all edge-maxim2) Amal 21 C-colorable 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 edge-uni 2 C -colorable. 2) Suppose that G is an edge-m21 C aximal -color- le graph with ab 2 21 bG EG p . Let as in 1). Sin p be de- ce G is an edge-maximal i W fined 21 C -colorable graph, the subgraph induces byi is a W complete bipartite graph. Since 2p 21pEG, by 1), G is edge-uniformly 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 3-Chromatic Graphs,” Discrete Mathematic 2, 1985, pp. 127-132. doi:10.1016/0012-365X(85)90073-1 [4] 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. [5] P. A. Catlin, “Graph Homomorphisms onto the 5-Cycle,” Journal of Combinatorial Theory, Ser 2, 1988, pp. 199-211. doi:10.1016/0095-8956(88)90069-X [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, “Star-Extremal Graphs and the Lexicographic Product,” Discrete Mathematics, Vo 1996, pp. 147-156. [8] S. Poljak and Z. Tuza, “Maximum Bipartite Subgraphs of Kneser Graphs,” Graphs and 1987, pp. 191-199. doi:10.1007/BF01788540 A. J. Bondy and U. S. R with
|
