A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $de{g}_{G}u+de{g}_{G}v\ge n-1$, G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $de{g}_{G}u+de{g}_{G}v$ and the structure of the distant area for u and v. We prove...

Let $\alpha \left(n\right)$ be the least number $k$ for which there exists a simple graph with $k$ vertices having precisely $n\ge 3$ spanning trees. Similarly, define $\beta \left(n\right)$ as the least number $k$ for which there exists a simple graph with $k$ edges having precisely $n\ge 3$ spanning trees. As an $n$-cycle has exactly $n$ spanning trees, it follows that $\alpha \left(n\right),\beta \left(n\right)\le n$. In this paper, we show that $\alpha \left(n\right)\le \frac{1}{3}(n+4)$ and $\beta \left(n\right)\le \frac{1}{3}(n+7)$ if and only if $n\notin \{3,4,5,6,7,9,10,13,18,22\}$, which is a subset of Euler’s idoneal numbers. Moreover, if $n\neg \equiv 2(mod3)$ and $n\ne 25$ we show that $\alpha \left(n\right)\le \frac{1}{4}(n+9)$ and $\beta \left(n\right)\le \frac{1}{4}(n+13).$ This improves some previously estabilished...

For an end $\tau$ and a tree $T$ of a graph $G$ we denote respectively by $m\left(\tau \right)$ and $m_T\left(\tau \right)$ the maximum numbers of pairwise disjoint rays of $G$ and $T$ belonging to $\tau$, and we define $\mathrm{t}m\left(\tau \right):=min\left\{m_T\left(\tau \right)T\text{is}\text{a}\text{spanning}\text{tree}\text{of}G\right\}$. In this paper we give partial answers—affirmative and negative ones—to the general problem of determining if, for a function $f$ mapping every end $\tau$ of $G$ to a cardinal $f\left(\tau \right)$ such that $\mathrm{t}m\left(\tau \right)\le f\left(\tau \right)\le m\left(\tau \right)$, there exists a spanning tree $T$ of $G$ such that $m_T\left(\tau \right)=f\left(\tau \right)$ for every end $\tau$ of $G$.

By a ternary system we mean an ordered pair $(W,R)$, where $W$ is a finite nonempty set and $R\subseteq W\times W\times W$. By a signpost system we mean a ternary system $(W,R)$ satisfying the following conditions for all $x,y,z\in W$: if $(x,y,z)\in R$, then $(y,x,x)\in R$ and $(y,x,z)\notin R$; if $x\ne y$, then there exists $t\in W$ such that $(x,t,y)\in R$. In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair $(G,T)$, where $G$ is a connected graph and $T$ is a spanning tree of $G$. If $(G,T)$ is a ct-pair, then by...

We examine decompositions of complete graphs with an even number of vertices, $K_{2n}$, into n isomorphic spanning trees. While methods of such decompositions into symmetric trees have been known, we develop here a more general method based on a new type of vertex labelling, called flexible q-labelling. This labelling is a generalization of labellings introduced by Rosa and Eldergill.

We examine constructions of non-symmetric trees with a flexible q-labeling or an α-like labeling, which allow factorization of $K_{2n}$ into spanning trees, arising from the trees with α-labelings.

For a connected graph $G$ of order $n\ge 2$ and a linear ordering $s:v_1,v_2,...,v_n$ of vertices of $G$, $d\left(s\right)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})$, where $d(v_i,v_{i+1})$ is the distance between $v_i$ and $v_{i+1}$. The upper traceable number $t^{+}\left(G\right)$ of $G$ is $t^{+}\left(G\right)=max\left\{d\left(s\right)\right\}$, where the maximum is taken over all linear orderings $s$ of vertices of $G$. It is known that if $T$ is a tree of order $n\ge 3$, then $2n-3\le t^{+}\left(T\right)\le \lfloor n^2/2\rfloor -1$ and $t^{+}\left(T\right)\le \lfloor n^2/2\rfloor -3$ if $T\ne P_n$. All pairs $n,k$ for which there exists a tree $T$ of order $n$ and $t^{+}\left(T\right)=k$ are determined and a characterization of all those trees of order $n\ge 4$ with upper traceable number $\lfloor n^2/2\rfloor -3$ is established. For a connected...