Properties and structures in extremal graphs

The question of Turán on the maximum number of edges in a graph without containing complete graph K_r as a subgraph had been a starting point for the research in extremal graph theory. The complete graph K_r is called the forbidden subgraph in this case. Turán's question was then generalised to other set of forbidden subgraphs and known as Turán's type problem. Our research focuses on extremal graphs with forbidden subgraphs that are cycles of length 3 and 4. Knowing the existence of small cycles in a graph can be applied in the area of genome sequencing. Human genome contains many repeated DNA sequences and some DNA repeats are mutation "hot spots". If we modelled the genome sequencing using graphs and we glue the DNA repeats together, then those repeats will form a cycle in the graph. A short cycle in a graph provides the information that the repeats occur frequently. The detection of small cycles existence in the model graph is important since the repeats of certain DNA sequence indicated some diseases. Let n be the number of vertices in a graph. We were able to improve the known upper bound of the maximum number of edges for infinitely many values of n. Beside considering the maximum number of edges, we can consider graphs with maximum number of vertices. The well known degree diameter problem deals with the maximum number of vertices in a graph given a bounded degree and diameter. However, sometimes in daily life, there is not much freedom to arrange connections among objects. When the placement of edges is restricted by certain architectures/networks, then the solution from the degree diameter problem becomes inapplicable. Therefore, the maximum degree diameter bounded subgraph (MaxDDBS) problem was introduced to accommodate this restriction. Given a host graph, we try to construct the largest possible subgraph lying in the host graph subject to the given degree/diameter constraints. In the second part of our research, we solve the MaxDDBS on hyperdiamond networks, butterfly networks and Beneš network of given degree and diameter.