(k,k-1)-雙正則圖的平衡Judicious Partitions

Bollobás和Scott提出猜想:任意一個邊數(shù)為m且最小度大于1的圖存在頂點集的平衡二部劃分使得每一部分點集的導(dǎo)出子圖包含的邊數(shù)不超過m/3.Bollobds和Scott證明了絕大部分正則圖存在頂點集的平衡二部劃分使得每一部分點集的導(dǎo)出子圖包含的邊數(shù)比m/4小.這里討論(k,k-1)-雙正則圖的平衡二部劃分,證明了每一個(k,k-1).雙正則圖存在平衡二部劃分使得每一部分點集的導(dǎo)出子圖包含的邊數(shù)是m/4左右.

作 者： 顏娟 許寶剛 Yan Juan Xu Baogang   作者單位： 顏娟,Yan Juan(南京師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,江蘇 南京,210097;新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,新疆,烏魯木齊,830046)

許寶剛,Xu Baogang(南京師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,江蘇,南京,210097) 

刊 名： 南京師大學(xué)報(自然科學(xué)版)  ISTIC PKU 英文刊名： JOURNAL OF NANJING NORMAL UNIVERSITY(NATURAL SCIENCE EDITION)  年，卷(期)： 2008 31(3)  分類號： O157.5  關(guān)鍵詞： judicious partition   平衡二部劃分   (k   k-1)-雙正則圖   judicious partition   balanced bipartition   (k   k - 1) - biregular graph  

【(k,k-1)-雙正則圖的平衡Judicious Partitions】相關(guān)文章：

《成功》教案k04-25

命運的平衡04-27

學(xué)科術(shù)語 K05-04

K歌的真諦作文08-08

K歌大賽作文10-09

g、k、h教案04-28

平衡優(yōu)秀作文03-03

關(guān)于平衡的說說11-09

平衡優(yōu)秀作文03-03

關(guān)于平衡的作文08-30