[PDF] Random graphs with bounded maximum degree: asymptotic

View - Download Random graphs with bounded maximum degree: asymptotic

Previous PDF

Next PDF

Gallai's pathdecomp ositionconjecture

for graphsof smallmaxim umdegree

Marthe Bonamy

and ThomasJ. Perrett yGallai'spathdecompositionconjectureforgraphsofsmall

Abstract

Gallai's pathdecomp ositionconjecturestatesthat theedges ofan yconnected graphon n verticescanb edecomp osedintoat most n +12 paths. Weconrmthat conjecture forall graphs with maximumdegree atmostve.

1 Introduction

AdecompositionDof agrap hGis acollection ofsubgraphs ofGsuchthat each edgebelongsto precisely onegraph inD. Apathde compositionis adecomp ositionDsuchthat every subgraph inDis apath. IfGhas apath decomposition Dsuchthat jDj=k, thenwesa ythatGcan be decomposedintokpaths. Inansw ertoaquestion ofErd} os,Gallai conjecturedthe following, see[4]. Conjecture 1.1.[4]Every connectedgraphonnverticesc anbede composed intodn2 epaths. Gallai's conjectureis easilyse ento besharp:If Gis agraph inwhic hev eryvertexhas odd degree, thenin any pathdecompositionof Geachv ertexmustb etheendpoin tofsomepath, andso at leastdn

2epaths arerequired. Lov asz[4]provedth atev erygraphonnverticeshas adecomp osition

Dconsisting ofpaths andcycles, andsuc hthat jDj=bn2 c:::::::::jDj bn2 c . Byan argument similartothe above,itfollows thatin agraphwithat moston ev ertexof even degree,suc ha decomposition must bea pathdec omposition. Thus,Gallai'sconjectureholdsf orallgraphswith atmost onev ertexof evendegree. LetGEdenote thesubgraph ofGinduced bythev erticesof evendegree. Buildingon Lovasz's result, Conjecture1.1hasbeen prov edfor severalclassesof graphsdenedbyimposing some structure onGE. Therst resultof thiskind was obtainedb yPyb er:::[1].

Theorem 1.1.[1]If

Gis agr aphonnverticessuch thatGEis afor est,thenGcanb edecomp osed intobn2 cpaths.

Later, Theorem1.1 was strengthenedbyF an

:::[2], whopro vedthefollowing. Theorem 1.2.[2]IfGis agr aphonnverticessuch thate achblo ckofGEis a triangle-free:graphof maximumde gre eatmost3, thenGcanb edecomp osedintobn2 cpaths.

CNRS, LaBRI,Univ ersitedeBordeaux,France

yTechnicalUniversit yofDenmark,Denmark 1 Gallai's conjecture is also known to hold for a variety of other graph classes. In 1988, Favaron

and Koudier [6] proved that the conjecture holds for graphs where the degree of every vertex is either

2 or 4. More recently, Botler and Jimenez [3] proved that the conjecture holds for 2k-regular graphs

of large girth and admitting a pair of disjoint perfect matchings. Jimenez and Wakabayashi [7]

showed that the conjecture holds for a subclass of planar, triangle-free graphs satisfying a distance

condition on the vertices of odd degree. Finally, it was shown by Geng, Fang and Li [5], that the conjecture holds for maximal outerplanar graphs. In this article, we prove that Gallai's conjecture holds for the class of graphs with maximum degree at most 5. Theorem 1.3.LetGbe a connected graph onnvertices. If(G)5, thenGadmits a path decomposition intodn2 epaths. To prove Theorem 1.3, we show that ifGis a smallest counterexample, thenGcannot containone::: any:of 5congurations :::::given:::::::::::::congurations::::::::(Lemma::::3.1). This restriction is enough to show

thatGEis a forest:::::::(Lemma::::3.2), whence the result follows by Theorem 1.1. It seems that proving

Theorem 1.3 for graphs of maximum degree 6 will require some new ideas. However, we think the approach of considering graphs of bounded maximum degree allows step-by-step improvements whichcould:::: may ev entuallylead to a general solution. In proving special cases of Conjecture 1.1, the presence of a ceiling in the bound brings with it a number of technical complications. It is therefore tempting to explore ways of proving a stronger,

ceiling-free version except in a few special cases. We say a graph is anodd semi-cliqueif it is obtained

from a clique on 2k+ 1 vertices by deleting at mostk1 edges. By a simple counting argument, we can see that an odd semi-clique on 2k+ 1 vertices does not admit a path decomposition intok paths. It is natural to ask if these are the only obstructions: Question 1.1.Does every connected graphGthat is not an odd semi-clique admit a path decom- position intobjV(G)j2 cpaths?

2Denitionsandnotation

:::::::::::::::::Background All graphs in this article are nite and simple, that is :they contain no loops or multiple edges. We say that a path decompositionDof a graphGisgoodifjDj djV(G)j2 e. In gures we make use of the following conventions: Solid black circles denote vertices for which all incident edges are depicted. White hollow circles denote vertices which may have other, undepicted incident edges. Vertices containing a number indicate a vertex of that specic degree. A dotted line between two vertices indicates that those vertices are non-adjacent. ::We::::::often:::use component::as:a::::::::shortcut:::for::::::::::connected::::::::::component.: We will often modify a path decomposition of a graphGto give a path decomposition of another graphG0. To describe these modications we use a number of xed expressions, which we formally dene here. LetDbe a path decomposition ofG. LetP2 Dbe a path andQbe a subpath ofP.

IfRis a path inG0with the same end vertices asP

::Q, we say that wereplaceQwithRto mean that we dene a new pathP0=PQ+Rand redeneDto be the collectionD P+P0. IfRis a path inG0with an endpoint in common withP, we say that weextendPwithRto mean that we dene a new pathP0=P+Rand redeneDto be the collectionDP+P0. For a vertexuon 2 P, we say that wesplitPatuto mean that we dene pathsP1andP2such thatP1[P2=Pand P

1\P2=u, and redeneDto be the collectionD P+P1+P2. Finally, for a pathRinG0, we

say that weaddthe pathRto mean that we redeneDto be the collectionD+R.:::::Given::a:::::graph

G:::and::::two:::::::disjoint::::sets:::A::::and::B::of:::::::vertices:::of:::G,:::we::::::denote:::by::::::::E(A;B):::the:::set:::of:::::edges:::::with:::one

endpoint::in::A::::and::::the:::::other::in:::B.:

By:::::::simple::::::::::arithmetic,:::we::::can::::::obtain:::the:::::three::::::::::::propositions::::::below.:

Proposition 2.1.LetGandG0be two graphs such thatjV(G)j jV(G0)j+2, and letDbe a path decomposition ofG. If there is a good path decompositionD0ofG0andjDj jD0j+ 1:,then Dis a good path decomposition ofG.LetjV(G)j=n.WehavejDj jD

0j+ 1 dn22

e+ 1 =dn2 e.ThusDisagoodpathdecomposition ofG.Proposition 2.2.LetG,G1andG2be three graphs such thatjV(G)j jV(G1)j+jV(G2)j, and letDbe a path decomposition ofG. If there are good path decompositionsD1andD2ofG1andG2 (respectively) andjDj jD1j+jD2j 1, thenDis a good path decomposition ofG.LetG;G 1andG

2haven;n

1andn

2verticesrespectively.WehavejDj jD

1j+jD2j 1 dn12

e+dn22 e 1 dn2

e.ThusDisagoodpathdecompositionofG.Proposition 2.3.LetG,G1andG2be three graphs such thatjV(G)j jV(G1)j+jV(G2)j+ 1,

and letDbe a path decomposition ofG. If there are good path decompositionsD1andD2ofG1and G

2(respectively) andjDj jD1j+jD2j, thenDis a good path decomposition ofG.LetG;G

1andG

2haven;n

1andn

2verticesrespectively.WehavejDj jD

1j+jD2j dn12

e+dn22 e dn2 e.ThusDisagoodpathdecompositionofG.3 Main Result LetGbe a graph with (G)k. We rst prove that a number of congurations are reducible in G,if.

::::::That:::is,::if::G::::::::contains::::one::of::::::them::::andGallai's conjecture holds for all sm allergraphs of

maximum degreek,:::::then:::::::Gallai's::::::::::conjecture:::::holds:::for::G. Lemma 3.1.Letk2N. LetGbe a connected graph with maximum degree(G)k, and suppose thatGdoes not admit a good path decomposition. IfGis vertex minimal with these properties, then Gdoes not contain any of the following congurations (see Figure 1): C

1:A vertex of degree2whose neighbours are not adjacent.

C

2:A cut-edgeuvsuch thatd(u)andd(v)are even.

C

3:An edgeuvsuch that:::::::::::::::d(u) =d(v) = 4,::::anduandvhave precisely2common neighbours,and

d(u) =d(v) = 4. C

4:An edgeuvsuch thatd(u) =d(v) = 4, and fort

1;t2;t3::

t1,:::t2,::t3:(resp.w

1;w2;w3:::w1,:::w2,::::w3)

the three otherneighbors::::::::: neighbours:ofu(resp.v), the pairst1t2andw1w2are not edges and t

36=w3.

3 4u 4v :::::t 1uvw 2t 3t 2w 3w

16=42j42j4Figure 1: CongurationsC1,C3,C4andC5from Lemma 3.1.

C

5:A triangleuvwsuch thatd(u) = 4andd(v);d(w)2 f2;4g::::d(v),::::::::::::d(w)2 f2;4g.

Proof.

Claim 1.Gdoes not contain the congurationC1.

Proof.Suppose that the claim is false. Letube the vertex of degree 2 withN(u) =fv;wg, and let G

0be the graphGu+vw. Sincevandware non-adjacent::in::G,G0is a simple graph. By the

minimality ofG, we have thatG0admits a good path decompositionD0. By Proposition 2.3, we obtain a good path decomposition ofGby replacing the edgevwwith the pathvuw(see Figure 2).vu w vwP vu wPP

Figure 2: The reduction ofC1.

This contradicts the assumption thatGhas no such decomposition.

Claim 2.Gdoes not contain the congurationC2.

Proof.Suppose that the claim is false. Deletinguv::::from::G:results in two connected graphsG1and G

2, containinguandvrespectively. By the minimality ofG, bothG1andG2admit good path

decompositionsD1andD2. To obtain a path decomposition ofG, note that, sinceuhas odd degree inG1, there is a pathPu2 D1ending atu. Similarly, there is a pathPv2 D2ending atv. Now letDbe the path decomposition ofGformed by taking the unionD1[ D2, deletingPuandPv, and adding a new pathP=Pu+uv+Pv(see Figure 3). By Proposition 2.2,Dis a good path decomposition ofG, a contradiction.uv uvP uP v uvPP P

Figure 3: The reduction ofC2.

4

Claim 3.Gdoes not contain the congurationC3.

Proof.Suppose that the claim is false. Let::uv:::be::::the::::edge::::::stated:::in:::::::::::::Conguration:::C3,::::and:::let:x

andybe the::::twoc ommonneigh boursof uandv. Sinced(u) =d(v) = 4, bothuandvboth: u::::and:v have precisely oneotherneighbour.Lettheseverticesbe:::: more::::::::::neighbour,:::say:u0andv0respectively. Sinceuandvhavepreciselytwocommonneighbours,wehavethat, ::::::::::::respectively,:::::where:u06=v0.

Suppose rst that at most one of the edgesxu

0;u0y;yv0;v0x:::

xu0,::::u0y,::::yv0,::::v0x:is present inG, sayxu0. IfGuvis connected, then letG0be the graphGuv+u0y+v0x. Otherwise, letG0=Guv+u0y+v0x+xy. Note thatG0is connected, and so by the minimality of G, it admits a good path decomposition. Now, replacev0xbyxvv 0:::: v0vx:and replaceu0ybyu0uy. Furthermore, ifxy2E(G0)nE(G), then replacexybyxuvy. Otherwise,:add a new pathxuvyto the decomposition. By Proposition 2.1, and since weadd::::: added:at most one new path, the resulting decomposition is a good path decomposition ofG. This contradicts the assumption thatGhas no such decomposition.

Next, suppose thatxu

0;u0y;yv0;v0x2E(G):::xu0,::::u0y,::::yv0,:::::::::::v0x2E(G), so the graphG0=G

uvis connected. By the minimality ofG, the graphG0has a good path decomposition. Now replace the edgexu0with the pathxvuu0, and add a new pathu0xuyvv0to the decomposition. By

Proposition 2.1, and since weadd:::::

added:at most one new path, the resulting decomposition is a good path decomposition ofG, contradicting the assumption. Finally, suppose that precisely two or three of the edgesxu

0;u0y;yv0;v0x:::

xu0,::::u0y,::::yv0,::::v0x:are present inG. As a consequence, from the setfxu0;u0y;yv0;v0xg nE(G), we may choose an edge, xu

0say, such that the graphG0=Guv+xu0is connected. By the minimality ofG, the

graphG0has a good path decomposition. Now replacexu0byxvuu0, and add a new pathxuyvv0 to the decomposition. Again, by Proposition 2.1, and since weadd:::::: added at most one new path, the resulting decomposition is a good path decomposition ofG, contradicting the assumption.

Claim 4.Gdoes not contain the congurationC4.

Proof.Suppose that the claim is false. SinceGdoes not contain CongurationC3, the verticesu andvdo not have precisely two common neighbours. First suppose thatuandvhave 3 common neighboursx;yandz. In this case, since there is a pair of non-adjacent vertices amongstN(u)nfvg, we may assumexy62E(G). Furthermore, by the denition of CongurationC4, the third vertexz is non-adjacent to at least one ofxory.Weconcludethattherearetwonon-edgesamongstx;y andz,saythesearexyandyz;::::say:::::::::yz62E(G). LetG0be the graphGuv+xy+yz. It is easy to see thatG0is connected. By the minimality ofG, the graphG0has a good path decomposition. In this decomposition, replacexybyxuyand replaceyzbyyvz. Finally, add a new pathxvuz(see Figure 4). This gives a good path decomposition ofG, a contradiction. We may thus assume that uandvhave at most one common neighbour. We now consider three cases depending on the structure ofG fu;vg. In each case we assume the previous ones do not apply (up to symmetry). 5 ux v zy x zy ux v zy Figure 4: The reduction ofC4in the case whereuandvhave three commonneighbors ::::::::::neighbours.

1.Assume thatGuhas at least three connected components. Becauseuvis not a cut-edge, the

component ofGucontainingvcontains at least one otherneighbor::::::::: neighbour:ofu. Thus Guhas precisely three components, andt1andt2lie in dierent components ofGu. Let G

0be the graph formed fromGuby adding the edget1t2. ThusG0has two components

G

1andG2, and by the minimality ofG, both have good path decompositionsD1andD2.

Without loss of generality we supposeG2containsv. LetP2 D1be the path containing the edget1t2. Furthermore, letP1andP2be the possibly empty subpaths ofPt1t2containing t

1andt2respectively. Note that sincevhas degree 3 inG0, there is some pathQ2 D2which

ends atv. We construct a path decomposition ofGby taking the unionD1[D2and replacing PandQwith the pathsP1+t1uv+QandP2+t2ut3. By Proposition 2.3, and since weintroducednonew::: did:::not::::::::increase:::the:::::::number:::ofpaths, the resulting path decomp ositionis good, a contradiction.

2.Assume thatG fu;vghas at least four connected components. Since bothGuandG

vhave at most two connected components, there are precisely four connected componentsC

1;C2;C3andC

4:::H1,::::H2,:::H3::::and:::H4. Furthermore, two of these components contain both

a neighbour ofuand a neighbour ofv, one component contains only a neighbour ofu, and one component contains only a neighbour ofv. Relabeling if necessary, we may suppose thatt

1;w12C1,t

2;w22C2,t

32C3andw

32C4::t1,::::::::w12H1,:::t2,:::::::::w22H2,:::::::t32H3::::and::::::::w32H4.

This relabelling preserves the fact thatt

1t2;w1w262E(G)::::

t1t2,:::::::::::::w1w262E(G):andt36=w3.

Consider the graphG1obtained fromC

1andC 2::

H1::::and::::H2by adding the edgest1t2and

w

1w2. Similarly, consider the graphG2obtained fromC

3andC 4::

H3::::and:::H4:by adding the

edget3w3. By the minimality ofG, we obtain good path decompositions ofG1andG2, which we merge in the obvious way. The edget1t2is replaced witht1ut2,w1w2withw1vw3, and t

3w3witht3uvw3) to obtain a path decomposition ofG. By Proposition 2.3, this yields a

good path decomposition ofG. 3. No wG fu;vghas at most three connected components, and each ofGuandGvhas at most two connected components. LetT=ft1;t2;t3gandW=fw1;w2;w3g. We claim that we can relabel the vertices inTandWsuch that the graphGuv+t1t2+w1w2 is connected and the properties thatt

1t2;w1w262E(G)::::

t1t2,::::::::::::w1w262E(G):andt36=w3are preserved. Indeed ifuandvhave a common neighbour, lett2Tandw2Wbe such thatt=w. Otherwise:,:lett=t1andw=w1. Suppose rst thattandwlie in the same component ofGuv. SinceGuvhas at most 3 components, andGuandGv have at most 2 components, there are non edgestt0andww0for somet02Tandw02W 6 such thatGuv+tt0+ww0is connected. Furthermore, sincetandware the only possible common neighbours ofuandv, we have that the single vertices inTnft;t0gandWnfw;w0g are not equal. Thus, lettingt1=t,t2=t0,w1=w,w2=w0and settingt3andw3to be the remaining vertices gives the desired relabeling. Suppose now thattandwlie in dierent components ofGuv. In particular this implies thatT\W=;. Again, sinceGuvhas at most 3 components, andGuandGv have at most 2 components, there are non-edgeseTandeWamongst the vertices ofTandW respectively, such thatGuv+eT+eWis connected. We relabel the vertices inTandW such thatt1andt2are the endpoints ofeT,w1andw2are the endpoints ofeW, andt3and w

3are the remaining vertices. SinceT\W=;, we have thatt36=w3are:

as:required. LetG0be the graph obtained fromG fu;vgby adding the edgest1t2andw1w2. By the argument above,G0is connected, and so by the minimality ofG, there is a good path decomposition ofG0. We obtain a path decomposition ofGby replacingt1t2witht1ut2and w

1w2withw1vw2, and adding the patht3uvw3. Note that sincet36=w3the latter is really a

path. By Proposition 2.1, and since weadd::::: added:at most one new path, this yields a good path decomposition ofG.t 1uvw 2t 3t 2w 3w 1 t 1w 2t 3t 2w 3w 1PQ t 1uvw 2t 3t 2w 3w 1PPQQ RRR Figure 5: The reduction ofC4in the connected case.

Claim 5.Gdoes not contain the congurationC5.

Proof.We rst consider the case where a pair infu;v;wg, sayfu;vg, has three commonneighbors ::::::::::neighbours.

Letxandybe the twoneighbors:::::::::

neighbours:offu;vgbesidesw. We argue thatwxyinduces a triangle. Indeed, rst assume there are at least two edges missing, sayxw;wy62E(G). Consider the graphG

00=G+xw+wy::::::::::::::::::::::::G00=Guv+xw+wy, note that it is connected, and consider a

good path decomposition of it. We obtain a path decomposition ofGby replacing the edgexwwith xuw, replacing the edgewywithwvy, and adding the pathxvuy, see Figure 6. By Proposition 2.1, this yields a good path decomposition ofG. Assume now that there is precisely one edge missing, say the edgexy. ConsiderG0, the graph obtained fromG fu;vgby adding the edgexy. IfG0is connected, then by the minimality ofG, it has a good path decomposition. From this, we obtain a path decomposition ofGby replacing the edgexywithxuvyand adding the pathxvwuy, see Figure 7. By Proposition 2.1, this yields a good path decomposition ofG. 7 xwyvu xwyPQ xwyvu PQR Figure 6: The reduction ofC5whenuandvhave three commonneighbors:::::::::: neighbours that indu ce at least two non-edges.xywvu xywP xywvu PQ Figure 7: The reduction ofC5whenuandvhave three commonneighbors:::::::::: neighbours that ind uce precisely one non-edge. Thereforex;yandwinduce a triangle. LetG0=G fu;vg, and note thatG0is connected. Thus, by the minimality ofG, the graphG0admits a good path decompositionD0. We obtain a path decomposition ofGas follows: First assume without loss of generality thatxyandwy do not belong to the same path ofD0. LetQ0be the path ofD0containing the edgexw, and Q=Q0xw+xu. We considerD00=D0Q0+Q. LetP0be the path ofD00containing the edge xy. We writeP0=P01+xy+P02, whereP01andP02may be empty paths. SetP1=P01+xyvwand P

2=P02+yuvxw. Note thatP1andP2are paths even ifP01also contains the edgexuor in other

wordsP01=Q. Finally, letR0be the path ofD00containing the edgeyw :::wy, and setR=R0+wu. Remember:::::that:::we::::::::assumed::::::::P06=R0.::We note thatD=D00P0R0+P1+P2+Ris a path decomposition ofG, with precisely one more path thanD0, see Figure 8. ThusDis a good path

decomposition by Proposition 2.1, a contradiction. Therefore no pair infu;v;wghas three commonneighbors

::::::::::neighbours.xyw vu P 0Q 0Rquotesdbs_dbs21.pdfusesText_27

[PDF] maximum dextrose concentration for peripheral line

[PDF] maximum heart rate

[PDF] maximum hours allowed to work in a day

[PDF] maximum mode of 8086 timing diagram

[PDF] maximum solutions corporation

[PDF] maxwell boltzmann distribution

[PDF] maxwell boltzmann distribution equation

[PDF] may 2017 movies in theaters

[PDF] maya course syllabus

[PDF] maybelline 10k

[PDF] mba assignment sample pdf

[PDF] mba cet 2020 admit card

[PDF] mba cet 2020 analysis

[PDF] mba cet 2020 application form login

[PDF] mba cet 2020 exam date karnataka