Measures of traceability in graphs

Title:

Measures of traceability in graphs

Creator:

Saenpholphat, Varaporn and Okamoto, Futaba

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:4ca8c67f-cdfe-42e2-a1e7-e164bf5f79d2
uuid:4ca8c67f-cdfe-42e2-a1e7-e164bf5f79d2
doi:10.21136/MB.2006.134076

Subject:

traceable graph, Hamiltonian graph, and Hamiltonian-connected graph

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

For a connected graph G of order n > 3 and an ordering s : v1, v2, . . . , vn of the vertices of G, d(s) = n−1 ∑ i=1 d(vi , vi+1), where d(vi , vi+1) is the distance between vi and vi+1. The traceable number t(G) of G is defined by t(G) = min {d(s)} , where the minimum is taken over all sequences s of the elements of V (G). It is shown that if G is a nontrivial connected graph of order n such that l is the length of a longest path in G and p is the maximum size of a spanning linear forest in G, then 2n−2−p ≤ t(G) ≤ 2n−2−l and both these bounds are sharp. We establish a formula for the traceable number of every tree in terms of its order and diameter. It is shown that if G is a connected graph of order n ≥ 3, then t(G) ≤ 2n − 4. We present characterizations of connected graphs of order n having traceable number 2n − 4 or 2n − 5. The relationship between the traceable number and the Hamiltonian number (the minimum length of a closed spanning walk) of a connected graph is studied. The traceable number t(v) of a vertex v in a connected graph G is defined by t(v) = min{d(s)}, where the minimum is taken over all linear orderings s of the vertices of G whose first term is v. We establish a formula for the traceable number t(v) of a vertex v in a tree. The Hamiltonian-connected number hcon(G) of a connected graph G is defined by hcon(G) = ∑ v∈V (G) t(v). We establish sharp bounds for hcon(G) of a connected graph G in terms of its order.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

63-83

Source:

Mathematica bohemica | 2006 Volume:131 | Number:1

Harvested from:

CDK

Metadata only:

false