On upper traceable numbers of graphs

Okamoto, Futaba, and Zhang, Ping. "On upper traceable numbers of graphs." Mathematica Bohemica 133.4 (2008): 389-405. <http://eudml.org/doc/250526>.

@article{Okamoto2008,
abstract = {For a connected graph $G$ of order $n\ge 2$ and a linear ordering $s\colon v_1,v_2,\ldots ,v_n$ of vertices of $G$, $d(s)= \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^+(G)$ of $G$ is $t^+(G)= \max \lbrace d(s)\rbrace $, 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^+(T)\le \lfloor \{n^2/2\}\rfloor -1$ and $t^+(T)\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^+(T)= 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 graph $G$ of order $n\ge 3$, it is known that $n-1\le t^+(G)\le \lfloor \{n^2/2\}\rfloor -1$. We investigate the problem of determining possible pairs $n,k$ of positive integers that are realizable as the order and upper traceable number of some connected graph.},
author = {Okamoto, Futaba, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {traceable graph; traceable number; upper traceable number; traceable graph; traceable number; upper traceable number},
language = {eng},
number = {4},
pages = {389-405},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On upper traceable numbers of graphs},
url = {http://eudml.org/doc/250526},
volume = {133},
year = {2008},
}

TY - JOUR
AU - Okamoto, Futaba
AU - Zhang, Ping
TI - On upper traceable numbers of graphs
JO - Mathematica Bohemica
PY - 2008
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 133
IS - 4
SP - 389
EP - 405
AB - For a connected graph $G$ of order $n\ge 2$ and a linear ordering $s\colon v_1,v_2,\ldots ,v_n$ of vertices of $G$, $d(s)= \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^+(G)$ of $G$ is $t^+(G)= \max \lbrace d(s)\rbrace $, 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^+(T)\le \lfloor {n^2/2}\rfloor -1$ and $t^+(T)\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^+(T)= 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 graph $G$ of order $n\ge 3$, it is known that $n-1\le t^+(G)\le \lfloor {n^2/2}\rfloor -1$. We investigate the problem of determining possible pairs $n,k$ of positive integers that are realizable as the order and upper traceable number of some connected graph.
LA - eng
KW - traceable graph; traceable number; upper traceable number; traceable graph; traceable number; upper traceable number
UR - http://eudml.org/doc/250526
ER -