一类(0,1)-多面体

A Type of (0,1)-Polyhedra

本文证明m×n阶(0,1)-矩阵类(R,S)的变换图,当min{m,n}=2时为某一(0,1)-多面体P的图(或骨架)C(P),进而证明其为Hamilton连通及边泛圈的(除两个例外)。同时指出min{m,n}>2时(R,S)的变换图一般不是一个(0,1)-多面体的图。

The class of matrices (R,S) was difined to be. the m×n matrices of zeros and ones with fixed row and column sum vectors. R A Brualdi introduced the concept of interchange graphs of these classes of matrice. We show that when m=2 (or n=2) (R,S) is isomorphic to a graph of (0,1)polyhedra which was introduced by D J Naddef and W R Potleyblank. However, when m>2 and n>1 this fact is not true in the general. Furthermore when n=2 ( orm=2) the interchange graph of (R,S) is Hamilton connected and edge Pancyclic except a few special cases.