✦ LIBER ✦

The square of a chordal graph

✍ Scribed by Frank Harary; Terry A. McKee

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 427 KB
Volume: 128
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90110-4

No coin nor oath required. For personal study only.

✦ Synopsis

We introduce the closed-neighborhood intersection multigraph as a useful multigraph version of the square of a graph. We characterize those multigraphs which are squares of chordal graphs and include an algorithm to go from the squared chordal graph back to its (unique!) square root. This becomes particularly simple in the case of k-trees, with the case of trees evoking a 1960 paper by Harary and Ross (1960) titled 'The Square of a Tree'.

📜 SIMILAR VOLUMES

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.

On the chordality of a graph

✍ Terry A. McKee; Edward R. Scheinerman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 574 KB

## Abstract The __chordality__ of a graph __G__ = (__V, E__) is defined as the minimum __k__ such that we can write __E__ = __E__~1~ ∩ … ∩ __E__~__k__~ with each (__V, E__~__i__~) a chordal graph. We present several results bounding the value of this generalization of boxicity. Our principal result

A generalization of chordal graphs

✍ P. D. Seymour; R. W. Weaver 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 487 KB

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In t

On the interval number of a chordal grap

On the interval number of a chordal graph

✍ Edward R. Scheinerman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB 👁 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum

The w-median of a connected strongly cho

The w-median of a connected strongly chordal graph

✍ Hai-Yen Lee; Gerard J. Chang 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB 👁 1 views

## Abstract Suppose __G = (V, E)__ is a graph in which every vertex __x__ has a non‐negative real number __w(x)__ as its weight. The __w__‐distance sum of a vertex __y__ is __D~G, w~(y)__ = σ~x≅v~ __d(y, x)w(x).__ The __w__‐median of __G__ is the set of all vertices __y__ with minimum __w__‐distanc

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