The product Gi□G2 is the graph with the cartesian product V(G1)×V(G2) as its vertex set
in which the vertex (u
v) is adjacent to (x
y) if and only if either u = x and v is adjacentto y in G2 or v = y and u is adjacent to x in G1. We show that for every spanning tree T of graph Cm□Cn with m and n not both even
there exists an edge of graph Cm□Cn outside T whose addition to T forms a cycle of length at least m+n-1 . This solves an open problem posed by Chen(Discrete Mathematics 287(2004) 11-15).
关键词
Keywords
references
BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York:Elsevier Science Publishing, 1976.
CHEN ZHI-bo. On k -pairable graphs [J]. Discret Mathematics,2004, 287:11-15.
IMRICH W, KLAVZAR S. Product graphs, Structure and recognition[M]. New York: Wiley, 2000.