### Journal Menu >> Open Journal of Discrete Mathematics, 2013, 3, 175-182 http://dx.doi.org/10.4236/ojdm.2013.34031 Published Online October 2013 (http://www.scirp.org/journal/ojdm) A Lemma on Almost Regular Graphs and an Alternative Proof for Bounds on tk mPP Paul Feit Department of Mathematics, University of Texas of the Permian Basin, Odessa, USA Email: feit_p @utpb.edu Received July 16, 2013; revised August 10, 2013; accepted September 3, 2013 Copyright © 2013 Paul Feit. This is an open access article distributed under the Creative Commons Attribution License, which per- mits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT Gravier et al. established bounds on the size of a minimal totally dominant subset for graphs . This paper offers an alternative calculation, based on the following lemma: Let kmPP,kr so and . Let 3k2rH be an - regular finite graph, and put . 1) If a perfect totally dominant subset exists for , then it is minimal; 2) If and a perfect totally dominant subset exists for , then every minimal totally dominant subset of must be perfect. Perfect dominant subsets exist for when and satisfy specific modular conditions. Bounds for , for all follow easily from this lemma. Note: The analogue to this result, in which we replace “totally dominant” by simply “dominant”, is also true. rkGPHG>2rtkPG GkPCnknmP,km Keywords: Domination; Total Domination; Matrix; Linear Algebra 1. Introduction Let be a graph. In this paper, each edge of a graph must have two different endpoints; also, two vertices may be linked by at most one edge. A subset Z of vertices is said to totally dominate G if every vertex of G has a neighbor in Z. We say Z perfectly totally dominates if every vertex has exactly one neighbor in Z. Next, suppose that G is finite. In this case, we say a totally dominant subset Z is minimal if  ,GVGEGZ is the smallest size possible among all dominant subsets. This minimal size is denoted by tG. For , we say that a graph G is r-regular if every vertex is the endpoint of exactly r edges. Suppose G is regular. A subset Z which perfectly totally dominates is clearly minimal. If a perfect dominant set does not exist, we can search for minimality among dominant subsets Z by counting “overlaps”. That is, for each rvVGv, let t be the number of neighbors of which lie in Z, minus 1. If ,,G Zol v1Z and 2Z are two totally dominant subsets, then 12k(1 The graph consisting of plus an ed) Fo and2.n 1 anr GkP isge betweed k called the k-cycle. It denoted by kC. (1c H graphhe prct graph s, toduGH is deed asllows. The set of vertices fin foH is VGVG VH. Two vertices 11,xy and 22,xyr aredge if and only if  ei 2e linke an d bythe 1xx and 12yy is an edge of H, or  12xx is an edge of G and 12yy. For example, for ,kn, knPP is the familiar kn grid map. A proa aths and circuits is called a grid graph. A product of n copies of duct of list of pby  corresponds to the set n with the “Mahatten metric” notion of the edge: two les tupn1,,nxx and 1,,nyy are linked if and only if index at there is anith such 1iixy and Copyright © 2013 SciRes. OJDM P. FEIT 176 jjxy for all ji. Tiling is the route that Gravier  takes in computing t for grid graphs. The program begins with the work herself, Molland and Payan  on the tiling question. The solution generates perfectly dominant subsets on n. Now, finite grid graphs can be interpreted as rec- ular subsets, or (for products with nC factors) as such subsets with some “opposed” sides intified. Do- mination becomes a problem of refining the patterns at the edges. Our currbytangdonudeent xploits the abundance of perfect work eminations on graphs knGPC. A calculation with matrices leads to a lowertG that can only be attained by a perfectly totally dot subset. Once we classify which indices ,kn admit perfect domi- nations, an elementary trick ides upper and lower bounds for all graphs knPC. The bounds here do not improve on the earlier wt are almost as narrow. Suppose H is a finite r-regular graph for some natural bound on provork, buminanmber r, and put kGPH for 3k. Then the majority of vertices a de2rof G havegree . The vertices of the degree 1r form two conn sub- graphs. A crude bound for minimal totally dominant subset of G is ected a2kH r. However, this bound is too low by a positives e number timH. We find a subtler minimal bo usinundhe t subset is minimal, and bset cannot have fewer members is odd, if a perfect totally enclusions follow from a formula which, for Z a g matrices. Tcoasthadototmputation also shows that (2a) A perfect totally dominansumes the bound; (2b) A minimal sun a perfect subset; and (2c) Unless 2r and n minant subset exists, thn every minimal subset is perfect. The coally dominant subset, determines Z is a sum over vVG of ,,tjolvZ G, where each j is a w j of v. Remark. A variation on total dinatin non-zero dodo1.1. Saweight associated to roomois (simple) d v has no neighbors in Z, or Z. rfect mple Perfect Behavior ts: first, exhibit a sub- ite. Idmination. A subset dominates (non-totally) if each vertex v either has a neighbor in Z or belongs to Z. A dominant subset Z is perfect (non-totally) if for each vertex v, either (3a) Z anv(3b) and v has exactly one neighbor invZOur theory implies that, in this context, if a peminant subset exists, it is minimal and every minimal dominant subset is perfect. A proof of minimality has two parset; then prove no smaller totally dominant subset can exist. The examples here are drawn from Gravier . Assume n is even. In this case, knPC is bipartentify nC with n in the stanway. We can “color” the vertices: we say ,ij (where j is read moddard n) is black if ij is eand whit if ijven e is odhen every edgks a black vertex with a w one. If Z dominates knPC, then the set of black members of Z dominates all white vertices, and the white vertices of Z dominate all the black. Consequently, a minimal dominant subset is a disjoint union of two minimal “color” dominant subsets; each a subset of one color vertices that dominates all vertices of the other color. Furthermore, the “shift by 1” automorphism of kkPC identifies the sets of different colored vertices. re 1 shows a pattern of vertices of one colord. Tiguuse linhite. stead, FPrasovided that k is odd, this pattern will totally domi- nate all vertices of the opposite color. If k is even, this pattern does not quite woInrk. illtrated in Figure 2 for 8k, one can build a pattern by taking triangular wedof the first pattern, and pairing them with a skew reflection. The latter pattern can be repeated throughout knPC provided that ges 21k divides n. Thbution of his pae contritper is aset n alternate con- struction of a lower bound. The bound is met for these perfect subsets. Next, using these subsets, one can estab- lish a general upper bound for kmPP for all m. 1.2. A Tie with Perfection Gravier  proves that the Z consisting of the middle row of 3nPP, for any n,s a minimal totally dominant subset. Obviously, this choice of minimal i Figure 1. Once, k odd.e color dominan Figure 2. Once, k = 8. e color dominanCopyright © 2013 SciRes. OJDM P. FEIT 177For each integer 1jk, put subset pro blocks, duces many overlaps. By rotating 33we can produce other minimal dominant seth fewer overlaps, as in Figure 3. Furthermore, if n is a multiple of 4, there is a variation which is a perfect total domination of 3nPC, as in Figure 4. The flexibility in the number of s which are dominated by more than one member of ts wiverticeZ reflects the presence of vertices of two degrees, namely 3 and 4. In this example, the size of a minimal, imperfect to1.3. Weights ts of theorems based on series. tally dominant subset “ties” the size of a perfect totally dominant set. Can a minimal subset be smaller than a perfect one? We prove that a tie is rare, and that beating is impossible. We have two seDefinition 1 Let r be a real number. Let r ia be the set of infinite sequences of real numbers0i such that 121, .iiiiaraa Clearly, r1ii. is a real vector space, and the fu real, let ibe the unique member of nction ,aaa is a linear isomorphism from it onto For 012r,ir r sch that and ,1 1r. Observe ,2rr. In that thue o,0 0r g section, we defpeninip function ned the overla,,tv G Z for totally dominant subsets Z of a graph G. or G a graph and Z a dominant (but possibly not totally) subset, and vVG, let ,,olv GZ be ,,tolvGZ if vZ an,G ZZolIn addition, fd ,tol v1 if v. , GPH fh HvVefine the row of v to be the first of v. Lemma 2 Lt For >3kG, dcoordinatek row or some grap and ve such that and ,rk 2r3k. Figure 3. Two ways to totally dominate 3nPP. Figure 4. Perfect domination in 34mPC. 1,jrk   1 1,11, .jkjrk jrj  For each 1jk, 0(4a) j, and (4b) 0j if and only if is odd and is fer to 2r, k j even. We re1,,k as the weight system for para- mition 3 Let eters ,rk. Defin ,rk such that and 2r3. Let 1,,kkweight system,rk. let 1, be the for Also, ,k be the weight system for parame 1,rk ters. Define   1222,12 ,12, .2,1krk kr kr krk rrk  Suppose is an regular graph, and put r-nH H and kGPH. Define two functions on ZVG: , ,ZolvZG rowrowscorescore, ,tt vvVGtvvVGZolvZGv Theorem 4 Assume the hypothesis and construction of Lemma 2 and Definition 3. Let H be a finite graph, and put nH and kGPH.(A) If ZVG is totally dominant, then   scoretZ, .2,1Znrk rrk (B) If ZVG is dominant, then   scoreZ1, .31,1Znr krrk A trivial consequence of this theorem and the pre- ce ume the hypothesis of Theorem 4. ding lemma is: Corollary 5 Ass(A) Suppose 3r. If 12,ZZ are totally dominant subsets of G, then  121 2< score1. Define ,Lrk to be the kk matrix such that ,if ,,Ind, ,1ifis1or10otherwise.ijrijijkLrkij  ,Note that ,Lrkhese pa is symmetric. Also, for trameters, define,Mrk to be the Note that the case is covered in both parts of this conditional definition. atrix kk matrix such that ,Ind, ij k  ,,,1if ,,,,1if .ijri rkji jMrk rjrkij i  is essentially 1,rkL. 3. Relevant Sequences convexity for functions of a ij As we shall see, the m,MrkThere is a discrete analogy tosingle real variable. We recall some basics. Definition 8 Let 0iai be a sequence of real num- bers, starting at index We say that the sequence is convex if 0. 11, .iiiiiaaaa We saya the sequence is strictly convex if 11>iiiiaaa for each i. 0iaLemma 9 Let i be a convex sequence. For ,vu, 0 .uvuvaaaa Moreover, 0uvu vaaaa ch that if and only if there is a number t su1, .iiuvata  IndiProof. geWe may interchange u and v without loss of nerality. Hence, assume uv. For each i, put 1iiibaa. Then 1ibi weakly incr se- is a easingquence. Then00 01110110111011u vuv uviiiiiivvuv u vuiiiivvuvuvuv jijivuvuvuviiiaaaabbbaaaabbaaaabbaaaab b      uvObseaa (8) rve that   21 ii uv vi1uv 0.   For eacfoh index i in the last sum, the term has the rmat pqbb where >pq. Therefore 00.uvaa au va Now s00uv uvaaaa.) must be 0. Wh Then every term uppose in the final sum of (8en 1i, we get 10uvbb. Since ib is an increasing ence, it 1ibb sequfollows that  foevery index iuv. □ We focus sequences ,rfinition 1.r the ion  of De 0 Let r be a real number. Then Trivial. □ ThProof. e first remark is that the sign ceparated from the magnitude. Lemma 1an be s  1, 1,, .iiriri  Copyright © 2013 SciRes. OJDM P. FEIT 179Many of the positive sequences ,ri are convex. Lemma 11 Each member of 2 is a linear se- qu Trivial. □ ence. Proof.Lemma 12 Let >2r, and let ibr such that 1b00b. If 1bthen >0 , ibasing and more, 1iibb can occur only if 1i. is increstrictly convex. Further Proof. For , we can rewrite the relation 2is 12iirb b aib(9a) 11 12iiiib bb  2bbrbb b2bi111iiiiithe two identities to induct on br, and 2the double hy- po2. □ Corollary 13 Let and su(9b) . Use thesis that both >>0 anbb 111d >>0 iiiii ibbbb rkch that 2. Then r,rkof. This0. an easy consePro quence mma and LeFo is of this lemma 10. □ The next two propositions play roles in our analysis. Lemma 14 Let r be a real number other than 2. r 1k,  1,1, 1, 2.irk rkri r  (10) Proof. In what follows, a sum from any integer to kmv1 is defined to be 0. For this proof, we abbreiate mkFor for ,rk. each 0k, define 0, .kiksri Then for iDefine a new sequence by 2k,     2121012011 211 .kkikkjjkksrirj jrs s    12iitsr. Replace 12iistr into the previous relation to get kHence, 12, .kkktrtt it belongs to r. Now 0011112211.22tsrrrtsrr  2, In the vector space  111 1, 1,0,1.22 22rrrr rr  The sequences it and  11122ii irr both belong to rth, and agree on the first two indices. He sequence. This gives the equality of (10). □ Lemma 15 Let ence, they are e samr be a real number, and let ,jk such that kjn . The  ,1,, 2,1,1 .rkr jrkjrjrk j   Proof. We write i for ,ri in this a If kj r gu men t., then 22kjr, 111kjrecu defin, and the fition. result ollowsfrom a proo1 .j from the rsiveThe remaining cases follow f is by in- duction on j. The inductive hypothesis is 1kj , 21kjkjjk  For 1j, this follows from the fact that 11 and 00. Assume j for which the inductive hytrue. Let pothesis is k so >1kj. Then  21 11jkj jkjrj j     111112111 .k jjkjjrk jkjjk jjkjjk jk      111kjj kjrj jkj   1  □ 4. The Inverse Matrices We can now prove Lemma 16 Let k and . The matric prduct ro- ,,Lrk Mrk is ,1rk times the iden- tity matrix. ent, let Proof. For this argum,LLrk and ,MMrk and, for each i 0, let ,iri . Le,Induvthe lemma by comparing the v en and k. We prove t ,utry of LM1k times the u,v entry of the identhere at of cases. ity matrix. Tlo Case re a 1u. For any vkInd , Copyright © 2013 SciRes. OJDM P. FEIT 180 1,2, .vvvLM M Suppose 1. Recall that 11. Therefore 1, 2M v1,1 11Mrkkk   . 2,1Suppose1. Recall that rMv2r . Then and .Case . For any , this is 2v,  1, 110vvrMMrkvkv 2, r  ukIndvk, , .v kvL rM1,,kkvM M If vk 11 1 krkrk k   1k1.Now suppose . Then , and vk1vk  ,210 .kv vr vvrr  Case . For any There are three subcases here. First, supposLM1< 0j. (C) If >2r, then >0j. (D) Let xn. Expand ,Lrkx as Then T1,,bb. n  11 .2,1kjjjsum xbrrk  (11) Proof. We start with Part (D), as that is our motivation. Given 11,, and ,,, ,nkxxx bLrkxbb it follows that 1, .xLrkb Bemm1 ik , y La 16, for each ,1j1k, .,1ijijxMrk brk ma 17From Lem,   ,11,,1.2,1jij,1 ,1 ,kjjm xMrk brkbrrkeach surkrkjr j  Now replace ,ri by. The  11,irijb-coefficient becomes 2,1rrk. jRecall Lemma 12. Then is a non-negative an,iri d convex sequence, and ,0 0r. Convexity im- plies that kis(12a) and are both odd, and (12b) trictly convex. This lishes all our conclusions excep in the case when k is odd and j is even. Assume these parameand we know for all and (A) follow This corollary proves Lemma 2. 1,1 1,11,jrkrkjr j  j positive unless 1j,kj is not sri remark estabt2r, ters, s. 2,ii i, □ Corolla ry 19 Let k,r. A, and ssume let 2r j be the overla in which everyp w eeights ftry is 1,or be nTh,kr that is . Let ˆ11,1, the vector ,1 . en 1, ,ˆ1 ,sumLrk  r kwhere is defined in Definition 3. Proof. The easiest way is to get this formula is (13a) Start with the formulas in Lemma 17; s over using Lemma 14; and onv,rk (13b) Sum the termj (13c) Cert all ,ri to  11,iriroof o. servationf all thpr dae examles ofnd 1. Fi e The ob of (6) completes the popositions in Section 1.3. 5. When r = 2 Th s to add some secon-e numerical calculations allow ury comments on thp Sections a1 and 1.2. x2r , and put 2,LL k. Then2,ii for all indices i. If Z is a perfect totallyt subset of PC and z is its row-count v dominanector, then knˆ1Lz n. is odd, If kˆ12,0, 2,0, , 2n nnn1 .L cannot exConsequently, a perfect totally dominant subsetist if n is odd. However, since 0j for j even dominabsets who, th sthere may be totallynt sue size “ties” e estimate for a perfect subset. In the case 3k, the set consisting of the middle row has row-count 0, ,0n. Its image under L is ,n. -th coordia,3nnIf k is even, the nite of 1ˆ1Ln is 1ifis odd, times is even.21ki iniifik The entre integral i if 1k di. Unlike the case hen k is odd, 1ˆ1ries af and onlyvides n wsum Ln cannot be matched by the size of an imperfect dominant subset. Near Perfect Now  224 ifis even,812,1ifis odd.4kk kkkkk Prosition 20 Fo ,4kn, op r  2, 2tk nknPPn2, k. Proof. There is d  and kdZPC suchat (14a) th2n divides d, (14b) Z is a totally dominant subset okdC, Pf (14c) 2,ZkdPartition kmPC in subsets re each . to whe1,,mYYiY consists of 2n successive columns. For at least ndex one ii,  2,iYZ k2n. Ch, the su knPP with Yrough 1noose such an bgraph of ns 2index. Identifycolum th of iY. Let 1ZZY. Any er ofmemb Y which is not dominated by 1Z is domi- ed by enatxactly one member of Z in either the 1st or Copyright © 2013 SciRes. OJDM P. FEIT Copyright © 2013 SciRes. OJDM 182 column; furthermore, each member of either col- inates just one member of . Consequently, n expand (15b) EG is union of 1kiiEH with : 1< .ivhvikvVH 2n umn domwe caY1Z Yto a totally dominant 2Z for of size iYZ6.Our loPslii the asser Theoremd its Coroo ravier,d Graphs,” D lied Ma 121, No. 1-3, 2002, pp. 119- 128. http://dx.doi.org/10.1016/S0166-218X(01)00297-9. □ igraphwer bouuses only a few as the hs ntly, alculaa arger rhs. nd e pecttion of grapkThentions of 4, anllary, apply t G. REFERENCES Extended Functs skghtly lfamily of gapH. Consequthe capplies to S. G “Total Domination of GriiscreteApp thematics, Vol.Fix k n with ,,>2nkr . Let 1,,r,,HHvertices. For eac be a h he (dniolis1Det of r-regular graphs, eac:hed th with n  be