By R. Balakrishnan, K. Ranganathan

 This moment variation contains new chapters: one on domination in graphs and the opposite at the spectral houses of graphs, the latter including a dialogue on graph energy.  The bankruptcy on graph colours has been enlarged, overlaying extra subject matters similar to homomorphisms and colors and the individuality of the Mycielskian as much as isomorphism. 

This publication additionally introduces numerous fascinating themes equivalent to Dirac's theorem on k-connected graphs, Harary-Nashwilliam's theorem at the hamiltonicity of line graphs, Toida-McKee's characterization of Eulerian graphs, the Tutte matrix of a graph, Fournier's facts of Kuratowski's theorem on planar graphs, the evidence of the nonhamiltonicity of the Tutte graph on forty six vertices, and a concrete program of triangulated graphs.

Show description

Read or Download A Textbook of Graph Theory PDF

Best graph theory books

A Beginner's Guide to Discrete Mathematics

Wallis's booklet on discrete arithmetic is a source for an introductory direction in a subject matter primary to either arithmetic and desktop technological know-how, a direction that's anticipated not just to hide sure particular themes but additionally to introduce scholars to special modes of notion particular to every self-discipline .

Geometric Methods in Bio-Medical Image Processing

The genesis of this e-book is going again to the convention held on the college of Bologna, June 1999, on collaborative paintings among the college of California at Berkeley and the college of Bologna. The publication, in its current shape, is a compilation of a few of the new paintings utilizing geometric partial differential equations and the extent set method in scientific and biomedical photo research.

Visualization for Computer Security: 5th International Workshop, VizSec 2008, Cambridge, MA, USA, September 15, 2008. Proceedings

This e-book constitutes the refereed complaints of the fifth overseas Workshop on Visualization for Cyber safeguard hung on September 15, 2008, in Cambridge, Massachusetts, united states, together with the eleventh overseas Symposium on fresh Advances in Intrusion Detection (RAID). The 18 papers provided during this quantity have been rigorously reviewed and chosen from 27 submissions.

Additional resources for A Textbook of Graph Theory

Example text

Then ¢-I(V') is a vertex of G 1 incident to both e, and ej so that e, and e j are adjacent vertices of L( G 1). Thus, e, and e j are adjacent vertices of L(G'> if, and only if, B(ei) and B(ej) are adjacent vertices of L(G 2). Hence B is an isomorphism of L(Gh onto L(G 2). 2 is not true . 3 and K3. Theirline graphs are K 3. 3 whereas there is no such vertex in K3. 4 shows that the above two graphs are the only two exceptional simple graphs of this type. 4* (H. Whitney) Let G and G' be simple connected graphs with isomorphic line graphs.

3-regular) connected graph G has a cut vertex if, and only if, it ha s a cut edge. Proof Let G have a cut vertex vo. Let Vt, V2 , V3 be the vertices of G that are adjacent to Vo in G. Consider G-vo, which has either two or three components. If G-vo has three components, no two of VI , V2 , and V3 can belong to the same component of G-vo. In this case, each of VoVt. VOV2, and VOV3 is a cut edge of G. ) In the case when G-vo has only two components, one of the vertices, say VI , belongs to one component of G-vo, and V2 and V3 belong to the other component.

An ordered triple (u , u, w) of vertices of T is a transitive triple of T if whenever (u , v ) E A(T) and (u , w) E A (T) , then (u , w) E A(T) . 8. 6 1. If v is any vertex of T and u , ware two outne ighbors of v , then {u , v, w} determines a unique transitive triple in T. Such a transitive triple is said to be defined by the vertex v. Clearly, any transitive triple of T is defined by some vertex of T . Further, the number of transitive triples defined by v is ( S~») . 2. The number of directed 3-cycle s in a tournament T of order n is obtained by subtracting the total number of transitive triples of vertices of T from the total number of triples of vertice s of T .

Download PDF sample

Download A Textbook of Graph Theory by R. Balakrishnan, K. Ranganathan PDF
Rated 4.96 of 5 – based on 38 votes