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"”.

  1. 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 …

    byu Repository record for A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes (opens in a new tab) Download PDF for A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes (opens in a new tab)

  2. 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 …

    uvic Repository record for Chordality of digraphs, signed graphs, and signed bigraphs (opens in a new tab)

  3. 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 …

    byu Repository record for The Minimum Rank Problem Over Finite Fields (opens in a new tab) Download PDF for The Minimum Rank Problem Over Finite Fields (opens in a new tab)

  4. 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, …

    uiuc Repository record for Extremal problems in disjoint cycles and graph saturation (opens in a new tab)

  5. 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 …

    montana Repository record for ON THREE GENERALIZATIONS OF THE TURÁN PROBLEM (opens in a new tab)

  6. 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 …

    montana-tech Repository record for ON THREE GENERALIZATIONS OF THE TURÁN PROBLEM (opens in a new tab)

  7. 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$ …

    uiuc Repository record for Problems in extremal graph theory (opens in a new tab)

  8. 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 …

    iastate Repository record for Efficient processing of hierarchical graphs (opens in a new tab)

  9. 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 …

    glasgow Repository record for Dynamically weakened constraints in bounded search for constraint optimisation problems (opens in a new tab) Download PDF for Dynamically weakened constraints in bounded search for constraint optimisation problems (opens in a new tab)

  10. 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 …

    utahstate Repository record for Hamiltonicity, Pancyclicity, and Cycle Extendability in Graphs (opens in a new tab)

  11. 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 …

    clemson Repository record for Intersections and Representations of Graphs (opens in a new tab)