可推出3-NZF的平方图

The Square of Graphs Which Can Admit 3-NZF

已知G2=G∪{uv dG(u,v)=2,u,v∈V(G)},如果定义算法,1)令G2=G0,2)Gk=Gk-1\{uv},dG(u,v)=2,这样就可以得到边数更少的图G。考虑G2推出3-NZF但∈τ1,3且|V(G)|+|E(G)|的极小反例,以及Gτ1,3但G2不推出3-NZF且满足1.|E(G)|-|V(G)|尽可能小,2.在1)成立的条件下,|E(G)|尽可能小的反例,于是有结论:G2推出3-NZF,当且仅当Gτ1,3。

It is shown that G^2=G∪{uv｜dG（u,v）=2,u,v∈V（G）}.If we define the algo rithm ： （ 1 ） suppose G^2=G0,2）Gk=Gk-1／{uv},dG（u,v）=2,thus we can obtain a graph G whose edges is less than G^2. Considering the least counter-example G which belongs to τ1,3,but G^2 admits 3-NZF, and ｜V（ G）｜ ＋ ｜E （G） ｜ is as small as possible, on the contrary, considering the counter-example that G2 doesn＇t admit 3-NZF, bu t G doesn＇t belongs to τ1,3 satis[ying （1） ｜ E （ G ）｜- ｜V（G）｜ is as small as possible,（2） on the basis of （ 1 ）, ｜ E （ G ）｜I is as small as possible, then we make conclusions：G^2 admits 3 - NZF,if and only if G￠τ1,3.