摘要
积图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).
出处
《新疆大学学报(自然科学版)》
CAS
2006年第4期410-413,共4页
Journal of Xinjiang University(Natural Science Edition)
关键词
支撑树
圈
k-可配对图
积图
Spanning tree
Cycle
k-pairable graph
product graph