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

For a nontrivial connected graph $G$ of order $n$ and a linear ordering $s{v}_1,v_2,...,v_n$ of vertices of $G$, define $d\left(s\right)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})$. The traceable number $t\left(G\right)$ of a graph $G$ is $t\left(G\right)=min\left\{d\right(s\left)\right\}$ and the upper traceable number $t^{+}\left(G\right)$ of $G$ is $t^{+}\left(G\right)=max\left\{d\left(s\right)\right\},$ where the minimum and maximum are taken over all linear orderings $s$ of vertices of $G$. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs $G$ for which $t^{+}\left(G\right)-t\left(G\right)=1$ are characterized and a formula for...

Let C denote the claw $K_{1,3}$, N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and $Z_i$ the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free...

Let $G$ be a finite connected graph with minimum degree $\delta$. The leaf number $L\left(G\right)$ of $G$ is defined as the maximum number of leaf vertices contained in a spanning tree of $G$. We prove that if $\delta \ge \frac{1}{2}(L\left(G\right)+1)$, then $G$ is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if $\delta \ge \frac{1}{2}\left(L\right(G)+1)$, then $G$ contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin....