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 Wk(G) has
vertex set identical with the set of
admissible walks of length k in G. Two vertices are
adjacent in Wk(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 Wk(G) is connected
and we find bounds for the diameter of Wk(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