C_m□C_n的支撑树的一些性质(英文)

Some Properties on Spanning Trees of C_m□C_n

积图G1□G2是一个以笛卡儿积V(G1)×V(Gt)作为其点集．其中点(u,v)点(x,y)相邻当且仅当u=v且v与y在G2中相邻,或者v=y且u与z在G2相邻．证明了对图Cm□Cn的任意支撑树T,其中m和n不全为偶数,总存在一条Cm□CnT之外的边,添加到T上形成一个长度至少为m+n-1的圈．这解决了陈(Dis-creteMathemstics 287(2004)11-15)给出的一个公开问题．

The product G1□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 adjacent to 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）.