Some counting problems in graphs

Abstract

This doctoral thesis is based on six research papers. We give upper and lower bounds on the number of subsets of the vertex set of a graph with certain properties, often we also characterize the extremal graphs. The results can be divided in four main parts. In the first part we give upper bounds on the number of maximum independent sets in connected graphs and trees in terms of the independence number and the order of a graph. We examine a similar problem for dominating sets in the second part by giving upper bounds on the number of minimum (total) dominating sets in forests. We give tight lower bounds on the number of rainbow triangles in edge colored graphs in terms of the number of colors and the number of edges of the graph in the third part of the thesis. We also characterize the extremal graphs. In the last part we give a tight upper bound on the number of Hamiltonian cycles in claw-free cubic graphs and characterize the set of graphs that fulfill this bound with equality.