The upper traceable number of a graph

Futaba Okamoto; Ping Zhang; Varaporn Saenpholphat

Czechoslovak Mathematical Journal (2008)

  • Volume: 58, Issue: 1, page 271-287
  • ISSN: 0011-4642

Abstract

top
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 d ( s ) = ∑ i = 1 n - 1 d ( v i , v i + 1 ) . 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.

How to cite

top

Okamoto, Futaba, Zhang, Ping, and Saenpholphat, Varaporn. "The upper traceable number of a graph." Czechoslovak Mathematical Journal 58.1 (2008): 271-287. <http://eudml.org/doc/31210>.

@article{Okamoto2008,
abstract = {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.},
author = {Okamoto, Futaba, Zhang, Ping, Saenpholphat, Varaporn},
journal = {Czechoslovak Mathematical Journal},
keywords = {traceable number; upper traceable number; Hamiltonian number; traceable number; upper traceable number; Hamiltonian number},
language = {eng},
number = {1},
pages = {271-287},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The upper traceable number of a graph},
url = {http://eudml.org/doc/31210},
volume = {58},
year = {2008},
}

TY - JOUR
AU - Okamoto, Futaba
AU - Zhang, Ping
AU - Saenpholphat, Varaporn
TI - The upper traceable number of a graph
JO - Czechoslovak Mathematical Journal
PY - 2008
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 58
IS - 1
SP - 271
EP - 287
AB - 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.
LA - eng
KW - traceable number; upper traceable number; Hamiltonian number; traceable number; upper traceable number; Hamiltonian number
UR - http://eudml.org/doc/31210
ER -

References

top
  1. 10.1002/jgt.3190040310, J. Graph Theory 4 (1980), 315–336. (1980) MR0584677DOI10.1002/jgt.3190040310
  2. 10.1016/0166-218X(83)90042-2, Discrete Appl. Math. 5 (1983), 211–222. (1983) MR0683513DOI10.1016/0166-218X(83)90042-2
  3. On Hamiltonian walks, Congr. Numer. 15 (1976), 41–51. (1976) Zbl0329.05113MR0398891
  4. On the Hamiltonian number of a graph, Congr. Numer. 165 (2003), 51–64. (2003) MR2049121
  5. A new look at Hamiltonian walks, Bull. Inst. Combin. Appl. 42 (2004), 37–52. (2004) MR2082480
  6. Introduction to Graph Theory, McGraw-Hill, Boston, 2005. (2005) 
  7. On Hamiltonian walks in graphs, Congr. Numer. (1973), 335–342. (1973) MR0357223
  8. 10.1137/0203017, SIAM J. Comput. 3 (1974), 214–221. (1974) MR0432492DOI10.1137/0203017
  9. A generalization of Hamiltonian cycles for trees, Czech. Math. J. 26 (1976), 596–603. (1976) MR0543670
  10. Measures of traceability in graphs, Math. Bohem. 131 (2006), 63–83. (2006) MR2211004
  11. Graphs with prescribed order and Hamiltonian number, Congr. Numer. 175 (2005), 161–173. (2005) MR2198624
  12. On open Hamiltonian walks in graphs, Arch Math. (Brno) 27A (1991), 105–111. (1991) Zbl0758.05067MR1189647

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.