Graph Polynomials and Graph Transformations in Algebraic Graph Theory

Abstract

The thesis consists of two parts. In the first part we study two graph transformations, namely the Kelmans transformation and the generalized tree shift. In the second part of this thesis we study an extremal graph theoretic problem and its relationship with algebraic graph theory. The main results of this thesis are the following. • We show that the Kelmans transformation is a very effective tool in many extremal alge- braic graph theoretic problems. Among many other things, we attain a breakthrough in a problem of Eva Nosal by the aid of this transformation. • We define the generalized tree shift which turns out to be a powerful tool in many extremal graph theoretic problems concerning trees. With the aid of this transformation we prove a conjecture of V. Nikiforov. We give a strong method for attacking extremal graph theoretic problems involving graph polynomials and trees. By this method we give new proofs for several known results and we attain some new results. • We completely solve the so-called density Turan problem for trees and we give sharp bounds for the critical edge density in terms of the largest degree for every graphs. We establish connection between the problem and algebraic graph theory. By the aid of this connection we construct integral trees of arbitrarily large diameters. This was an open problem for more than 30 years.