دراسة طريقة تجزيء للبيان تحقق تخمين فيزنج

الملخص

ليكن G(V,E) بيان ، ولتكن D مجموعة جزئية من مجموعة رؤوس البيان G، يقال عن D إنها مجموعة سيطرة للبيان G إذا كان لأجل كل رأس 12x∈"> V إما 12x∈D"> ، أو x مجاور لرأس واحد على الأقل لـ D . ونسمي عدد عناصر أصغر مجموعة سيطرة للبيان G بعدد السيطرة ونرمز له بـ 12خ³G">  .

لقد خمن فيزنج في [7] إن المتراجحة 12خ³Gأ—H ≥ خ³Gأ—خ³H">  محققة من أجل أي بيانين
G و H، يعني أن عدد السيطرة للجداء الديكارتي لأي بيانين G×H أكبر أو يساوي حاصل جداء عدد السيطرة  للبيان  G بعدد السيطرة  للبيان  H . ومن الجدير بالذكر أن هذا التخمين ما يزال مفتوحاً حتى الآن.

تم في هذا العمل مناقشة وإثبات القضايا الآتية ، إذا كان للبيان H    –Dتجزئة  يكون له K-تجزئة، وإذا كان له K-تجزئة ، فإن تخمين فيزنج يتحقق من أجل أي بيان G، كما تم إثبات أن كل حلقة C_n، ،
تملك K-تجزئة.

أخيراً تم إثبات أنه إذا كان للبيان H K -تجزئة فإنه يحقق القضايا الآتية: 12 خ³H≤2"> ،

و  وأن البيان H يكون تام السيطرة.