度序列已给定的部分标定图的重构问题

设G=(V,E)是简单、无向的p阶部分标定图,V={v_1…,v_p},p≥3。设u,v∈V,X,Y(?)V。记N_Y(v)为顶点v在Y中的邻集,d_Y(v)=|N_Y(v)|为v关于Y的度,为v关于Y的邻接向量,它的第i个分量为0(或1),对应于v与y的第i个顶点不邻接(或邻接)。若d_Y(u)=d_Y(v),称u,v,关于Y等度;若u,v(?)Y,且u(Y)=v(Y),称u,v,关于Y