Graphs & digraphs / G. Chartrand and L. Lesniak.

Format:

Book

Author/Creator:

Chartrand, Gary.

Contributor:

Lesniak, Linda.

Classes of 1883 and 1884 Fund.

Language:

English

Subjects (All):

Graph theory.

Directed graphs.

Physical Description:

viii, 386 pages : illustrations ; 25 cm

Edition:

Fourth edition.

Other Title:

Graphs and digraphs

Place of Publication:

Boca Raton : Chapman & Hall/CRC, [2005]

Contents:

1 Introduction to graphs and digraphs 1

1.1 Graphs 1

1.2 Degree sequences 12

1.3 Connected graphs and distance 16

1.4 Digraphs and multigraphs 25

2 The structure of graphs 33

2.1 Cut-vertices, bridges and blocks 33

2.2 The automorphism group of a graph 38

2.3 Cayley color graphs 43

2.4 The reconstruction problem 47

3 Trees and connectivity 55

3.1 Elementary properties of trees 55

3.2 Arboricity and vertex-arboricity 65

3.3 Connectivity and edge-connectivity 69

3.4 Menger's theorem 75

3.5 The toughness of a graph 81

4 Eulerian and hamiltonian graphs and digraphs 85

4.1 Eulerian graphs and digraphs 85

4.2 Hamiltonian graphs and digraphs 92

4.3 Line graphs and powers of graphs 105

5 Directed graphs 111

5.1 Strong digraphs 111

5.2 Tournaments 113

5.3 Hamiltonian tournaments 124

6 Planar graphs 127

6.1 The Euler identity 127

6.2 Characterizations of planar graphs 135

6.3 Hamiltonian planar graphs 145

6.4 Crossing number and thickness 150

7 Graph embeddings 161

7.1 The genus of a graph 161

7.2 2-Cell embeddings of graphs 170

7.3 The maximum genus of a graph 186

8 Graph colorings 193

8.1 Vertex colorings 193

8.2 Edge colorings 209

8.3 Map colorings and flows 216

9 Matchings, factors and decompositions 233

9.1 Matchings and independence in graphs 233

9.2 Factorizations and decompositions 246

9.3 Labelings of graphs 262

10 Domination in graphs 273

10.1 The domination number of a graph 273

10.2 The independent domination number of a graph 283

10.3 Other domination parameters 286

11 Extremal graph theory 293

11.1 Turan's theorem 293

11.2 Extremal results on graphs 298

11.3 Cages 308

12 Ramsey theory 317

12.1 Classical Ramsey numbers 317

12.2 Generalized Ramsey theory 323

12.3 Rainbow Ramsey numbers 327

13 The probabilistic method in graph theory 333

13.1 The probabilistic method 333

13.2 Random graphs 340

Graph theory books 1936-2004 351.

Notes:

Includes bibliographical references and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Classes of 1883 and 1884 Fund.

ISBN:

1584883901

OCLC:

55510638