Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 10 of 10 for “"extremal graphs"”.
-
Cliques in graphs
… the minimal number of $r$-cliques in graphs with $n$ vertices and minimum degree~$\delta$. A fundamental result in Graph Theory states that a triangle-free graph of order $n$ has at most $n^2/4$ edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if $k_3(n,\delta) …
-
Eindeutige Faktoren von Graphen - maximale Kantenzahlen und Extremalgraphen
We are given a set V of vertices and a class of graphs on V. In this paper we examine the following question: What is the maximum number of edges in a graph on V, which contains exactly one graph of the class as a subgraph? What can we say about the corresponding extremal graphs? In this thesis we …
-
Regular factors in graphs
… a unique regular factor. The focus will be on extremal bipartite graphs with a unique regular factor. An analysis of the structure shows that all extremal bipartite graphs with a unique k-factor have exactly 2k vertices of minimum degree. This result allows for positive answers on the maximal …
-
On Topological Indices And Domination Numbers Of Graphs
… on these two topics. We study k-trees and cactus graphs with the sharp upper and lower bounds of the degree-based topological indices(Multiplicative Zagreb indices). The extremal cacti with a distance-based topological index (PI index) are explored. Furthermore, we provide the extremal graphs with …
-
Enumerating combinatorial objects with limited sub-configurations
Many well-studied problems in extremal combinatorics concern the number and the typical structure of discrete objects with forbidden substructures. Over the past decades, such problems have been extensively studied for various objects by many notable researchers. This thesis focuses on several …
-
Improving the capacity of radio spectrum: exploration of the acyclic orientations of a graph
… Firstly, we obtain computational results for all graphs with up to 8 vertices. We use the data to make observations on the structure of minimal and maximal graphs, by which we mean graphs with the fewest and greatest number of acyclic orientations respectively, as well as on the distribution of …
-
Distances in planar graphs
… results and methods of papers studying planar graphs, particularly those solving the degree diameter problem for various kinds of ρ-facedegree regular graphs. In this review, we provide a correction to an error in The degree/diameter problem in maximal planar bipartite graphs by Dalf´o, Huemer …
-
Extremal problems in disjoint cycles and graph saturation
… conditions for the existence of particular subgraphs in a graph, and variations on graph saturation. Determining whether a graph contains a certain subgraph is a computationally difficult problem; as such, sufficient conditions for the existence of a given subgraph are prized. In Chapter 2, we …
-
Multiple domination in graphs
… already much studied concept of domination in graphs. In particular, we are interested in finding k-dominating sets of minimum cardinality. Inspired by Fink and Jacobson, Cockayne, Gamble and Shepherd proved in the same year that the k- domination of every graph with minimum degree at least k …
-
Problems in extremal combinatorics
We consider a variety of problems in extremal graph and set theory. Given a property $\Gamma$ and a family of sets ${\mathcal F}$, let $f({\mathcal F},\Gamma)$ be the size of the largest subfamily of ${\mathcal F}$ having property $\Gamma$. Let $f(m,\Gamma)$ be the minimum of $f({\mathcal …