Displaying similar documents to “The upper traceable number of a graph”

Measures of traceability in graphs

Varaporn Saenpholphat, Futaba Okamoto, Ping Zhang (2006)

Mathematica Bohemica

Similarity:

For a connected graph G of order n 3 and an ordering s v 1 , v 2 , , v n of the vertices of G , d ( s ) = 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 ( G ) of G is defined by t ( G ) = min d ( s ) , where the minimum is taken over all sequences s of the elements of V ( G ) . 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 2 n - 2 - p t ( G ) 2 n - 2 - l and both these bounds are sharp. We establish a formula for the traceable...

On upper traceable numbers of graphs

Futaba Okamoto, Ping Zhang (2008)

Mathematica Bohemica

Similarity:

For a connected graph G of order n 2 and a linear ordering s : v 1 , v 2 , ... , v n of vertices of G , d ( s ) = 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 + ( G ) of G is t + ( G ) = max { d ( s ) } , 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 3 , then 2 n - 3 t + ( T ) n 2 / 2 - 1 and t + ( T ) n 2 / 2 - 3 if T P n . All pairs n , k for which there exists a tree T of order n and t + ( T ) = k are determined and a characterization of all those trees of order n 4 with upper traceable number n 2 / 2 - 3 is established. For a connected...

Minimum degree, leaf number and traceability

Simon Mukwembi (2013)

Czechoslovak Mathematical Journal

Similarity:

Let G be a finite connected graph with minimum degree δ . The leaf number L ( G ) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G . We prove that if δ 1 2 ( L ( G ) + 1 ) , then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if δ 1 2 ( L ( 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....