2.3 Unrestricted k-Binomial-Colorable Graphs 1 While there cannot exist a k-regular k-binomial-colorable graph of order 2-1 for any odd integer k,there is,however,a (k+1)-regular k-binomial-colorable graph of order 2-I for every odd integer k>5.For a graph G and two disjoint subsets X and Y of V(G).let [X.Y]denote the set of edges joining a vertex of X and a vertex of Y. Proof.We begin with the k-cube having the edge coloring c described in the proof of Theorem 2.3.1.As in the proof of Theorem 2.3.1,the vertices of are labeled by the set of k-bit sequences.For 0se <k,let Ve be the set of the ( vertices of O whose k-bit labels have exactly e terms equal to 1.Thus,each set V is an independent set of vertices in Q.Hence.V()=V.For0ssk,let V={w.12…".⑤ each set Vare listed so that their labelsare in reverse eicogrhicalorde Fot a verte(in the vertex 元=(1-a1,1-a2,..,1-ak) is the complementary vertex of v.If v Vt,then Vi-t. Let F=-v be the graph of order 2-1 having 2-k-1 vertices of degreek and k vertices of degreek-1.From F,our goal is to construct a(k+1)-regulark e graph Gof or er 24 ere V(G)=V(F)and E(F)E(G) will then defin an edge cole ring co on G such that c (e) c(e)if e e E(F) and co(v)= c(v)for each V(G).For this purpose,it is useful to consider the diagram in Fig.2.8 showing the general structure of the graph G to be constructed We now describe the construction of this graph (as well as the notation in Fig.2.8) as follows. Letk=2p+l,where then p≥2.For1≤e≤p-l,let H be the(的-1) graph of th omplement F of Fw with partit ets Ve and V 、gia31 nmdiq3 aiesH3ouS"A3aa3yMas约8p阳3pJ0u0u8 it contains a perfect matching M.All the matchings Me(1 s<p-1)are then added to F.For each edge xy in M.there is at least one term i in the k-bit sequences ofx and y that both equal I(since x and y are not complementary vertices).In this case,the edge xy is colored i by co.resulting in co(x)=c'(x)and co(y)=c'(y). The subgraph F=F[V U V+]is a (p+1)-regular bipartite subgraph of F with partite sets Vp and V+wherep=p=().Let H be the bipartite subgraph of F with partite sets V and V+having edge set E(Hp)=[Vp.Vp+i]-E(Fp)-vE Vpl
2.3 Unrestricted k-Binomial-Colorable Graphs 17 While there cannot exist a k-regular k-binomial-colorable graph of order 2k 1 for any odd integer k, there is, however, a .kC1/-regular k-binomial-colorable graph of order 2k 1 for every odd integer k 5. For a graph G and two disjoint subsets X and Y of V.G/, let ŒX; Y denote the set of edges joining a vertex of X and a vertex of Y. Theorem 2.3.3 ([27]). For each odd integer k 5, there exists a .k C 1/-regular k-binomial-colorable graph of order 2k 1. Proof. We begin with the k-cube Qk having the edge coloring c described in the proof of Theorem 2.3.1. As in the proof of Theorem 2.3.1, the vertices of Qk are labeled by the set of k-bit sequences. For 0 ` k, let V` be the set of the k ` vertices of Qk whose k-bit labels have exactly ` terms equal to 1. Thus, each set V` is an independent set of vertices in Qk. Hence, V.Qk/ D Sk `D0 V`. For 0 ` k, let V` D n v`;1; v`;2;:::;v`;.k `/ o ; where the vertices of each set V` are listed so that their labels are in reverse lexicographical order. For a vertex v D .a1; a2;:::; ak/ in Qk, the vertex v D .1 a1; 1 a2;:::;1 ak/ is the complementary vertex of v. If v 2 V`, then v 2 Vk`. Let F D Qkvk;1 be the graph of order 2k1 having 2kk1 vertices of degree k and k vertices of degree k 1. From F, our goal is to construct a .k C 1/-regular kbinomial-colorable graph G of order 2k 1 where V.G/ D V.F/ and E.F/ E.G/. We will then define an edge coloring c0 on G such that c0.e/ D c.e/ if e 2 E.F/ and c0 0.v/ D c0 .v/ for each v 2 V.G/. For this purpose, it is useful to consider the diagram in Fig. 2.8 showing the general structure of the graph G to be constructed. We now describe the construction of this graph (as well as the notation in Fig. 2.8) as follows. Let k D 2p C 1, where then p 2. For 1 ` p 1, let H` be the . k ` 1/- regular bipartite subgraph of the complement F of F with partite sets V` and Vk` containing none of the edges vv, where v 2 V`. Since H` is a regular bipartite graph, it contains a perfect matching M`. All the matchings M` (1 ` p 1) are then added to F. For each edge xy in M`, there is at least one term i in the k-bit sequences of x and y that both equal 1 (since x and y are not complementary vertices). In this case, the edge xy is colored i by c0, resulting in c0 0.x/ D c0 .x/ and c0 0.y/ D c0 .y/. The subgraph Fp D FŒVp [ VpC1 is a .p C 1/-regular bipartite subgraph of F with partite sets Vp and VpC1, where jVpjDjVpC1j D 2pC1 p . Let Hp be the bipartite subgraph of F with partite sets Vp and VpC1 having edge set E.Hp/ D ŒVp; VpC1 E.Fp/ fvv W v 2 Vpg:
18 2 Binomial Edge Colorings 0-0…00● -2 V+2 V M.CHp Hp-15 Mp 1 0-1 HM -3= 巧 6:● Since H is a)-p-2)-regular bipartite graph.H has a perfect matching M.This matching is also added to F.Each edgeMp has at least one termiin the k-bit sequences ofx and y that both equal 1.The edge xry is colored i by co. At this stage,each vertex of the graph currently constructed has degree k+1 except for each of the k =2p+1 vertices in V-and the single vertex in Vo has degree k. To complete the construction of G.we add p+1 edges to F,namely (1)thep edges 1.2 nd (2) 2i Io ach of the ges x) escn bed in(1)there is at east e term colored k by co.Thus.co(x)=c(x)and co(y)=c(y)for all these added edges xy in G.The vertices vo.and v-are drawn as solid vertices.Consequently,co is a k-binomial coloring of G and so G is a (k +1)-regular k-binomial-colorable graph of order 2-1
18 2 Binomial Edge Colorings • • • . • ... ........... ................ ... .. ........ ... . ............... ... ........... ................ ... .. ........ ... • • • ............... • • • • .......... . . .. .. ............ ......... ......... . . . . .. .. ............ ........ .......... .......... .......... .......... .......... .......... .......... .......... ........... . . ........................ .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ........ .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ........... . . ........................ .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .............. .......... .......... .......... .......... .......... .......... .......... .......... ......... . . . . .. .. ............ ........ .......... .......... .......... .......... .......... .......... .......... .......... .......... ......... . . . . .. .. ............ ........ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . .. .. ... ... ... ... ... ... .... .......... . . ......................... .......... . . ......................... V0 : V1 V2 Vk−1: Mp ⊂ Hp H1⊃ M1 M2⊂ H2 Vk−2 Vp+2 Vp−1 Vp Vp+1 Hp−1 ⊃ Mp−1 Fig. 2.8 The structure of a .k C 1/-regular k-binomial-colorable graph G of order 2k 1 in Theorem 2.3.3 Since Hp is a 2pC1 p p 2 -regular bipartite graph, Hp has a perfect matching Mp. This matching is also added to F. Each edge xy 2 Mp has at least one term i in the k-bit sequences of x and y that both equal 1. The edge xy is colored i by c0. At this stage, each vertex of the graph currently constructed has degree k C 1 except for each of the k D 2p C 1 vertices in Vk1 and the single vertex in V0 has degree k. To complete the construction of G, we add p C 1 edges to F, namely (1) the p edges vk1;2i1vk1;2i for i D 1; 2; : : : ; p and (2) the edge v0;1vk1;k. For each of the p added edges xy described in (1), there is at least one term i in the k-bit sequences of x and y that both equal 1. The edge xy is colored i by c0 and the edge v0;1vk1;k is colored k by c0. Thus, c0 0.x/ D c0 .x/ and c0 0.y/ D c0 .y/ for all these added edges xy in G. The vertices v0;1 and vk1;k are drawn as solid vertices. Consequently, c0 is a k-binomial coloring of G and so G is a .k C 1/-regular k-binomial-colorable graph of order 2k 1. ut
Chapter 3 Kaleidoscopic Edge Colorings eused t ibe.Suppose that a hard-line network of n computers is to be constructed.Each of these computers requires k different types of connections.There are r locations on the back of each computer at which ports can be placed.Each computer needs to have at least one connection of each type and.for security reasons,no two computers can have more than one connection between them.In order to maximize the number of fail-safe connections eous for a comp ble to dist uish the ters based o on the of type connections they have.For which values such a situation possible? 3.1 Introduction A well-known observation in graph theory concerning the degrees of the vertices of a graph is that every nontrivial gr same degree.Indeed,it isk vertices having the for rn≥2，the e are two gra即 ns of order nhaving exactly two 1e e degree an the two graphs are complements of each other.Consequently,in any decomposition of the complete graph K of order n into two graphs,necessarily into a graph G and its complement C.there are at least two vertices u and v such that deg u=degv(and so degu=degv as well).In particular,for every decomposition of a complete 点e城aaCn each vertex y of an c ordered pair(b)of pos sitive inte with a =deg eth amrI not only m v.Consequently,fo ition of K.the of the complete graph into two graphs but decompositions of every regular graph ©The Author2016 19 P.Zhang,A Kaleie
Chapter 3 Kaleidoscopic Edge Colorings In this chapter, we consider an edge coloring problem in graphs that can be used to model certain situations, one of which we now describe. Suppose that a hard-line network of n computers is to be constructed. Each of these computers requires k different types of connections. There are r locations on the back of each computer at which ports can be placed. Each computer needs to have at least one connection of each type and, for security reasons, no two computers can have more than one connection between them. In order to maximize the number of fail-safe connections, every port is to be used. Furthermore, it is advantageous for a computer technician to be able to distinguish the computers based only on the number of types of connections they have. For which values of n; k and r is such a situation possible? 3.1 Introduction A well-known observation in graph theory concerning the degrees of the vertices of a graph is that every nontrivial graph contains at least two vertices having the same degree. Indeed, it is known that for every integer n 2, there are exactly two graphs of order n having exactly two vertices of the same degree and these two graphs are complements of each other. Consequently, in any decomposition of the complete graph Kn of order n into two graphs, necessarily into a graph G and its complement G, there are at least two vertices u and v such that degG u D degG v (and so degG u D degG v as well). In particular, for every decomposition of a complete graph Kn into two graphs G1 and G2 (where then G2 D G1) such that each vertex of Kn is incident with at least one edge in each of G1 and G2, there is associated with each vertex v of Kn an ordered pair .a; b/ of positive integers with a D degG1 v and b D degG2 v. Consequently, for each such decomposition of Kn, there are at least two vertices with the same ordered pair. In fact, this is not only true of decompositions of the complete graph into two graphs but decompositions of every regular graph © The Author 2016 P. Zhang, A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, DOI 10.1007/978-3-319-30518-9_3 19
20 3 Kaleidoscopic Edge Colorings into two graphs.Indeed,for a given regular graph G.there is a question of whether ther graphs G.G G such that (1 on ph G:and (2) fo and of G.d By as ng the concept,first introduced in [28]. For an r-regular graph G,letc:E(G→={l,2,,k,k≥3，bean edge coloring of G.where every vertex of G is incident with at least one edge of each color.Thus,r>k.For a vertex v of G,the set-color c (v)of v is defined as the set of colors of the edges incident with v.Thus,c(v)=[]for every vertex v of G That is each such edge colori of G induces ertex coloring of G.Th color ()ofis defined s the or aid2. ak,where a(1≤ ≤)ish orde of edges in Gcolored a are inciden with v. Hence,eac ai is a positive integer and =1ai r.Suc an edge coloring c is called a k-kaleidoscopic coloring of G if cm(u)cm(v) for every two distinct vertices u and v of G.That is,each such edge coloring of G induces a multiset-irregular vertex coloring of G.An edge coloring of G is a kaleidoscopic coloring if it is a k-kaleidoscopic coloring for some integer k 3. Thus.a kaleidoscopic coloring is both set-regular and multiset-irregular.A reg cope if G ha ak-kaleidos copic coloring.Fis 3.1 s a 6-r ular 3-kaleidoso ope G of order 8 toge ith a3-kaleidosc oring of G.where the multiset-co of a vertex v is I ndicated inside the vertex It is sometimes useful to look at kaleidoscopic colorings from another point of view.For a connected graph G of order n>3 and a k-tuple factorization 多={Fi,F2,…,F}ofG,where each F,has no isolated vertices for I≤i≤k,we associate the ordered k-tuple aa2..a with a vertex v of G where dege.v =a;for ik.Thus =degr=degc v.If distinct vertices have distinct k-tuples 14 231 --2 3 12 1 321 213 Fig 3.1 A 6-regular 3-kaleidoscope Gof order 8
20 3 Kaleidoscopic Edge Colorings into two graphs. Indeed, for a given regular graph G, there is a question of whether there exists a decomposition of G into k 3 graphs G1; G2;:::; Gk such that (1) each vertex of G is incident with at least one edge of every graph Gi and (2) for every two vertices u and v of G, degGi u ¤ degGi v for some i. By assigning the color i (1 i k) to each edge of Gi, we are led to the following graph coloring concept, first introduced in [28]. For an r-regular graph G, let c W E.G/ ! Œk D f1; 2; : : : ; kg, k 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. Thus, r k. For a vertex v of G, the set-color cs.v/ of v is defined as the set of colors of the edges incident with v. Thus, cs.v/ D Œk for every vertex v of G. That is, each such edge coloring of G induces a set-regular vertex coloring of G. The multiset-color cm.v/ of v is defined as the ordered k-tuple .a1; a2;:::; ak/ or a1a2 ::: ak, where ai (1 i k) is the number of edges in G colored i that are incident with v. Hence, each ai is a positive integer and Pk iD1 ai D r. Such an edge coloring c is called a k-kaleidoscopic coloring of G if cm.u/ ¤ cm.v/ for every two distinct vertices u and v of G. That is, each such edge coloring of G induces a multiset-irregular vertex coloring of G. An edge coloring of G is a kaleidoscopic coloring if it is a k-kaleidoscopic coloring for some integer k 3. Thus, a kaleidoscopic coloring is both set-regular and multiset-irregular. A regular graph G is called a k-kaleidoscope if G has a k-kaleidoscopic coloring. Figure 3.1 shows a 6-regular 3-kaleidoscope G of order 8 together with a 3-kaleidoscopic coloring of G, where the multiset-color of a vertex v is indicated inside the vertex v. It is sometimes useful to look at kaleidoscopic colorings from another point of view. For a connected graph G of order n 3 and a k-tuple factorization F D fF1; F2; ; Fkg of G, where each Fi has no isolated vertices for 1 i k, we associate the ordered k-tuple a1a2 ak with a vertex v of G where degFi v D ai for 1 i k. Thus Pk iD1 degFi v D degG v. If distinct vertices have distinct k-tuples, 141 411 231 312 321 213 123 222 1 2 3 Fig. 3.1 A 6-regular 3-kaleidoscope G of order 8
3.2 Complete Kaleidoscopes 2 then we can assign the color i(1 ……ak.l this case,the factorization is called irregular.Conversely,every k-kaleidoscopic coloring of G gives rise to an irregular k-tuple factorization=(F1.F2.....F of G where the edges of F;are those edges of G colored i and each F;has no isolated vertices for 1<i<k.Hence.an edge coloring of a graph G is a kaleidoscopic coloring if and only if the corresponding factorization of G is irregular.Therefo Ghas a k-kaleidoscopic c oloring if and only if G has an rregular k-tuple 3.2 Complete Kaleidoscopes We begin with some observations.Let G be an r-regular k-kaleidoscope of order n. Then k<r<n.First.it is impossible that r=k.for otherwise.any edge coloring c of G in which every vertex of G is incident with at least one edge of each color results in)be ng the k-tuple in which each term is 1.Ifr +1,then there are at m ostk distin each of In this case.nk,which is impossible.Therefore.+2.Since the number of r-element multisets M whose elements belong to a k-element set .S is ()we have the following bounds involving k,r and n. Proposition 3.2.1.If G is an r-regular k-kaleidoscope of order n,then k+2≤r<n≤ -9-（-） Proof Let c be a k-kaleidoscopic coloring of G.Since we have already ob tr+2.it remains to show thatn().The number of r ement mu iset whose elements belong to the k-element set[]such that each multiset contains at least one element i for eachi(l≤i≤k)is r-k Hence,n≤() As Proposition 3.2.1 indicates,for a given integerk3,the smallest possible value of r for an r-regular k-kaleidoscope is r =k+2 and the smallest possible order n of such a graph is n=r+1.Obviously,the graph in question is the complete graph K+3.We show for eachk=3 that K+3 is,in fact,a k-kaleidoscope. Theorem3.2.2.For each integer k z 3.the complete graph K+3 is a k-kaleidoscope
3.2 Complete Kaleidoscopes 21 then we can assign the color i (1 i k) to each edge of Fi and obtain a kkaleidoscopic coloring of G for which the multiset-color cm.v/ of v is a1a2 ak. In this case, the factorization F is called irregular. Conversely, every k-kaleidoscopic coloring of G gives rise to an irregular k-tuple factorization F D fF1; F2; ; Fkg of G where the edges of Fi are those edges of G colored i and each Fi has no isolated vertices for 1 i k. Hence, an edge coloring of a graph G is a kaleidoscopic coloring if and only if the corresponding factorization of G is irregular. Therefore, a graph G has a k-kaleidoscopic coloring if and only if G has an irregular k-tuple factorization. 3.2 Complete Kaleidoscopes We begin with some observations. Let G be an r-regular k-kaleidoscope of order n. Then k r < n. First, it is impossible that r D k, for otherwise, any edge coloring c of G in which every vertex of G is incident with at least one edge of each color results in cm.v/ being the k-tuple in which each term is 1. If r D kC1, then there are at most k distinct k-tuples, each of which has 2 as one term and 1 for all other terms. In this case, n k, which is impossible. Therefore, r k C 2. Since the number of r-element multisets M whose elements belong to a k-element set S is r1 rk , we have the following bounds involving k;r and n. Proposition 3.2.1. If G is an r-regular k-kaleidoscope of order n, then k C 2 r < n r 1 r k ! D r 1 k 1 ! : Proof. Let c be a k-kaleidoscopic coloring of G. Since we have already observed that r kC2, it remains to show that n r1 rk . The number of r-element multisets whose elements belong to the k-element set Œk such that each multiset contains at least one element i for each i (1 i k) is .r k/ C k 1 r k ! D r 1 r k ! D r 1 k 1 ! : Hence, n r1 k1 . ut As Proposition 3.2.1 indicates, for a given integer k 3, the smallest possible value of r for an r-regular k-kaleidoscope is r D k C 2 and the smallest possible order n of such a graph is n D rC1. Obviously, the graph in question is the complete graph KkC3. We show for each k 3 that KkC3 is, in fact, a k-kaleidoscope. Theorem 3.2.2. For each integer k 3, the complete graph KkC3 is a k-kaleidoscope.