**
ACTA MATHEMATICA UNIVERSITATIS COMENIANAE **

Vol. LXXVI, 2 (2007)

p. 223 - 230

Diameter in Walk Graphs

T. Vetrik

**Abstract**.
A walk *W* of length *k* is admissible if
every two consecutive edges of *W*
are distinct. If *G* is a graph, then its walk graph *W*_{k}(*G*) has
vertex set identical with the set of
admissible walks of length *k* in *G*. Two vertices are
adjacent in *W*_{k}(*G*) if and only if one of the corresponding walks
can be obtained from the other by deleting an edge from one end
and adding an edge to the other end. We show that if the degree of
every vertex in *G* is more than one, then *W*_{k}(*G*) is connected
and we find bounds for the diameter of *W*_{k}(*G*).

**Keywords:**
diameter, walk graph.

**AMS Subject classification.** 05C12, 05C38.

**Download:**
Adobe PDF
Compressed Postscript

**Version to read:**
Adobe PDF

Acta Mathematica Universitatis Comenianae

Faculty of Mathematics, Physics and Informatics

Comenius University

842 48 Bratislava, Slovak Republic

Telephone: + 421-2-60295755 Fax: + 421-2-65425882

e-Mail: amuc@fmph.uniba.sk
Internet: www.iam.fmph.uniba.sk/amuc
©
Copyright 2006, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE