The upper traceable number of a graph |
| |
| Authors: | Futaba Okamoto Ping Zhang Varaporn Saenpholphat |
| |
| Institution: | (1) Mathematics Department, University of Wisconsin-La Crosse, La Crosse, WI 54601, USA;(2) Department of Mathematics, Srinakharinwirot University, Sukhumvit Soi 23, Bangkok, 10110, Thailand;(3) Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA |
| |
| Abstract: | For a nontrivial connected graph G of order n and a linear ordering s: v
1, v
2, …, v
n
of vertices of G, define  . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t
+(G) of G is t
+(G) = max{d(s)}, 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.
Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand
under the grant number MRG 5080075. |
| |
| Keywords: | traceable number upper traceable number Hamiltonian number |
| 本文献已被 SpringerLink 等数据库收录！ |
|
