Originators: Kenta Ozeki (presented by Kenta Ozeki - REGS 2012)
Definitions: In this problem, a $k$-tree is a tree with maximum degree at most $k$, and a $k$-walk is a closed walk in which each vertex is visited at most $k$ times (these terms have other meanings in other contexts). The $k$-prism over a graph $G$ is the Cartesian product $G\Box K_k$, where $K_k$ is the complete graph with $k$ vertices. A graph $G$ is $k$-prism-hamiltonian if the $k$-prism over $G$ is Hamiltonian. Let $\alpha(G)$ denote the maximum size of an independent set of vertices in $G$. Given $\alpha(G)\ge k$, let $\sigma_k(G)$ be the minimum sum of the degrees of $k$ independent vertices in $G$.
Background: Note that a spanning $2$-tree is a Hamiltonian path, while a spanning $1$-walk is a Hamiltonian cycle. For general $k$, the concepts are related. Every graph having a spanning $k$-tree is $k$-prism-hamiltonian ([KRKRV] for $k =2$ and Čada-Flandrin-Li [CFL] for $k \geq 3$). Trivially (by projection), every graph that is $k$-prism-hamiltonian has a spanning $k$-walk. Finally, every graph having a spanning $k$-walk has a spanning $(k+1)$-tree (follow the walk, omitting edges that would complete cycles).
These concepts have been studied for a long time. Let $G$ be an $n$-vertex graph. For a spanning $k$-tree, it is sufficient that $\sigma_k(G)\ge n-1$ (Ore [O1] for $k=2$, Win [W] for $k>2$). Another sufficient condition is $\alpha(G)\le(k-1)m+1$ when $G$ is $m$-connected (Chvátal-Erdős [CE] for $k=2$, Neumann-Lara and Rivera-Campo [NR] for $k>2$).
For the existence of a spanning $k$-walk, analogous conditions are sufficient. It is sufficient that $\sigma_{k+1}(G)\ge n$ (Ore [O1] for $k=1$ and Jackson-Wormald [JW] for $k>1$). Another sufficient condition is $\alpha(G)\le km$ when $G$ is $m$-connected (Chvátal-Erdős [CE] for $k=1$ and Jackson-Wormald [JW] for $k>1$). Ozeki [O2,O3] showed that the same conditions suffice for the stronger condition of being $k$-prism-hamiltonian ([O2] for $k=2$ and [O3] for $k>2$), with one exception:
Problem 1: Is it true that $G$ must be $2$-prism-Hamiltonian when $\alpha(G)\le 2\kappa(G)$?
Comments: The inequalities in these conditions are sharp. The complete bipartite graph $K_{t,kt+1}$ has no spanning $k$-walk and is not $k$-prism-Hamiltonian. Also, $K_{t,kt+2}$ has no spanning $(k+1)$-tree. Given the sharpness examples and the form of the conditions, it seems that spanning $(k+1)$-trees are more closely related than spanning $k$-trees to the existence of spanning $k$-walks and the property of being $k$-prism-hamiltonian.
Another property is closely related to being $k$-prism-hamiltonian. A $k$-cycle-cover of a graph $G$ is a set of at most $k$ cycles or edges in $G$ that together cover the vertices of $G$. Recently, Ozeki [O3] showed for $k\geq 3$ that every connected graph having a $k$-cycle-cover is $k$-prism-hamiltonian. The proof involves another concept. A cactus is a connected graph in which every edge appears in at most one cycle. A $k$-cactus is a cactus in which the degree of every vertex is at most $k$ plus the number of cycles containing it. A $k$-hairy cycle is a unicyclic $k$-cactus. Ozeki [O3] proved for $k\ge2$ that every connected graph having a $k$-cycle-cover has a spanning $k$-hairy cycle. He also proved for $k\ge3$ that every graph containing a spanning $k$-cactus is $k$-prism-Hamiltonian.
The existence of $k$-cycle-covers is also related to the properties above. The condition $\sigma_{k+1}(G)\ge n$ is sufficient for a $k$-cycle-cover ([KL]), as is $\alpha(G)\le k\kappa(G)$ ([K]). However, the existence of a $2$-cycle-cover does not make $G$ $2$-prism-hamiltonian. For example, the graph obtained from $K_5$ by subdividing each edge twice (replacing each edge by a path of length $3$) has a $2$-cycle-cover, but it has no spanning even cactus (a $2$-cactus in which each cycle has even length and no cycles share vertices) and is not $2$-prism-hamiltonian.
In light of these sufficient conditions, the four properties ``having a $k$-cycle-cover'', ``being $k$-prism-hamiltonian'', ``having a spanning $k$-walk'' and ``having a spanning $(k+1)$-tree'' can be viewed as being similar.
Question 2: For $k\ge2$, given a sufficient condition for having a spanning $(k+1)$-tree, is there a similar sufficient condition for having a spanning $k$-walk? Are there also similar sufficient conditions for ``being $k$-prism-hamiltonian'' or ``having a $k$-cycle-cover''?
Comments: Several interesting questions about the special case of $2$-prism-Hamiltonicity were given in this problem. We can consider variations of these questions for the properties above. For example, the following is a variation of the question there by Rosenfeld concerning prism-hamiltonicity of regular graphs.
Problem 3: Given $k$ and $r$, for each property specified, what is the largest value of $n$ such that every 2-connected $r$-regular $n$-vertex graph has the property, where the property is that of having a $k$-cycle-cover, a spanning $k$-walk, a spanning $(k+1)$-tree, or being $k$-prism-hamiltonian?
Comments: Some researchers have considered the existence of a spanning $k$-walk and a spanning $(k+1)$-tree in graphs with lower bounds on edge-connectivity and upper bounds on maximum degree; these conditions spread edges apart. For example, for $k \geq 2$, every $2$-edge-connected graph with maximum degree at most $2k-1$ has a spanning $k$-walk [KKLW], and every $2$-edge-connected graph with maximum degree at most $2k$ has a spanning $(k+1)$-tree [LX]. Both of these bounds on the maximum degree are best possible.
Question 4: For $k\ge2$, consider $2$-edge-connected graphs. Does maximum degree at most $2k-1$ imply that such a graph is $k$-prism-hamiltonian or has a $k$-cycle-cover?
Comments: It is also known that every $m$-edge-connected graph with maximum degree at most $m(k-1)$ has a spanning $(k+1)$-tree ([ENV] and [LX] independently), but the bound ``$m(k-1)$'' does not seem best possible.
Question 5: For $m \geq 3$ and $k\ge2$, does every $m$-edge-connected graph with maximum degree at most $mk$ have a spanning $(k+1)$-tree? How about a spanning $k$-walk, a $k$-cycle-cover, or the property ``being $k$-prism-hamiltonian''?
Comments: There exist $m$-edge-connected graphs with maximum degree $mk+1$ having no spanning $(k+1)$-tree. Thus the bound ``$mk$'' would be best possible.
References:
[CFL] R. Čada, E. Flandrin and H. Li,
Hamiltonicity and pancyclicity of cartesian products of graphs,
Discrete Math. 309 (2009), 6337-6343.
[CE] V. Chvátal and P. Erdős,
A note on hamiltonian circuits,
Discrete Math. 2 (1972), 111-113.
[ENV] M.N. Ellingham, Y. Nam, and H.-J. Voss,
Connected $(g,f)$-factors,
J. Graph Theory 39 (2002), 62-75.
[EKKT] H. Enomoto, A. Kaneko, M. Kouider, and Zs. Tuza,
Degree sums and covering cycles,
J. Graph Theory 20 (1995), 419-422.
[JW] B. Jackson and N.C. Wormald,
$k$-walks of graphs,
Australas. J. Combin. 2 (1990), 135-146.
[KKLW] T. Kaiser, R. Kužel, H. Li, and G. Wang,
A note on $k$-walks in bridgeless graphs,
Graphs and Combin. 23 (2007), 303-308.
[KRKRV] T. Kaiser, Z. Ryjáček, D. Král, M. Rosenfeld,
and H.-J. Voss, Hamilton Cycles in Prisms,
J. Graph Theory 56 (2007), 249-269.
[K] M. Kouider
Cycles in graphs with prescribed stability number and connectivity,
J. Combin. Theory Ser. B 60 (1994), 315-318.
[KL] M. Kouider and Z. Lonc,
Covering cycles and $k$-term degree sums,
Combinatorica 16 (1996), 407-412.
[LX] Liu Zhenhong and Xu Baoguang,
On low bound of degree sequences of spanning trees in
$k$-edge-connected graphs
J. Graph Theory 28 (1998), 87-95.
[NR] V. Neumann-Lara and E. Rivera-Campo,
Spanning trees with bounded degrees,
Combinatorica 11 (1991) 55-61.
[O1] O. Ore,
Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), 55.
[O2] K. Ozeki,
A degree sum condition for graphs to be prism hamiltonian,
Discrete Math. 309 (2009), 4266-4269.
[O3] K. Ozeki,
A relationship among $k$-cycle covers, $k$-prism-hamiltonian, spanning
$k$-walks and spanning $(k+1)$-trees, in preparation.
[W] S. Win,
Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen
(German),
Abh. Math. Sem. Univ. Hamburg 43 (1975), 263-267.