- Title
- Properties and structures in extremal graphs
- Creator
- Bong, Novi Herawati
- Relation
- University of Newcastle Research Higher Degree Thesis
- Resource Type
- thesis
- Date
- 2017
- Description
- Research Doctorate - Doctor of Philosophy (PhD)
- Description
- The question of Turán on the maximum number of edges in a graph without containing complete graph Kr as a subgraph had been a starting point for the research in extremal graph theory. The complete graph Kr 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.
- Subject
- extremal graph theory; degree/diameter problem; MaxDDBS problem; EX graphs
- Identifier
- http://hdl.handle.net/1959.13/1333547
- Identifier
- uon:27099
- Rights
- Copyright 2017 Novi Herawati Bong
- Language
- eng
- Full Text
- Hits: 772
- Visitors: 1383
- Downloads: 656
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Thesis | 2 MB | Adobe Acrobat PDF | View Details Download | ||
| View Details Download | ATTACHMENT02 | Abstract | 251 KB | Adobe Acrobat PDF | View Details Download |