16
$\begingroup$

My question is

Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must $G$ have the following substructures?
i) a leafless spanning tree;
ii) a spanning forest consisting of rays;
iii) a spanning forest consisting of double-rays.

A ray is a 1-way infinite (self-avoiding) path. A double-ray is a 2-way infinite path. A tree $T$ is leafless, if it has no vertex of degree 1 (a leaf). Equivalently, every edge of $T$ lies in a double-ray.

The following implications hold for every (infinite, connected, locally finite) graph G, vertex-transitive or not:

iii) trivially implies ii), by removing one edge from each double-ray.

iii) also implies i): given a spanning forest $F$ of double-rays, let $T$ be a minimal tree containing $F$, which can be constructed greedily by connecting the components of $F$ one by one, thereby never creating a leaf.

i) implies ii): pick a root $r$ of the leafless tree $T$, and a ray $R$ containing $r$. Delete all edges of $T$ incident with $R$ but not contained in it. Repeat in each resulting component, picking the vertex adjacent with $R$ as the root.

The other implications can fail for general $G$, but I don't know if they hold when $G$ is vertex-transitive.

Note that if $G$ is a Cayley-graph, and one of its generators has infinite order, then iii) holds. In 2009 I asked if every 1-ended, finitely generated, (connected) Cayley graph has a spanning double ray (Problem 3 in Infinite Hamilton cycles in squares of locally finite graphs), which is much stronger than iii) above, and still open as far as I know. It follows from the main result of the same paper that for every vertex-transitive $G$, the square $G^2$ satisfies iii). Here, $G^2$ is defined by adding an edge between each two vertices that are at distance 2 in $G$. In particular, every f.g. group has a f.g. Cayley graph satisfying iii) (and hence i) and ii)).

Improve this question
$\endgroup$
7
  • $\begingroup$ Conjecture (iii) says in other words: every infinite, connected, locally finite, vertex-transitive graph has an acyclic $2$-regular spanning subgraph. By the usual compactness argument, this is equivalent to the ostensibly weaker assertion: if $G$ is an infinite, connected, locally finite, vertex-transitive graph, then for each finite set $X\subset V(G)$ there is a subgraph $H_X$ of $G$ such that $X\subset V(H_X)$ and every vertex in $X$ has degree $2$ in $H_X$. $\endgroup$
    – bof
    Commented Feb 12, 2023 at 10:39
  • 2
    $\begingroup$ Conjecture (iii) implies that every infinite, connected, $3$-regular, vertex-transitive graph has edge chromatic number $3$. Is this true? $\endgroup$
    – bof
    Commented Feb 12, 2023 at 11:11
  • $\begingroup$ "Equivalently, every edge of š¯‘‡ lies in a double-ray." Doesn't this assume that T is infinite? $\endgroup$
    – Daniel Asimov
    Commented Feb 13, 2023 at 1:39
  • 1
    $\begingroup$ @DanielAsimov For an acyclic graph (in particular a tree), "every edge lies in a double ray" is equivalent to "no vertex has degree $1$". Why do you think it's necessary to assume that the graph is infinite? What finite counterexample do you have in mind? $\endgroup$
    – bof
    Commented Feb 13, 2023 at 2:10
  • 2
    $\begingroup$ Question i) appears as question 28 in this list from 2010: users.renyi.hu/~abert/questions.pdf, attributed there to Babai. $\endgroup$
    – Gabor Lippner
    Commented Feb 13, 2023 at 17:02

0

Reset to default

You must log in to answer this question.