A Seminar on Graph Theory
eBook - ePub

A Seminar on Graph Theory

Frank Harary

Share book
  1. 128 pages
  2. English
  3. ePUB (mobile friendly)
  4. Available on iOS & Android
eBook - ePub

A Seminar on Graph Theory

Frank Harary

Book details
Book preview
Table of contents
Citations

About This Book

Presented in 1962–63 by experts at University College, London, these lectures offer a variety of perspectives on graph theory. Although the opening chapters form a coherent body of graph theoretic concepts, this volume is not a text on the subject but rather an introduction to the extensive literature of graph theory. The seminar's topics are geared toward advanced undergraduate students of mathematics.
Lectures by this volume's editor, Frank Harary, include `Some Theorems and Concepts of Graph Theory,` `Topological Concepts in Graph Theory,` `Graphical Reconstruction,` and other introductory talks. A series of invited lectures follows, featuring presentations by other authorities on the faculty of University College as well as visiting scholars. These include `Extremal Problems in Graph Theory` by Paul Erdös, `Complete Bipartite Graphs: Decomposition into Planar Subgraphs,` by Lowell W. Beineke, `Graphs and Composite Games,` by Cedric A. B. Smith, and several others.

Frequently asked questions

How do I cancel my subscription?
Simply head over to the account section in settings and click on ā€œCancel Subscriptionā€ - itā€™s as simple as that. After you cancel, your membership will stay active for the remainder of the time youā€™ve paid for. Learn more here.
Can/how do I download books?
At the moment all of our mobile-responsive ePub books are available to download via the app. Most of our PDFs are also available to download and we're working on making the final remaining ones downloadable now. Learn more here.
What is the difference between the pricing plans?
Both plans give you full access to the library and all of Perlegoā€™s features. The only differences are the price and subscription period: With the annual plan youā€™ll save around 30% compared to 12 months on the monthly plan.
What is Perlego?
We are an online textbook subscription service, where you can get access to an entire online library for less than the price of a single book per month. With over 1 million books across 1000+ topics, weā€™ve got you covered! Learn more here.
Do you support text-to-speech?
Look out for the read-aloud symbol on your next book to see if you can listen to it. The read-aloud tool reads text aloud for you, highlighting the text as it is being read. You can pause it, speed it up and slow it down. Learn more here.
Is A Seminar on Graph Theory an online PDF/ePUB?
Yes, you can access A Seminar on Graph Theory by Frank Harary in PDF and/or ePUB format, as well as other popular books in Mathematik & Diskrete Mathematik. We have over one million books available in our catalogue for you to explore.

Information

Year
2015
ISBN
9780486805146

[1]

Some Theorems and Concepts of Graph Theory

The field of graph theory is even today being independently rediscovered by scholars in various disciplines as they require its techniques for the solution of their structural and combinatorial problems. In recent years, this subject has been receiving increasing attention and interest in mathematics and other sciences. The stimulus to the renaissance of graph theory stems from its wide applicability to many fields. In fact, the theory of graphs is now quite important not only in pure mathematics (combinatorial theory), but also in theoretical physics, electrical engineering, organic chemistry, social psychology, and operational research.
It is our hope that the presentation of some historical comments and illustrations, with the statements of selected theorems, will set the stage for the remaining lectures.
We will describe four independent approaches to graph theory:
(1) Euler: Kƶnigsberg Bridge Problem.
(2) Hamilton: Around the World.
(3) Cayley, Heawood: Four-color Conjecture.
(4) Kirchhoff, Cayley, Jordan, Sylvester: Trees.

Kƶnigsberg Bridge Problem

Euler (1707-1782) became the father of graph theory, as well as the rest of topology, when he settled a famous problem of his day called the Kƶnigsberg bridge problem [4]. The area in question contains two islands linked to each other and to the banks of the Pregel River by seven bridges, as in Fig. 1.1.
The problem was to begin at any of the four land areas and, without swimming or flying or travelling around the world, cross each bridge exactly once and return to the starting point. One can see immediately that there are many ways of attempting this problem without solving it.
The considerable contribution of Euler in this case was negative, for he proved that the problem is unsolvable. He replaced each land area by a point and each bridge by a line joining the corresponding points. The result, shown in Fig. 1.2, is a collection of points with lines joining them. The points, labeled a, b, c, and d, correspond to the land areas of Fig. 1.1.
images
Fig. 1.1. The Kƶnigsberg bridge problem.
images
Fig. 1.2. The ā€œmultigraphā€ of the Kƶnigsberg bridge problem.
images
Fig. 1.3. A (4, 5) graph with points and lines labeled.
Since almost any two graph theorists use different terminology, and since we wish this exposition to be self-contained, we will preface a precise formulation of the problem with a rather substantial list of definitions.
A graph G consists of a finite nonempty set V of points and a set X of lines, each of which joins two distinct points. We assume that distinct lines do not join the same pair of points; otherwise, as in Fig. 1.2, the configuration is a multigraph. Furthermore, if we permit loops, that is, lines joining a point with itself, the result is a general graph. A (p, q) graph has p points and q lines. The number of points in a graph is called its order. Fig. 1.3 shows a (4, 5) graph with points and lines labeled, i.e., designated by symbols.
The two points joined by a line are adjacent, and each is incident with the line. Two graphs are isomorphic if there is a one-to-one correspondence between their sets of points preserving adjacency. The degree d(v) of a point v is the number of lines incident with it. A point of degree 0 is isolated, and the graph consisting of such a point is called trivial. In a regular graph all points have the same degree. A regular graph in which every point has degree 3 is called cubic. The complete graph Kp of order p has every pair of its points adjacent and so is regular of degree p ā€“ 1. All the complete graphs with up to five points are shown in Fig. 1.4.
A walk in a graph G is an alternating sequence of points and lines of G, beginning and ending with a point, in which each line is incident with the point preceding it and the point following it. A walk of the form v1, x1, v2, x2, v3 Ā· Ā· Ā·, vn is said to join v1 with vn. The length of a walk is the number of occurrences of lines in it. A trail is a walk in which all lines are distinct. A path is a walk in which all points (and hence all lines) are distinct. A closed walk has the same first and last points. The walk v1, x1, v2, x2, Ā· Ā· Ā·,vn is often written v1v2Ā· Ā· Ā·vn, the lines being evident by context. A cycle is a closed walk v1v2Ā· Ā· Ā·vnv1, n ā‰„ 3, in which the n points vi are distinct. A spanning walk (spanning path, spanning cycle, and so on) contains all the points of G.
Some of these concepts are illustrated in Fig. 1.3. The walk v1v2v3v4. is a path; in fact, it is a spanning path. The cycle v1v2v4v1 has length 3, and v2v1v4v2v3vA, is a trail containing all lines.
In a connected graph, every pair of distinct points is joined by a path. A subgraph of G consists of subsets of V and X which themselves form a graph.
images
Fig. 1.4. The smallest complete graphs.
A component of G is a maximal connected subgraph. Ob...

Table of contents