Maximally connected graphs and digraphs [Elektronische Ressource] / vorgelegt von Angelika Hellwig

Sujets

• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2005
• Nombre de lectures: 50
• Langue: Deutsch

Extrait

Maximally Connected Graphs and Digraphs
Von der Fakult at fur Mathematik, Informatik und Naturwissenschaften
der Rheinisch-Westf alischen Technischen Hochschule Aachen
zur Erlangung des akademischen Grades
eines Doktors der Naturwissenschaften
genehmigte Dissertation
vorgelegt von
Diplom-Mathematikerin
Angelika Hellwig
aus Aachen
Berichter: Professor Dr. Lutz Volkmann
Universit atsprofessor Dr. Eberhard Triesch
Tag der mundlic hen Prufung: 27.04.2005
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugbar.Danksagung
Mein ganz besonderer Dank gilt Herrn Prof. Dr. Lutz Volkmann fur die hervorra-
gende Betreuung dieser Doktorarbeit, die stetige Unterstutzung und Motivation, sowie
die vielen wertvollen Anregungen und Diskussionen.
Desweitern danke ich Herrn Prof. Dr. Eberhard Triesch dafur, dass er meine Auf-
nahme ins Graduiertenkolleg -Hierarchie und Symmetrie in mathematischen Modellen-
unterstutzt hat und sich als Korreferent zur Verfugung gestellt hat.
Herrn Prof. Dr. Peter Dankelmann und Herrn Prof. Dr. Dieter Rautenbach danke
ich fur die produktive Zusammenarbeit.
Ausserdem danke ich allen Mitarbeitern des Lehrstuhls II, meinen Eltern, Herrn
Hermann Luc ken und Frau Vera Tognazzi fur ihre Unterstutzung beim Entstehen dieser
Arbeit.Preface
Graphs are often used as a model for networks, for example transport networks,
telecommunication systems, a network of servers and so on. Typically, the networks
and thus the representing graphs are connected; that means, that there exists a path
between all pairs of two vertices in the graph. But sometimes an element of the net-
work fails, for the graphs that means the removal of a vertex or an edge. Clearly, it is
desirable that a network stays connected as long as possible in case faults should arise.
The graph theoretical parameter edge-connectivity (G) equals the minimum number
of edges, whose removal disconnects the graph. Analogougsly, the vertex-connectivity
(G) equals the minimum number of vertices, whose removal disconnects the graph.
By removing all vertices or edges adjacent to a vertex of minimum degree (G) the
resulting graph is always disconnected and hence(G)(G) and(G)(G): Thus,
in order to construct reliable and fault-tolerant networks one is interested in nding
su cien t conditions for graphs to satisfy (G) =(G) and (G) =(G): For the case
that graphs are maximally edge(vertex)-connected, further connectivity parameters are
needed in order to investigate the fault-tolerance. Such parameters are for example:
A graph is called super-edge-connected, if every minimum edge-cut consists of
edges incident to a vertex of minimum degree.
0The restricted edge-connectivity (G) equals the minimum cardinality over all
edge-cuts S in a graph G such that there are no isolated vertices in G S:
The p-q-restricted edge(vertex)-connectivity (G) ( ) is the minimum cardi-p;q p;q
nality of an edge(vertex)-cut S such that one component of G S contains at
least p vertices and another component of G S contains at least q vertices.
The local-edge-connectivity (u;v) of two vertices u and v equals the maximum
number of edge-disjoint u-v paths.
In this thesis, we mainly study su cien t conditions for these connectivity parameters
to be maximal.ii
After a short introduction to the used notations, we give in Chapter 2, 3, 4, 6
several su cien t conditions for graphs to be maximally edge-connected, super-edge-
connected, maximally restricted-edge-connected and maximally local-edge-connected,
respectively. Hereby we generalize some known results by Goldsmith and Entringer and
by Dankelmann and Volkmann. Furthermore we give analogue results to Xu’s theorem
for bipartite graphs. In Chapter 5 we characterize the graphs, where the parameter
exists.p;q
The Chapters 7 and 8 deal with vertex-connectivity parameters. In Chapter 7, we
will see that a result by Topp and Volkmann forp-partite graphs is also valid for graphs
having clique numberp, hence a generalization. Furthermore, we obtain some su cien t
conditions for diamond-free and C -free graphs to be maximally vertex-connected. In4
Chapter 8 we rst characterize the graphs, where the parameter exists. Then wep;q
describe the graphs, whose parameter is maximal.1;2
In Chapter 9 we study the relations between edge- and vertex-connectivity param-
eters. For arbitrary graphs G; we prove the inequality (G) (G): An example,1;p p;p
which shows that this inequality is the best possible, gives a negative answer to a
question raised by Harary. In 1983 he asked, if (G;P ) (G;P ); where (G;P )
((G;P )) equals the minimum cardinality of an edge(vertex)-cut S such that every
component of G S satis es a given property P: For line graphs we prove the in-
equality (L(G)) (G) p q (L(G)): With the help of this result wep 1;q 1 p;q ;( ) ( )2 2
obtain the equality (L(G)) = (G); which improves the results (L(G)) (G)2;2
and (L(L(G))) 2(G) 2 shown by Chartrand and Stewart in 1969.Contents
1 Introduction 3
1.1 General concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Edge-connectivity concepts . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Vertex-connectivity . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Relations between edge- and vertex-connectivity concepts . . . . . . . . 14
2 Edge-connectivity 17
2.1 Generalizations of a result by Goldsmith and Entringer . . . . . . . . . 17
2.2 Neighborhood of an edge . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Degree sequence conditions . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Distance maximal sets in arbitrary graphs . . . . . . . . . . . . . . . . 29
2.5 sets in bipartite . . . . . . . . . . . . . . . . 30
2.6 Analog results to Xu’s theorem for bipartite graphs . . . . . . . . . . . 31
2.7 A generalization of a result by Dankelmann and Volkmann . . . . . . . 33
3 Super-edge-connectivity 35
3.1 Arbitrary graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Bipartite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Restricted edge-connectivity 49
4.1 Arbitrary graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Graphs having diameter 2 . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Triangle-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.4 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.5 Graphs with given clique number . . . . . . . . . . . . . . . . . . . . . 66
5 p-q-restricted-edge-connectivity 69
5.1 Characterization of -connected graphs . . . . . . . . . . . . . . . . . 69p;q
6 Local-edge-connectivity 71
6.1 Digraphs having diameter 2 . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2 p-partite digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3 Bipartite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732 CONTENTS
7 Vertex-connectivity 79
7.1 Graphs with given clique number - A generalization of a result by Topp
and Volkmann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.2 Diamond-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.3 C -free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864
8 p-q-restricted-vertex-connectivity 91
q8.1 Characterization of -connected graphs . . . . . . . . . . . . . . . . . 91p
8.2 Properties of . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 921;2
9 Relations between edge- and vertex-connectivity 97
9.1 The inequality and an answer to a question of Harary . . . . 971;p p;p
9.2 Connectivity in line graphs . . . . . . . . . . . . . . . . . . . . . . . . . 98
Bibliography 100Chapter 1
Introduction
In this chapter we present the basic notation and terminology of graph theory which
will be used throughout this thesis. Special notations and de nitions will be presented
where needed. Hereby we mainly follow the given in the books of L. Volkmann
[53] and G. Chartrand and L. Lesniak [9]. For graph theory terminology not given here
we direct the reader to these books.
1.1 General concepts
1.1.1 (Undirected) graphs
We consider nite graphs without loops and multiple edges. For any graph G the
vertex set is denoted by V (G) and the edge set by E(G): We de ne the order of G
by n(G) =jV (G)j and the size by m(G) =jE(G)j: The vertex degree d(v) of a vertex
v2 V (G) of a graph G equals the number of vertices adjacent to v: Let (G) denote
the minimum vertex degree and ( G) the maximum vertex degree in G. The degree
sequence of a graph G is de ned as the non-increasing sequence of the degrees of the
vertices of G. For a vertex v2 V (G), the open neighborhood N(v) of v is the set
of all vertices adjacent to v and the closed neighborhood of v is N[v] = N(v)[fvg.S
Furthermore, N(A) = N(a)nA and N[A] = N(A)[A for a subset A of V (G).a2A
For a graph G, let (G) =d(x) +d(y) 2 be the edge degree of the edge e =xy ande
(G) denotes the minimum edge degree and ( G) the maximum edge degree in G: If
X V (G), then let G[X] be the subgraph induced by X. For any graph H a graph
G is H-free if G does not contain the graph H as an induced subgraph. A vertex set
A V (G) is called independent, if E(G[A]) =;: For two disjoint vertex sets X;Y
of a graph let (X;Y ) be the set of edges from X to Y