论文部分内容阅读
图的优美性是图的重要研究内容之一,有广泛的应用背景.1991年,马克杰提出猜想:完备二分图Km,n的冠I(Km,n)是k-优美图,其中m,n,k是任意正整数且m≤n.2010年,刘育兴证明了当m=2,3,4,5或k>(m-2)n时猜想成立.2011年,李武装,严谦泰证明了当m=1或m=2,k≥2或m≥3,k≥(m-2)(n-1)的三种情况时猜想均成立.本文在第三章中证明了对于任意正整数m,n,k,m<n,m≥6,n≥m2-3m+2/2的情形时猜想也成立。
完备二分图Km,n的r-冠Ir(Km,n)的k-优美性的证明难度较大.包玉兰、吉日木图、斯琴其木格等人分别证明了当m=1;m=2,3;m=4,其中m≤n,r≥2时完备二分图Km,n的r-冠Ir(Km,n)是k-优美的.在本文的第四章中,我们利用构造的方法证明了当n≥5,r≥2时,完备二分图K5,n的r-冠Ir(K5,n)是k-优美图.