For a connected graph $G$ of order $n\ge 3$ and an ordering $s{v}_1$, $v_2,\cdots ,v_n$ of the 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 traceable number $t\left(G\right)$ of $G$ is defined by $t\left(G\right)=min\left\}d\left(s\right)\right\{,$ where the minimum is taken over all sequences $s$ of the elements of $V\left(G\right)$. It is shown that if $G$ is a nontrivial connected graph of order $n$ such that $l$ is the length of a longest path in $G$ and $p$ is the maximum size of a spanning linear forest in $G$, then $2n-2-p\le t\left(G\right)\le 2n-2-l$ and both these bounds are sharp. We establish a formula for the traceable number of...

Zero forcing number has recently become an interesting graph parameter studied in its own right since its introduction by the “AIM Minimum Rank–Special Graphs Work Group”, whereas metric dimension is a well-known graph parameter. We investigate the metric dimension and the zero forcing number of some line graphs by first determining the metric dimension and the zero forcing number of the line graphs of wheel graphs and the bouquet of circles. We prove that $Z\left(G\right)\le 2Z\left(L\right(G\left)\right)$ for a simple and connected graph $G$. Further,...

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. 15 (2008),...