Exercises in Graph Theory by O. Melnikov, V. Sarvanov, R.I. Tyshkevich, V. Yemelichev,

By O. Melnikov, V. Sarvanov, R.I. Tyshkevich, V. Yemelichev, Igor E. Zverovich

This e-book vitamins the textbook of the authors" Lectures on Graph The­ ory" [6] through greater than thousand workouts of various complexity. The books fit one another of their contents, notations, and terminology. The authors wish that either scholars and teachers will locate this ebook priceless for studying and verifying the knowledge of the peculiarities of graphs. The workouts are grouped into 11 chapters and diverse sections accord­ ing to the themes of graph idea: paths, cycles, parts, subgraphs, re­ constructibility, operations on graphs, graphs and matrices, timber, independence, matchings, coverings, connectivity, matroids, planarity, Eulerian and Hamiltonian graphs, measure sequences, shades, digraphs, hypergraphs. each one part starts off with major definitions and short theoretical discussions. They represent a minimum history, only a reminder, for fixing the workouts. the awarded evidence and a extra prolonged exposition can be present in Proofs of the pointed out textbook of the authors, in addition to in lots of different books in graph concept. so much routines are provided with solutions and tricks. in lots of instances whole ideas are given. on the finish of the publication you'll locate the index of phrases and the word list of notations. The "Bibliography" checklist refers simply to the books utilized by the authors in the course of the coaching of the exercisebook. basically, it mentions just a fraction of accessible books in graph conception. the discovery of the authors used to be additionally pushed via a number of magazine articles, that are most unlikely to record here.

Show description

Read or Download Exercises in Graph Theory PDF

Best graph theory books

Spectra of graphs. Theory and application

The idea of graph spectra can, in a fashion, be regarded as an try to make the most of linear algebra together with, particularly, the well-developed conception of matrices for the needs of graph concept and its functions. although, that doesn't suggest that the idea of graph spectra may be decreased to the idea of matrices; to the contrary, it has its personal attribute positive factors and particular methods of reasoning totally justifying it to be handled as a idea in its personal correct.

Graph Theory and Interconnection Networks

The development of enormous scale built-in circuit know-how has enabled the development of advanced interconnection networks. Graph concept presents a basic instrument for designing and interpreting such networks. Graph thought and Interconnection Networks presents an intensive knowing of those interrelated themes.

Fractional Graph Theory

"Both authors are first-class expositors-exceptionally so-and this makes for a pleasant learn and makes it possible for transparent realizing of the mathematical ideas. " -Joel Spencer Fractional Graph concept explores a number of the ways that integer-valued graph conception innovations may be changed to derive nonintegral values.

Extra resources for Exercises in Graph Theory

Example text

18. Does there exist a graph with exactly two skeletons? 19. Which graphs are such that every skeleton has exactly two pendant vertices? 20. Draw a graph that has two skeletons with disjoint edge sets. 21. Prove the following two statements for connected graphs. a) For any vertex v of a graph G there exists a spanning tree T of G such that dG(v, w) = dT(v, w) for any vertex wE VG. Here dH(V, w) denotes the distance between v and w in the graph H. b) The center of a graph is contained in the union of the centers of its skeletons.

14. Prove that every edge of a graph belongs to some skeleton of the graph. 15. Prove that a subgraph of a graph G is its skeleton if and only if it is a maximal subgraph of G without cycles. 2. 16. Let G be obtained by "gluing together" two connected graphs G I , Gil at a single vertex. Express the number of spanning trees of G in terms of the numbers of spanning trees of G I and Gil. 17. Prove that if a graph has a simple cycle of length k then the graph has at least k skeletons. 18. Does there exist a graph with exactly two skeletons?

37. Find a clique graph for the graph shown at Fig. 4. 38. Find the graphs Q(G) and L(G) for (a) G = Pn , (b) G = Cn . 39. Prove that if a graph G has no isolated vertices and triangles then Q( G) L(G). 40. Describe the structure of Q(L(K5» (the clique graph of the line graph of K5). 41. Prove that (a) every graph G with minimal degree 8(G) greater than 2 is isomorphic to an induced subgraph of Q(L(G)). (b) G ~ Q(L(G» if 8(G) > 1 and G is triangle-free. 42. If a graph G is isomorphic to the line graph of some graph then G is also called a line graph.

Download PDF sample

Rated 4.59 of 5 – based on 15 votes