✦ LIBER ✦

Kernels in graphs with a clique-cutset

✍ Scribed by Henry Jacob

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 138 KB
Volume: 156
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(96)00018-0

No coin nor oath required. For personal study only.

✦ Synopsis

We consider graphs that have a clique-cutset, and we show that this property preserves the existence of a kernel in a certain sense.

We consider finite directed graphs that do not have multiple arcs or loops, but there may be symmetric arcs between some pairs of vertices. Let G = (V, A) be a directed graph, where V is the vertex-set and A is the arc-set. A kernel of G is a subset K of vertices such that (a) every vertex of G-K has a successor in K (the kernel is absorbant) and (b) there is no arc between any two vertices of the kernel (the kernel is stable). Not every directed graph admits a kernel; in fact it was shown by Chvhtal [2] that deciding if a graph possesses a kernel is an NP-complete problem; this result was strengthened by Fraenkel . On the other hand, many conditions are known that imply the existence of a kernel, see e.g. . Such conditions are usually hereditary, and so they also imply the existence of a kernel for every induced subgraph. A directed graph such that every induced subgraph has a kernel is called kernel-perfect. By similarity with other topics in graph theory, it is interesting to know what kind of graph constructions preserve kernel-perfectness. Here we consider the clique cutset. A clique-cutset is a subset C of vertices such that C is a clique and G -C is disconnected. For each connected component A of G-G we call the subgraph induced by A uC a piece of G with respect to C. The subgraph of G induced by a subset S will be denoted by G [S]. The main result of this paper is the following:

Theorem 1. Let G be a directed graph which admits a clique-cutset C. Then G is kernel-perfect if and only if every piece of G with respect to C is kernel-perfect.

This theorem should be viewed in parallel with some similar classical results in graph theory, in particular: if a graph admits a clique-cutset C, then it is

📜 SIMILAR VOLUMES

Disjoint clique cutsets in graphs withou

Disjoint clique cutsets in graphs without long holes

✍ Elaine M. Eschen; Chính T. Hoàng; Mark D. T. Petrick; R. Sritharan 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB

## Abstract A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class

The maximum number of q-cliques in a gra

The maximum number of q-cliques in a graph with no p-clique

✍ Steven Roman 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 805 KB

On connectivity in graphs with given cli

On connectivity in graphs with given clique number

✍ Angelika Hellwig; Lutz Volkmann 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 1 views

## Abstract We consider finite, undirected, and simple graphs __G__ of order __n__(__G__) and minimum degree δ(__G__). The connectivity κ(__G__) for a connected graph __G__ is defined as the minimum cardinality over all vertex‐cuts. If κ(__G__) < δ(__G__), then Topp and Volkmann 7 showed in 1993 f

Covering the cliques of a graph with ver

Covering the cliques of a graph with vertices

✍ Paul Erdős; Tibor Gallai; Zsolt Tuza 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 681 KB

The following problem is investigated. Given an undirected graph G, determine the smallest cardinality of a vertex set that meets all complete subgraphs KC G maximal under inclusion.

r-Dominating cliques in graphs with hype

r-Dominating cliques in graphs with hypertree structure

✍ Feodor F. Dragan; Andreas Brandstädt 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 848 KB

Let G = (V, E) be an undirected graph and r be a vertex weight function with positive integer values. A subset (clique) D ~\_ V is an r-dominating set (clique) in G ifffor every vertex v e V there is a vertex u e D with dist(u, v) <~ r(v). This paper contains the following results: (i) We give a si

Kernels in directed graphs: a poison gam

Kernels in directed graphs: a poison game

✍ P. Duchet; H. Meyniel 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 282 KB

We consider a two player game on a progressively and locally finite directed graph and we prove that the first player wins if and only if the graph has a local kernel. The result is sharp. From it, we derive a short proof of a general version of the Galeana-Sanchez & Neuman-Lara Theorem that give a