路和圈、圈和圈的Kronecker积图的超点连通性

摘要

如果图G的每一个最小点割都是某个点的邻点集,那么G是超点连通的,或者简称为是super-κ的.图G₁与G₂的Kronecker积图是一个点集为V （G₁×G₂）=V （G₁）×V （G₂）,边集为E（G₁×G₂）={（u₁,v₁）(u₂,v₂):u₁u₂∈E（G₁）, v₁v₂∈E（G₂）}的图.本文证明了对整数m≥4和奇数n≥3, Pm×Cn是超点连通的;对整数m≥5和奇数n≥3, C_m×C_n是超点连通的.

关键词

Kronecker积 / 点连通度 / 极大点连通性 / 超点连通性