✦ LIBER ✦

Clique neighborhoods and nearly chordal graphs

✍ Scribed by Terry A. McKee

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 559 KB
Volume: 171
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00028-3

No coin nor oath required. For personal study only.

✦ Synopsis

We study two new special families of complete subgraphs of a graph. For chordal graphs, one of these reduces to the family of minimal vertex separators while the other is empty. When the intersection characterization of chordal graphs is extended from acyclic (i.e., K3-free chordal) hosts to K4-free chordal hosts, these new families are as fundamental as minimal vertex separators are for chordal graphs. Every graph satisfies certain inequalities involving the cardinalities of these families, with interesting questions arising when equality holds.

📜 SIMILAR VOLUMES

Strong clique trees, neighborhood trees,

Strong clique trees, neighborhood trees, and strongly chordal graphs

✍ McKee, Terry A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationsh

Squares, clique graphs, and chordality

✍ W. D. Wallis; Julin Wu 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB

## Abstract We study the squares and the clique graphs of chordal graphs and various special classes of chordal graphs. Chordality conditions for squares and clique graphs are given. Several theorems concering chordal graphs are generalized. © 1996 John Wiley & Sons, Inc.

Dominating cliques in chordal graphs

✍ Dieter Kratsch; Peter Damaschke; Anna Lubiw 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 492 KB

A chordal graph has a dominating clique iff it has diameter at most 3. A strongly chordal graph which has a dominating clique has one as small as the smallest dominating set-and, furthermore, there is a linear-time algorithm to find such a small dominating clique.

Diameters of iterated clique graphs of c

Diameters of iterated clique graphs of chordal graphs

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

Partitioning chordal graphs into indepen

Partitioning chordal graphs into independent sets and cliques

✍ Pavol Hell; Sulamita Klein; Loana Tito Nogueira; Fábio Protti 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 217 KB

We consider the following generalization of split graphs: A graph is said to be a (k; ')-graph if its vertex set can be partitioned into k independent sets and ' cliques. (Split graphs are obtained by setting k = ' = 1.) Much of the appeal of split graphs is due to the fact that they are chordal, a

On covering all cliques of a chordal gra

On covering all cliques of a chordal graph

✍ Thomas Andreae; Carsten Flotow 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 205 KB

For a graph G = (V,E), a vertex set XC\_ V is called a clique if Ixl>~2 and the graph G [X] induced by X is a complete subgraph maximal under inclusion. We say that a vertex set T is a clique-transversal set if T N X ~ 0 for all cliques X of G, and define the clique-transversal number re(G) as the m