A note on bounds for the maximum traceable number of a graph

作者：Fujie Futaba^*

来源：Ars Combinatoria, 2014, 113: 353-359.

• traceable number of a graph
• maximum traceable number of a graph
• upper traceable number of a graph

For a connected graph G of order n >= 2 and a linear ordering S : upsilon(1), upsilon(2),..., upsilon(n) of V(G), d(s) = Sigma(n-1)(i=1) d(upsilon(i), upsilon(i)+1), where d(upsilon(i), upsilon(i)+1.) is the distance between upsilon(i) and upsilon(i+1). The traceable number t(G) and upper traceable number t(+) (G) of G are defined by t(G) = min{d(s)} and t(+) (G) = max{d(s)}, respectively, where the minimum and maximum are taken over all linear orderings s of V(G). The traceable number t(v) of a vertex v in G is defined by t(v) = min{d(s)}, where the minimum is taken over all linear orderings s of V(G) whose first term is upsilon. The maximum traceable number t*(G) of G is then defined by t* (G) = max{t(v) : v E V (G)}. Therefore, t(G) <= t* (G) <= (t)+(G) for every nontrivial connected graph G. We show that t*(G) <= [t(G)+t+(G)+1/2] for every nontrivial connected graph G and that this bound is sharp. Furthermore, it is shown that for positive integers a and b, there exists a nontrivial connected graph G with t(G) = a and t*(G) = b if and only if a <= b >= [3a/2].

• 出版日期2014-1