On a class of kernel-perfect and kernel-perfect-critical graphs

✍ Scribed by Kiran B. Chilakamarri; Peter Hamburger

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 275 KB
• Volume: 118
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90068-5

✦ Synopsis

Chilakamarri, K.B. and P. Hamburger, On a class of kernel-perfect and kernel-perfect-critical graphs, Discrete Mathematics 118 (1993) 253-257.

In this note we present a construction of a class of graphs in which each of the graphs is either kernel-perfect or kernel-perfect-critical. These graphs originate from the theory of games (Von Neumann and Morgenstern).

We also find criteria to distinguish kernel-perfect graphs from kernelperfect-critical graphs in this class. We obtain some of the previously known classes of kernelperfect-critical graphs as special cases of the present construction given here. The construction that we give enlarges the class of kernel-perfect-critical graphs.

Let G=(X, W) be a directed graph with no loops and no multiple arcs. For any subsetKcX,onedefinesr-(K)={xEX:thereisanarcfromxtoyforsomeyinK}.

If a vertex x is in r-(K), then we say that x is absorbed by K. Throughout this note we consider graphs with no loops and no multiple arcs.

A kernel in a directed graph G =(X, W) is a subset Kc X of vertices with the following properties: