Imperfect Graph
المؤلف:
Godsil, C. and Royle, G
المصدر:
"Imperfect Graphs." §7.6 in Algebraic Graph Theory. New York: Springer-Verlag,
الجزء والصفحة:
...
4-3-2022
1825
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
