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 12 of 12 for “"forbidden subgraph"”.
-
A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes
… In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such …
-
Chordality of digraphs, signed graphs, and signed bigraphs
… enjoy beautiful characterizations, in terms of forbidden subgraphs, vertex or edge orderings, and tree-like representations. A digraph analogue of chordal graphs was introduced by Haskins and Rose. Unfortunately, a forbidden subdigraph characterization of chordal digraphs is not known and …
-
The Minimum Rank Problem Over Finite Fields
… bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs and show that many of these are minimal forbidden subgraphs for any field. Our second main result …
-
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, …
-
ON THREE GENERALIZATIONS OF THE TURÁN PROBLEM
… edges in an n-vertex graph subject to some forbidden subgraph condition. Namely, we work in the areas of generalized Turán problems, rainbow Turán problems, and positive co-degree problems. Our main contribution to generalized Turán theory is a general supersaturation result. We also obtain …
-
ON THREE GENERALIZATIONS OF THE TURÁN PROBLEM
… edges in an n-vertex graph subject to some forbidden subgraph condition. Namely, we work in the areas of generalized Turán problems, rainbow Turán problems, and positive co-degree problems. Our main contribution to generalized Turán theory is a general supersaturation result. We also obtain …
-
Problems in extremal graph theory
… {\it minor} of $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges. We show that the upper bound for $\chi(G^2)$ conjectured by Wegner (1977) for planar graphs holds when $G$ is a $K_4$-minor-free graph. We also show that $\chi(G^2)$ is equal to the bound only when $G^2$ …
-
Efficient processing of hierarchical graphs
… to three classes: connectivity augmentation, subgraph homeomorphism, and matroid optimization. The P-connectivity augmentation problem, where P is a connectivity property, is to determine the number of edges that must be added to a graph to satisfy P. We present polynomial-time hierarchical …
-
Dynamically weakened constraints in bounded search for constraint optimisation problems
… solving extremal graph problems. We use the forbidden subgraph problem to show that our approach of using decision diagram branch and bound as a search scheme in a constraint solver can be paired with canonical search. Canonical search is a technique for graph search which ensures that no two …
-
Hamiltonicity, Pancyclicity, and Cycle Extendability in Graphs
… it is cycle extendable. A graph H is an induced subgraph of another graph G if H can be obtained from G by deleting vertices. A graph is said to be chordal if it has no cycle on four or more vertices as an induced subgraph; that is, every cycle long enough to have a chord (an edge connecting two …
-
Intersections and Representations of Graphs
… complete 4-partite graph K3,3,3,3 is a minimal forbidden subgraph. The parity of the subpaths affects the representation; graphs in which the subpaths are of a fixed odd order are strongly chordal (in fact, these are precisely the unit interval graphs), and graphs in which the subpaths are all …