Please use this identifier to cite or link to this item: https://www.um.edu.mt/library/oar/handle/123456789/119419
Title: Feasibility and forbidden subgraphs
Authors: Cassar, Matthew (2023)
Keywords: Graph theory
Issue Date: 2023
Citation: Cassar, M. (2023). Feasibility and forbidden subgraphs (Master's dissertation).
Abstract: The topics of feasibility and forbidden subgraphs are two topics that are very well-known in the area of graph theory. This thesis aims to delve into both areas and continue to build on the results already proved, with a particular focus on the feasibility of line graphs. This thesis is sectioned into two main parts, where the first part consists of two chapters containing some basic definitions and results, as well as results on forbidden subgraphs. In the former, the definitions which will be used throughout the text are provided, as well as some basic results and concepts which are used in the theorems and examples that follow. The latter chapter consists of three parts, where the first part contains results on the forbidden subgraphs in extremal graph theory, while the second part mainly focuses on subdivisions and minors. In this part, several results are provided, most of which are also proved, such as the fact that both K5 and K3,3 are not planar, Kuratowski’s Theorem with a proof, as well as results on outerplanar graphs. The last part of this chapter introduces results on forbidden induced subgraphs. It incorporates results on the relation between chordal graphs and split graphs, results on forbidden subgraphs and line graphs, and finally, a note on Hamiltonicity, together with some theorems and conjectures related to this area, are also provided. The second part of the this thesis contains a chapter on feasibility, which essentially is the question of how many edges a graph on H vertices can have if it does not contain a forbidden induced subgraph or a family of such subgraphs. We focus in particular on the feasibility of H-free graphs, mainly paw-free graphs and H-free graphs where H is an extension of the paw graph, and conclude with a section on future work that can be done in this area of feasibility. The main results and observations in the paper Feasibility of Line Graphs, by Caro, Lauri & Zarb, which was the main inspiration behind this thesis, are presented and discussed in more detail. A technique used in this paper (the Universal Elimination Procedure construction) is complemented by a new construction (the Edge Elimination construction) to give further feasibility results, which are the main new findings of this thesis. These results are further explained with concrete examples. The last part of this thesis includes possible improvements on the results obtained in this study, as well as a conjecture on the feasibility of F-free graphs, where F is a family of at least two independent forbidden graphs. One of the independent forbidden graphs is proven to be feasible by the Universal Elimination Procedure construction, but not feasible by the Edge Elimination method, while the other graph can be solved by the Edge Elimination method but not by the Universal Elimination Procedure.
Description: M.Sc.(Melit.)
URI: https://www.um.edu.mt/library/oar/handle/123456789/119419
Appears in Collections:Dissertations - FacSci - 2023
Dissertations - FacSciMat - 2023

Files in This Item:
File Description SizeFormat 
2418SCIMAT500305056409_1.PDF
  Restricted Access
2.55 MBAdobe PDFView/Open Request a copy


Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.