A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $c{n}^{3/4}$ (at most n).

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...

For two vertices $u$ and $v$ of a graph $G$, the closed interval $I[u,v]$ consists of $u$, $v$, and all vertices lying in some $u\text{--}v$ geodesic of $G$, while for $S\subseteq V\left(G\right)$, the set $I\left[S\right]$ is the union of all sets $I[u,v]$ for $u,v\in S$. A set $S$ of vertices of $G$ for which $I\left[S\right]=V\left(G\right)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g\left(G\right)$. A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in $G$ is its extreme order $\mathrm{e}x\left(G\right)$. A graph $G$ is an...

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...

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...

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...