Abstract
dc:description.abstractA 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 δ(G), α'(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 δ(G) \geq α'(G), then each of the following holds. \\ (i) $L(G)$ is Hamilton-connected if and only if $\kappa(L(G))\ge 3$. \\ (ii) $L(G)$ is 1-hamiltonian if and only if $\kappa(L(G))\ge 3$. %==========sp For a graph $G$, an integer $s \ge 0$ and distinct vertices $u, v \in V(G)$, an $(s; u, v)$-path-system of $G$ is a subgraph $H$ consisting of $s$ internally disjoint $(u,v)$-paths. The spanning connectivity \kappa*(G) is the largest integer $s$ such that for any $k$ with $0 \le k \le s$ and for any $u, v \in V(G)$ with $u \neq v$, $G$ has a spanning $(k; u,v)$-path-system. It is known that \kappa*(G) \le \kappa(G), and determining if \kappa*(G) > 0 is an NP-complete problem. A graph $G$ is maximally spanning connected if \kappa*(G) = \kappa(G). Let $msc(G)$ and sk(G) be the smallest integers $m$ and $m'$ such that Lm(G) is maximally spanning connected and \kappa*(Lm'(G)) \ge k, respectively. We show that every locally-connected line graph with connectivity at least 3 is maximally spanning connected, and that the spanning connectivity of a locally-connected line graph can be polynomially determined. As applications, we also determined best possible upper bounds for $msc(G)$ and sk(G), and characterized the extremal graphs reaching the upper bounds. %==============st 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$. Pulleyblank in [J. Graph Theory, 3 (1979) 309-310] showed that determining whether a graph is $(0,0)$-supereulerian, even when restricted to planar graphs, is NP-complete. Settling an open problem of Bauer, Catlin in [J. Graph Theory, 12 (1988) 29-45] showed that every simple graph $G$ on $n$ vertices with δ(G) \ge \frac{n}{5} -1, when $n$ is sufficiently large, is $(0,0)$-supereulerian or is contractible to K2,3. We prove the following for any nonnegative integers $s$ and $t$. \\ (i) For any real numbers $a$ and $b$ with $0 < a < 1$, there exists a family of finitely many graphs $\F(a,b;s,t)$ such that if $G$ is a simple graph on $n$ vertices with $\kappa'(G) \ge t+2$ and δ(G) \ge an + b, then either $G$ is $(s,t)$-supereulerian, or $G$ is contractible to a member in $\F(a,b;s,t)$. \\ (ii) Let \ell K2 denote the connected loopless graph with two vertices and $\ell$ parallel edges. If $G$ is a simple graph on $n$ vertices with $\kappa'(G) \ge t+2$ and δ(G) \ge \frac{n}{2}-1, then when $n$ is sufficiently large, either $G$ is $(s,t)$-supereulerian, or for some integer $j$ with $t+2 \le j \le s+t$, $G$ is contractible to a j K2. %==================index For a hamiltonian property $\cp$, Clark and Wormold introduced the problem of investigating the value \cp(a,b) = \max\{\min\{n: Ln(G) has property $\cp$\}: $\kappa'(G) \ge a$ and δ(G) \ge b\}, and proposed a few problems to determine $\cp(a,b)$ with $b \ge a \ge 4$ when $\cp$ is being hamiltonian, edge-hamiltonian and hamiltonian-connected. Zhan in 1986 proved that the line graph of a 4-edge-connected graph is Hamilton-connected, which implies a solution to the unsettled cases of above-mentioned problem. We consider an extended version of the problem. Let $ess'(G)$ denote the essential edge-connectivity of a graph $G$, and define \cp'(a,b) = \max\{\min\{n: Ln(G) has property $\cp$\}: $ess'(G) \ge a$ and δ(G) \ge b\}. We investigate the values of $\cp'(a,b)$ when $\cp$ is one of these hamiltonian properties. In particular, we show that for any values of $b \ge 1$, $\cp'(4,b) \le 2$ and $\cp'(4,b) = 1$ if and only if Thomassen's conjecture that every 4-connected line graph is hamiltonian is valid.
Degree
thesis:*- Name thesis:degree_name
- PhD
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- xie, yikang
- Contributors dc:contributor
-
- Hong-Jian Lai
- John Goldwasser
- Rong Luo
- Jerzy Wojciechowski
- Guodong Guo
Subjects
dc:subject × 9Identifiers
dc:identifier.*- Identifier
-
<p><a href="https://orcid.org/0000-0003-1627-7218">https://orcid.org/0000-0003-1627-7218</a></p>
https://researchrepository.wvu.edu/etd/11976