Imperfect Graph

An imperfect graph  is a graph that is not perfect. Therefore, graphs  with

(1)

where  is the clique number and  is the chromatic number are imperfect. A weaker form using a bound of  states that a graph with

(2)

where  is the independence number is imperfect.

By the perfect graph theorem, applying the above to the graph complement gives that a graph  with

(3)

where  is the clique covering number is also imperfect.

A graph is also imperfect iff either the graph or its complement has a chordless cycle of odd order.

Families of imperfect graphs include:

1. cycle graphs 

2. fullerenes (which by definition contain an odd 5-cycle)

3. king graphs  with 

4. helm graphs  for odd 

5. wheel graphs 

A list of imperfect graphs on small numbers of vertices is implemented in the Wolfram Language as GraphData["Imperfect"].

The numbers of simple imperfect graphs on , 2, ... vertices are 0, 0, 0, 0, 1, 8, 138, 3459, ... (OEIS A187236).

The numbers of connected imperfect graphs on , 2, ... vertices are 0, 0, 0, 0, 1, 7, 129, 3312,... (OEIS A187237).

---

REFERENCES

Godsil, C. and Royle, G. "Imperfect Graphs." §7.6 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 142-145, 2001.

Sloane, N. J. A. Sequences A187236 and A187237 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "Imperfect Graphs." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 334-340, 2000.

اخر الاخبار

اخبار العتبة العباسية المقدسة

العتبة العباسية المقدسة تعلن أسماء الفائزين بمسابقة الذكرى الميمونة لولادة الإمام الحسين (عليه السلام)

شعبة الخطابة النسوية تستعد لإطلاق مسابقة (سبيل المنتظرين) بنسختها الثالثة

قسم الشؤون الفكرية يقدّم محاضرتين توعويتين لطلبة جامعة المنارة في ميسان

سماحة السيد الصافي يؤكّد أن القرآن عظّم شخصية النبي (صلّى الله عليه وآله) وكشف زيف ما أُلصِق بسيرته

المزيد

الآخبار الصحية

دراسة: محاولة متعمدة لنشر الإنفلونزا تنتهي بـ"مفاجأة"

من خبير في هارفارد.. 6 نصائح يومية "فعالة" لإبطاء الشيخوخة

7 مشروبات طبيعية لتقوية الذاكرة وزيادة التركيز

عرض شائع على الأصابع.. قد يكشف سرطان الرئة مبكرا

المزيد

الآخبار التكنلوجية

وسائل التواصل بين الإفراط والامتناع.. ما هو الحد الآمن للمراهقين؟

أعمق خندق في الكوكب الارض !

روساتوم: روسيا تقترب من تطوير ساعات ذرية فائقة الدقة

مفاجأة علمية عن الإنجاب.. كم طفلا يطيل عمر المرأة؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength