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

A planar Eulerian triangulation is a simple plane graph in which each face is a triangle and each vertex has even degree. Such objects are known to be equivalent to spherical Latin bitrades. (A Latin bitrade describes the difference between two Latin squares of the same order.) We give a classification in the near-regular case when each vertex is of degree $4$ or $6$ (which we call a near-homogeneous spherical Latin bitrade, or NHSLB). The classification demonstrates that any NHSLB is equal to two graphs...

For a graph G of order n we consider the unique partition of its vertex set V(G) = A ∪ B with A = {v ∈ V(G): d(v) ≥ n/2} and B = {v ∈ V(G):d(v) < n/2}. Imposing conditions on the vertices of the set B we obtain new sufficient conditions for hamiltonian and pancyclic graphs.

In this note we show that deciding the existence of a Hamiltonian cycle in a cubic plane graph is equivalent to the problem of the existence of an associated cubic plane multi-3-gonal graph with a Hamiltonian cycle which takes alternately left and right edges at each successive vertex, i.ei̇t is also a Petrie cycle. The Petrie Hamiltonian cycle in an $n$-vertex plane cubic graph can be recognized by an $O\left(n\right)$-algorithm.

A digraph D = (V,A) is arc-traceable if for each arc xy in A, xy lies on a directed path containing all the vertices of V, i.e., hamiltonian path. We prove a conjecture of Quintas [7]: if D is arc-traceable, then the condensation of D is a directed path. We show that the converse of this conjecture is false by providing an example of an upset tournament which is not arc-traceable. We then give a characterization for upset tournaments in terms of their score sequences, characterize which arcs of...

We consider cubic graphs formed with k ≥ 2 disjoint claws $C_i{K}_{1,3}$ (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of $C_i$ are joined to the three vertices of degree 1 of $C_{i-1}$ and joined to the three vertices of degree 1 of $C_{i+1}$. Denote by $t_i$ the vertex of degree 3 of $C_i$ and by T the set $t₁,t₂,...,t_{k-1}$. In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices ${\bigcup }_{i=0}^{i=k-1}V\left(C_i\right)\setminus T$ induce j cycles (note that the graphs...

In this paper the following theorem is proved: Let $G$ be a connected graph of order $p\ge 4$ and let $M$ be a matching in $G$. Then there exists a hamiltonian cycle $C$ of $G^4$ such that $E\left(C\right)\bigcap M=0$.