1 - 2 of 2
Number of results to display per page
Search Results
2. The upper traceable number of a graph
- Creator:
- Okamoto, Futaba, Zhang, Ping, and Saenpholphat, Varaporn
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- traceable number, upper traceable number, and Hamiltonian number
- Language:
- English
- Description:
- For a nontrivial connected graph $G$ of order $n$ and a linear ordering $s\: v_1, v_2, \ldots , v_n$ of vertices of $G$, define $d(s) = \sum _{i=1}^{n-1} d(v_i, v_{i+1})$. The traceable number $t(G)$ of a graph $G$ is $t(G) = \min \lbrace d(s)\rbrace $ and the upper traceable number $t^+(G)$ of $G$ is $t^+(G) = \max \lbrace d(s)\rbrace ,$ where the minimum and maximum are taken over all linear orderings $s$ of vertices of $G$. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs $G$ for which $t^+(G)- t(G) = 1$ are characterized and a formula for the upper traceable number of a tree is established.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public