We first prove a ``non-embeddable extensions' theorem for polyhedral graph embeddings. Let G be a ``weakly 4-connected' planar graph. We describe a set of constructions that produce a finite list of non-planar graphs, each having a minor isomorphic to G, such that every non-planar weakly 4-connected graph H that has a minor isomorphic to G has a minor isomorphic to one of the graphs in the list. The theorem is more general and applies in particular to polyhedral embeddings in any surface. We discuss an approach to proving Jorgensen's conjecture, which states that if G is a 6-connected graph with no K_6 minor, then it is apex, that is, it has a vertex v such that deleting v yields a planar graph. We relax the condition of 6-connectivity, and prove Jorgensen's conjecture for a certain sub-class of these graphs. We prove that every graph embedded in the Klein bottle with representativity at least 4 has a K_6 minor. Also, we prove that every ``locally 5-connected' triangulation of the torus, with one exception, has a K_6 minor. (Local 5-connectivity is a natural notion of local connectivity for a surface embedding.) The above theorem uses a locally 5-connected version of the well-known splitter theorem for triangulations of any surface. We conclude with a theoretically optimal algorithm for the following graph connectivity problem. A shredder in an undirected graph is a set of vertices whose removal results in at least three components. A 3-shredder is a shredder of size three. We present an algorithm that, given a 3-connected graph, finds its 3-shredders in time proportional to the number of vertices and edges, when implemented on a RAM (random access machine).

Thesis (Ph. D.)--Rutgers University, 2009. / "Graduate Program in Mathematics." Includes bibliographical references (p. 57-58).

Thesis (M.S.)--West Virginia University, 2002. / Title from document title page. Document formatted into pages; contains iii, 19 p. Includes abstract. Includes bibliographical references (p. 17-19).

Thesis (Ph. D.)--West Virginia University, 2003. / Title from document title page. Document formatted into pages; 1 v. (various pagings) : ill. (some col.). Vita. Includes abstract. Includes bibliographical references.

published_or_final_version / abstract / toc / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

No description available.

No description available.

Given two set systems $\mathscr{A}$ and $\mathscr{B}$ over an $n$-element set, we say that $(\mathscr{A,B})$ forms a recovering pair if the following conditions hold: \\ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr{B}$, $A \setminus B = A' \setminus B' \Rightarrow A=A'$ \\ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr {B}$, $B \setminus A = B' \setminus A' \Rightarrow B=B'$ \\ In 1989, G\'bor Simonyi conjectured that if $(\mathscr)$ forms a recovering pair, then $|\mathscr||\mathscr|\leq 2^n$. This conjecture is the focus of this thesis. This thesis contains a collection of proofs of special cases that together form a complete proof that the conjecture holds for all values of $n$ up to 8. Many of these special cases also verify the conjecture for certain recovering pairs when $n>8$. We also present a result describing the nature of the set of numbers over which the conjecture in fact holds. Lastly, we present a new problem in graph theory, and discuss a few cases of this problem.

No description available.

For any graph parameter, the removal of a vertex from a graph can increase the parameter, decrease the parameter, or leave the parameter unchanged. This dissertation focuses on the case where the removal of a vertex decreases the parameter for the cases of independent domination and total domination. A graph is said to be independent domination vertex-critical, or i-critical, if the removal of any vertex decreases the independent domination number. Likewise, a graph is said to be total domination vertex-critical if the removal of any vertex decreases the total domination number. Following these notions, a graph is independent domination bicritical, or i-bicritical, if the removal of any two vertices decreases the independent domination number, and a graph is total domination bicritical if the removal of any two vertices decreases the total domination number. Additionally, a graph is called strong independent domination bicritical, or strong i-bicritical, if the removal of any two independent vertices decreases the independent domination number by two. Construction results for i-critical graphs, i-bicritical graphs, strong i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs are studied. Many known constructions are extended to provide necessary and sufficient conditions to build critical and bicritical graphs. New constructions are also presented, with a concentration on i-critical graphs. One particular construction shows that for any graph G, there exists an i-critical, i-bicritical, and strong i-bicritical graph H such that G is an induced subgraph of H. Structural properties of i-critical graphs, i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs are investigated, particularly for the connectedness and edge-connectedness of critical and bicritical graphs. The coalescence construction, which has appeared in earlier literature, constructs a graph with a cut-vertex and this construction is studied in great detail for i-critical graphs, i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs. It is also shown that strong i-bicritical graphs are 2-connected and thus the coalescence construction is not useful in this case. Domination vertex-critical graphs (graphs where the removal of any vertex decreases the domination number) have been studied in the literature. A well-known result gives an upper bound on the diameter of such graphs. Here similar techniques are used to provide upper bounds on the diameter for i-critical graphs, strong i-bicritical graphs, and total domination critical graphs. The upper bound for the diameter of i-critical graphs trivially gives an upper bound for the diameter of i-bicritical graphs. For a graph G, the gamma-graph of G is the graph where the vertex set is the collection of minimum dominating sets of G. Adjacency between two minimum dominating sets in the gamma-graph occurs if from one minimum dominating set a vertex can be removed and replaced with a vertex to arrive at the other minimum dominating set. One can think of adjacency between minimum dominating sets in the gamma-graph as a swap of two vertices between minimum dominating sets. In the single vertex replacement adjacency model these two vertices can be any vertices in the minimum dominating sets, and in the slide adjacency model these two vertices must be adjacent in G. (Hence the gamma-graph obtained from the slide adjacency model is a subgraph of the gamma-graph obtained in the single vertex replacement adjacency model.) Results for both adjacency models are presented concerning the maximum degree, the diameter, and the order of the gamma-graph when G is a tree. / Graduate / 0405 / michaedwards@gmail.com