Discrete Mathematics and Combinatorics Commons^™

On Eulerian Subgraphs And Hamiltonian Line Graphs, Yikang Xie

Graduate Theses, Dissertations, and Problem Reports

A graph {\color{black}$G$} is Hamilton-connected if for any pair of distinct vertices {\color{black}$u, v \in V(G)$}, {\color{black}$G$} has a spanning $(u,v)$-path; {\color{black}$G$} is 1-hamiltonian if for any vertex subset $S \subseteq {\color{black}V(G)}$ with $|S| \le 1$, $G - S$ has a spanning cycle. Let $\delta(G)$, $\alpha'(G)$ and $L(G)$ denote the minimum degree, the matching number and the line graph of a graph $G$, respectively. The following result is obtained. {\color{black} Let $G$ be a simple graph} with $|E(G)| \ge 3$. If $\delta(G) \geq \alpha'(G)$, then each of the following holds. \\ (i) $L(G)$ is Hamilton-connected if and only if $\kappa(L(G))\ge …

Finite Matroidal Spaces And Matrological Spaces, Ziyad M. Hamad

Graduate Theses, Dissertations, and Problem Reports

The purpose of this thesis is to present new different spaces as attempts to generalize the concept of topological vector spaces. A topological vector space, a well-known concept in mathematics, is a vector space over a field \mathbb{F} with a topology that makes the addition and scalar multiplication operations of the vector space continuous functions. The field \mathbb{F} is usually \mathbb{R} or \mathbb{C} with their standard topologies. Since every vector space is a finitary matroid, we define two spaces called finite matroidal spaces and matrological spaces by replacing the linear structure of the topological vector space with a finitary matroidal …

On Generalizations Of Supereulerian Graphs, Sulin Song

Graduate Theses, Dissertations, and Problem Reports

A graph is supereulerian if it has a spanning closed trail. Pulleyblank in 1979 showed that determining whether a graph is supereulerian, even when restricted to planar graphs, is NP-complete. Let $\kappa'(G)$ and $\delta(G)$ be the edge-connectivity and the minimum degree of a graph $G$, respectively. For integers $s \ge 0$ and $t \ge 0$, a graph $G$ is $(s,t)$-supereulerian if for any disjoint edge sets $X, Y \subseteq E(G)$ with $|X|\le s$ and $|Y|\le t$, $G$ has a spanning closed trail that contains $X$ and avoids $Y$. This dissertation is devoted to providing some results on $(s,t)$-supereulerian graphs and …

Polychromatic Colorings Of Certain Subgraphs Of Complete Graphs And Maximum Densities Of Substructures Of A Hypercube, Ryan Tyler Hansen

Graduate Theses, Dissertations, and Problem Reports

If G is a graph and H is a set of subgraphs of G, an edge-coloring of G is H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, poly_HG, is the largest number of colors in an H-polychromatic coloring. We determine poly_HG exactly when G is a complete graph on n vertices, q a fixed nonnegative integer, and H is the family of one of: all matchings spanning n-q vertices, all 2-regular graphs spanning at least n-q vertices, or all cycles of length precisely n-q. …

Algebraic, Analytic, And Combinatorial Properties Of Power Product Expansions In Two Independent Variables., Mohamed Ammar Elewoday

Graduate Theses, Dissertations, and Problem Reports

Let $F(x,y)=I+\hspace{-.3cm}\sum\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}A_{m,n}x^my^n$ be a formal power series, where the coefficients $A_{m,n}$ are either all matrices or all scalars. We expand $F(x,y)$ into the formal products $\prod\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}(I+G_{m,n}x^m y^n)$, $\prod\limits_{\substack{p=1\\m+n=p}}^{\infty}\hspace{-.3cm}(I-H_{m,n}x^m y^n)^{-1}$, namely the \textit{ power product expansion in two independent variables} and \textit{inverse power product expansion in two independent variables} respectively. By developing new machinery involving the majorizing infinite product, we provide estimates on the domain of absolute convergence of the infinite product via the Taylor series coefficients of $F(x,y)$. This machinery introduces a myriad of "mixed expansions", uncovers various algebraic connections between the $(A_{m,n})$ and the $(G_{m,n})$, and uncovers various algebraic …

Heterogeneous Generalizations Of Vertex Coloring, Lucian Ciletti Mazza

Graduate Theses, Dissertations, and Problem Reports

This dissertation proves a collection of results in some heterogeneous generalizations of vertex coloring, i.e. generalizations in which the relationship between the colors of two adjacent vertices may differ throughout the graph. For the most part, the results are from group coloring, group list coloring, and DP coloring. The main results are as follows: a group list coloring analogue of Brooks' Theorem for multigraphs, a result linking group structure (rather than only group size) with group coloring, some results involving coloring edge-disjoint unions, and an examination of the relationship between the group and DP coloring numbers of a multigraph and …

Cycle Double Covers And Integer Flows, Zhang Zhang

Graduate Theses, Dissertations, and Problem Reports

My research focuses on two famous problems in graph theory, namely the cycle double cover conjecture and the integer flows conjectures. This kind of problem is undoubtedly one of the major catalysts in the tremendous development of graph theory. It was observed by Tutte that the Four color problem can be formulated in terms of integer flows, as well as cycle covers. Since then, the topics of integer flows and cycle covers have always been in the main line of graph theory research. This dissertation provides several partial results on these two classes of problems.

Weighted Modulo Orientations Of Graphs, Jianbing Liu

Graduate Theses, Dissertations, and Problem Reports

This dissertation focuses on the subject of nowhere-zero flow problems on graphs. Tutte's 5-Flow Conjecture (1954) states that every bridgeless graph admits a nowhere-zero 5-flow, and Tutte's 3-Flow Conjecture (1972) states that every 4-edge-connected graph admits a nowhere-zero 3-flow. Extending Tutte's flows conjectures, Jaeger's Circular Flow Conjecture (1981) says every 4k-edge-connected graph admits a modulo (2k+1)-orientation, that is, an orientation such that the indegree is congruent to outdegree modulo (2k+1) at every vertex. Note that the k=1 case of Circular Flow Conjecture coincides with the 3-Flow Conjecture, and the case of k=2 implies the 5-Flow Conjecture. This work is devoted …

Circuits And Cycles In Graphs And Matroids, Yang Wu

Graduate Theses, Dissertations, and Problem Reports

This dissertation mainly focuses on characterizing cycles and circuits in graphs, line graphs and matroids. We obtain the following advances.

1. Results in graphs and line graphs. For a connected graph G not isomorphic to a path, a cycle or a K1,3, let pc(G) denote the smallest integer n such that the nth iterated line graph Ln(G) is panconnected. A path P is a divalent path of G if the internal vertices of P are of degree 2 in G. If every edge of P is a cut edge of G, then P is a bridge divalent path of G; …

Edge Colorings Of Graphs On Surfaces And Star Edge Colorings Of Sparse Graphs, Katherine M. Horacek

Graduate Theses, Dissertations, and Problem Reports

In my dissertation, I present results on two types of edge coloring problems for graphs.

For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. For a surface Σ with characteristic χ(Σ) ≤ 0, it is known ∆(Σ) ≥ H(χ(Σ))−1, where H(χ(Σ)) is the Heawood number of the surface, and if the Euler char- acteristic χ(Σ) ∈ {−7, −6, . . . , −1, 0}, ∆(Σ) is already …

Infinite Matroids And Transfinite Sequences, Martin Andrew Storm

Graduate Theses, Dissertations, and Problem Reports

A matroid is a pair M = (E,I) where E is a set and I is a set of subsets of E that are called independent, echoing the notion of linear independence. One of the leading open problems in infinite matroid theory is the Matroid Intersection Conjecture by Nash-Williams which is a generalization of Hall’s Theorem. In [31] Jerzy Wojciechowski introduced µ- admissibility for pairs of matroids on the same ground set and showed that it is a necessary condition for the existence of a matching. A pair of matroids (M,W) with common ground set E is µ-admissible if a …