On cycles and independence in graphs [Elektronische Ressource] / Friedrich Regen. Gutachter: Jochen Harant ; Eberhard Triesch. Betreuer: Dieter Rautenbach

Description

TECHNISCHE UNIVERSITÄT ILMENAUFAKULTÄT FÜR MATHEMATIK UND NATURWISSENSCHAFTENINSTITUT FÜR MATHEMATIKOn Cycles and Independence in GraphsDissertationzur Erlangung des akademischen GradesDr. rer. nat.eingereicht vonDipl.-Math. Friedrich RegenInstitut für MathematikTU IlmenauJuli 2010Betreuender Hochschullehrer: Univ.-Prof. Dr. rer. nat. habil. Dieter Rautenbach(Technische Universität Ilmenau)urn:nbn:de:gbv:ilm1-2010000384Meinen lieben ElternContents1 Introduction 31.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.1 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.2 Complexity Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Cycle Packings 92.1 Cycles of a given length . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.1.1 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.1.2 Hardness of Approximation . . . . . . . . . . . . . . . . . . . . . . 152.2 Cyclomatic Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.2.1 Graphs G with (G) (G) =k . . . . . . . . . . . . . . . . . . . 21e2.2.2 G with (G) (G) =k . . . . . . . . . . . . . . . . . . . 29v3 Cycle Spectrum of Hamiltonian Graphs 373.1 Chords of a Hamiltonian Path . . . . . . . . . . . . . . . . . . . . . . . . . 393.1.1 Chords of length greater than three . . . .

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_ilmenau
• Publié le: 01 janvier 2011
• Nombre de lectures: 17
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

TECHNISCHE UNIVERSITÄT ILMENAU

FAKULTÄT FÜR MATHEMATIK UND NATURWISSENSCHAFTEN

On

Cycles

INSTITUT FÜR MATHEMATIK

and

Independence

Dissertation

zur Erlangung des akademischen Grades Dr. rer. nat.

eingereicht von Dipl.-Math. Friedrich Regen Institut für Mathematik TU Ilmenau

Betreuender Hochschullehrer:

Juli 2010

in

Graphs

Univ.-Prof. Dr. rer. nat. habil. Dieter Rautenbach (Technische Universität Ilmenau)

urn:nbn:de:gbv:ilm1-2010000384

Meinen lieben Eltern

Cycle Spectrum of Hamiltonian Graphs 3.1 Chords of a Hamiltonian Path . . . . . . . 3.1.1 Chords of length greater than three 3.2 Cycle Lengths in Hamiltonian Graphs . .

3

. . .

. . .

. . .

. . .

4

47 51 51 57 61 65 66 68

v

Contents

2

. . . .

. . . . . . . .

. . . .

Introduction 1.1 Summary . . . . . . . . . . 1.2 Notation . . . . . . . . . . . 1.2.1 Graph Theory . . . . 1.2.2 Complexity Theory .

9 10 10 15 21 21 29

37 39 41 44

. . . . . .

. . . . . .

. . . .

. . . .

. . . .

1

. . . .

. . . .

. . . .

. . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

3 3 4 4 7

Forbidden Cycles and the Independence Ratio 4.1 Triangle-free Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Average degrees below 10/3 . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Average degrees beyond 10/3 . . . . . . . . . . . . . . . . . . . . . 4.2 Graphs with odd girth 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Bipartite ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Odd girth 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Triangle-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . . . . .

Cycle Packings 2.1 Cycles of a given length . . . . . . . . . 2.1.1 Exact Algorithms . . . . . . . . . 2.1.2 Hardness of Approximation . . . 2.2 Cyclomatic Number . . . . . . . . . . . 2.2.1 GraphsGwithµ(G)−ν e (G) =k 2.2.2 GraphsGwithµ(G)−ν v (G) =k

. . .

. . .

. . .

. . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Zusammenfassung

Contents

Die vorliegende Arbeit behandelt Fragestellungen im Zusammenhang mit Kreisen und unabhängigen Mengen in Graphen. Kapitel 2 handelt von unabhängigen Kreisen: Die Parameterν e bzw.ν v geben die ma- ximale Gröe kanten- bzw. eckendisjunkter Kreispackungen an, d.h. die maximale Anzahl von Kreisen in einem Graph, die paarweise keine gemeinsame Kante bzw. Ecke haben. Da die Berechnung dieser Parameter bekanntermaen schon für subkubische Graphen schwer ist, geht es im ersten Abschnitt um die Komplexität eines einfacheren Problems, des Packens von Kreisen einer festen Länge`in Graphen mit MaximalgradΔ. Für`= 3und beliebigesΔwurde diese Komplexität bereits von Caprara and Rizzi in [12] bestimmt, und wir verallgemeinern ihre Ergebnisse auf alle gröeren Kreislängen`. Im zweiten Ab- schnitt von Kapitel 2 untersuchen wir die Struktur von Graphen, für dieµ(G)−ν e (G) bzw.µ(G)−ν v (G)einen vorgegebenen Wert haben. Die2-zusammenhängenden derar- tigen Graphen können erzeugt werden, indem eine einfache Erweiterungsregel auf eine endliche Menge von Graphen angewandt wird. Aus diesem Strukturergebnis können wir folgern, da die Parameterν e (G)undν v (G)„fixed parameter tractable“ bezüglich ihrer Differenz zur zyklomatischen Zahl sind. In Kapitel 3 bestimmen wir die Gröenordnung der minimalen Anzahl von Kreislän- gen in einem Hamiltongraph mitqSehnen. Wir geben eine Familie von Beispielen an, in denen nur √ q+ 1Kreislängen auftreten, zeigen aber, da jeder Hamiltongraph mit qSehnen mindestens q 7 4 qKreislängen enthält. Der Beweis beruht auf einem Lemma von Faudree et al. in [23], demzufolge der Graph, der aus einem Weg mit Endeckenx undyundqgleichlangen Sehnen besteht,x-y-Wege von mindestens q 3 verschiedenen Längen enthält. Im ersten Abschnitt korrigieren wir den ursprünglich fehlerhaften Be- weis und leiten zusätzliche Schranken her. Im zweiten Abschnitt folgern wir daraus die Unterschranke für die Anzahl der Kreislängen. Im letzten Kapitel untersuchen wir Unterschranken für den Unabhängigkeitsquotien- t c e h n e , S d c . h h r . a d n e k n en B f r ü u r ch di n α e ( ( G G K ) ) ,fapheürGrir.Welstnflet,esgegnnebeiDreethcadbsemtgöil- uzeorgrüfeiwosnheapGrerlleasslanpaehdeGrngenenhäsamm bereits bekannt sind. Deshalb verändern wir die Fragestellung, indem wir Graphenklassen betrachten, die durch das Verbot kleiner ungerader Kreise definiert sind. Das Hauptergeb- nis des ersten Abschnitts ist eine Verallgemeinerung eines Ergebnisses von Heckman und Thomas, das die bestmögliche Schranke für zusammenhängende dreiecksfreie Graphen mit Durchschnittsgrad bis zu 3 01 impliziert und die extremalen Graphen charakterisiert. Der Rest der ersten beiden Abschnitte enthält Vermutungen ähnlichen Typs für zusam- menhängende dreiecksfreie Graphen mit Durchschnittsgrad im Intervall  01 3 , 45 31  und für zusammenhängende Graphen mit ungerader Taillenweite7mit Durchschnittsgrad bis zu 41 5 . Der letzte Abschnitt enthält analoge Beobachtungen zum Bipartitionsquotienten. Möglicherweise lassen sich viele Unterschranken für den Unabhängigkeitsquotienten auf den Bipartitionsquotienten übertragen, indem man sie einfach verdoppelt. Diese neuen Schranken sind stärker, und die zugehörigen Klassen extremaler Graphen oft viel reich- haltiger. Am Ende dieser Arbeit diskutieren wir Vermutungen dieser Art.

1

Contents

Dank

Meinem Doktorvater Professor Dieter Rautenbach möchte ich herzlich dafür danken, da er mir ermöglicht hat, in die graphentheoretische Forschung einzusteigen und diese Arbeit zu schreiben. Er hat die Arbeit mit groem Einsatz betreut, und ich habe ihn nicht nur als Mathematiker, sondern auch als Menschen sehr zu schätzen gelernt. Auch die Zusammenarbeit mit Dr. Stephan Brandt, Dr. Christian Löwenstein, Janina Müttel und Anders Sune Pedersen hat mir viel Freude gemacht und war für mich eine wertvolle Erfahrung. Die Herzlichkeit der Ilmenauer Graphentheoriegruppe und der Kammerchor der TU Ilmenau trugen wesentlich dazu bei, da mir mein Aufenthalt in Ilmenau in guter Er- innerung bleiben wird. Meinen Eltern und Geschwistern bin ich für ihre Unterstützung und viele gute Gespräche sehr dankbar.

2

1

1.1

Introduction

Summary

This thesis discusses several problems related to cycles and the independence number in graphs. In Chapter 2, we discuss independent sets of cycles. The parametersν e resp.ν v denote the maximum cardinality of edge-disjoint resp. vertex-disjoint cycle packings, i.e. the maximum number of cycles in a graph that can be arranged such that no two of them share an edge resp. a vertex. Since the computation of these parameters is known to be hard even for subcubic graphs, the first section discusses the complexity of a simpler problem, packing cycles of fixed length`in graphs of maximum degreeΔ. For`= 3 and arbitraryΔ, the complexity has been determined by Caprara and Rizzi in [12], and we extend their results to all greater values of`. Insecond section of Chapter 2, we the discuss the structure of graphs for whichµ(G)−ν e (G)resp.µ(G)−ν v (G)equals some given integer. The2of this kind can be obtained by a simple extension-connected graphs rules applied to a finite set of graphs, which yields a fixed-parameter-tractability result forν e (G)andν v (G). In Chapter 3, we approximate the minimum number of cycle lengths in a Hamiltonian graph withq give chords. Wea family of examples that contain only √ q+ 1cycle lengths, but show that q 7 4 q proof relies on a lemma by Thecycle lengths can be guaranteed. Faudree et al. in [23], which states that the graph that contains a path with endverticesx andyandqchords of equal length contains paths betweenxandyof at least q 3 different lengths. In the first section, we correct the originally faulty proof and derive additional bounds. The second section we use these bounds to derive the lower bound on the size of the cycle spectrum. In the last chapter, we study lower bounds on the independence ratio, i.e. the fraction n α ( ( G G ) ) ssibleboundsarearlaeydenivnsdey.itobWevresahtesebtop-tofgr,osgfarhp fymodie,weeforhpargyrartibraronncogearrlfondsa known both f ected graphs. Ther the question by considering classes of graphs defined by forbidding small odd cycles as subgraphs. The main result of the first section is a generalisation of a result of Heckman and Thomas that determines the best possible lower bound for connected triangle-free graphs with average degree at most 0 3 1 and characterises the extremal graphs. The rest of the first two sections contains conjectures with similar statements on connected triangle- free graphs of average degree in  1 3 0 , 31 45  and on connected graphs of odd girth7with average degree up to 5 41  last section collects analogous observations for the bipartite. The ratio. It seems possible to translate many lower bounds on the independence ratio to bounds on the bipartite ratio by just doubling them. Those new bounds are stronger

3

V(G),E(G)

n(G),m(G)

N G (v),N G [v]

d G (v)

δ(G),Δ(G),d(G)

1 Introduction

and the corresponding classes of extremal graphs usually much richer. with some conjectures for statements of such generalisations.

Acknowledgement

The thesis ends

I would like to thank Prof. Dieter Rautenbach for giving me the opportunity to enter graph theoretical research and to write this dissertation. He was a most competent, friendly and committed advisor. I have also enjoyed the collaboration with Dr. Stephan Brandt, Dr. Christian Löwenstein, Janina Müttel and Anders Sune Pedersen in joint projects very much. The Ilmenau graph theory group and the Kammerchor der TU Ilmenau made me feel at home in Ilmenau. I am very grateful to my family for their support and inspiration.

1.2 Notation

In this section, we briefly define the graph theoretical concepts used in this thesis. It is included merely as a reference and should be skipped both by the graph theorist and the newcomer, who will find well motivated and accessible introductions in the books by Diestel [18] and by Korte and Vygen [41]. The former covers more areas of “purely mathematical” interest while the latter emphasises algorithmic questions.

1.2.1 Graph Theory AgraphGis a pair  V(G), E(G)  , whereV(G)is an arbitrary set called thevertex set ofG, andE(G)⊆  {v, w}:v, w∈V(G), v6=w  is called theedge setofG may also. We refer to an edge{v, w}by the shorthand notationsvworwv this thesis, we. Throughout only considerfinite elements of Thegraphs, i.e. graphs whose vertex set is finite.V(G) are called thevertices, the elements ofE(G)theedgesofG cardinality of. TheV(G)is theordern(G) :=|V(G)|ofG, the cardinality ofE(G)thesizem(G) :=|E(G)|ofG.

Neighbourhoods and degreesA vertexvisincidentwith an edgee, ifv∈e. The (open)neighbourhoodof a vertexvis defined byN G (v) ={w∈V(G) :{v, w} ∈E(G)}. wis called adjacent tov, ifw∈N G (v) closed neighbourhood of. Thevis defined by N G [v] :=N G (v)∪ {v}. Thedegreeofvisd G (v) :=|N G (v)|. Theminimum degreeofGis δ(G) := min{d G (v)|v∈V(G)}, themaximum degreeofGisΔ(G) := max{d G (v)|v∈ n m(G) , since each edge contri t V h ( e G d ) e } rgfoee ethn tw d o ,aav v e er r t a i g c e es. deg V r e e r efo tcise Gsi foed d g ( re G e0 ):= are 2 c ( a G l ) ledisolatedllhaapgreoswhof t A e . buost vertices have degreeris calledr-regular particular,. In3-regular graphs are calledcubic, 4-regular graphs are calledquartic, and a graph is calledsubcubic, if its maximum degree is at most3. Two edges inGare calledadjacent, if they share a common vertex.

Operations on graphsAsubgraphofGis a graphG 0 withV(G 0 )⊆V(G)andE(G 0 )⊆ E(G) each subset. ForT⊆V(G), we defineG[T]to be the subgraph with vertex setTand the maximal edge set, i.e.E(G[T]) =  {v, w} ∈E(G) :v, w∈T  . Those

4

1.2 Notation

subgraphs are calledinduced subgraphs, while subgraphs that contain all vertices ofG are calledspanning. The edge sets of subgraphs of maximum degree at most one are calledmatchings. ForX⊆V(G), letG−Xbe the induced subgraphG[V(G)\X], and forv∈V(G)we defineG−v:=G− {v}. ForY⊆E(G), letG−Ybe the spanning subgraph ofGwith edge setE(G)\Y, and fore∈E(G)we defineG−e:=G− {e}oT. avoid an ambiguity, the expressionG− {u, v}withu, v∈V(G)always denotes a deletion of two vertices instead of one edge, since the edge deletion can be expressed byG−uv. ThecomplementGis given byV(G) =V(G), andE(G) =  V( 2 G)  \E(G) a set. For Y⊆E(G), letG+Ybe the graph with vertex setV(G)and edge setE(G)∪Y, and for a single edgee∈E(G), we defineG+e:=G+{e}. IfG 1 andG 2 are two graphs, then the cartesian productG 1 G 2 ofG 1 andG 2 is the graphGwith vertex setV(G 1 )×V(G 2 ) and edge set E(G) =  {(a, b),(c, d)} ⊆V(G) :  (a=c)∧(b, d)∈G 2  ∨  (a, c)∈G 1 ∧(b=d)  }  .

IfXis a nonempty set of vertices in a graphG, then thevertex identificationwith respect toXyields the graphG 0 with vertex setV(G 0 ) = (V(G)\X)∪ {ξ}and edge set

E(G 0 ) =E(G−X)∪ {ξw:∃x∈X, w6∈X:xw∈E(G)}.

IfX={u, v}induces a connected subgraph inG, then the vertex identification ofXis called acontraction.

MorphismsAhomomorphismϕfromG→G 0 between two graphs is a mapϕ:V(G)→ V(G 0 )with∀e∈E(G) :ϕ(e)∈E(G 0 ). AnisomorphismϕbetweenGandG 0 is a bijective mapϕ:V(G)→V(G 0 )such thatϕandϕ −1 are homomorphisms. In many situations, it is common to talk about specific graphs instead of isomorphism classes: For example, the statement “The graphGdoes not containK 3 3 as a subgraph” , usually only means thatGcontains no subgraph which isisomorphictoK 3,3 . Similarly, lists of graphs with special properties should be understood as lists as isomorphism classes of graphs. We adopt this simplified notation although it is imprecise.

Special graphsThe following special graph classes are used throughout the following text. For a setL={l 1 , . . . , l k } ⊆Z/nZ, we define thecirculant graphCi n [l 1 , . . . , l k ]to be the graph with vertex set{v i } i∈Z/nZ and edge set  v i v j :i−j∈L}  . Graphs that are isomorphic toK n :=Ci n [1, . . . , n]are calledcompletegraphs onn thatvertices. Graphs are isomorphic toC n :=Ci n [1]are calledcycles, ifn≥3 that are isomorphic. Graphs toP n withP 1 =K 1 ,P 2 =K 2 andP n =C n −v 1 v n forn≥3are calledpathswith endverticesv 1 andv n . An expression of the form “P=x 1 x 2 . . . x n ” defines a pathP on the vertex set{x 1 , . . . , x n }in which two vertices are adjacent if and only if they are consecutive entries of the sequence. Similarly, a cycle can be given by a sequence x 1 x 2 . . . x n x 1  Theof vertices.lengthof a path or a cycle is its size. A cycle of lengthk is called ak-cycle.

5

G− ∙ ∙ ∙

G− {u, v}

G G+∙ ∙ ∙

G 1 G 2

caveat

Ci n [. . .]

K n ,C n ,P n