✦ LIBER ✦

On the tree representation of chordal graphs

✍ Scribed by Yukio Shibata

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 344 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120313

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Representations of chordal graphs as sub

Representations of chordal graphs as subtrees of a tree

✍ James R. Walter 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

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 degree-preserving spanning tree prob

The degree-preserving spanning tree problem in strongly chordal and directed path graphs

✍ Ching-Chi Lin; Gerard J. Chang; Gen-Huey Chen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract Suppose __G__ is a connected graph and __T__ a spanning tree of __G__. A vertex __v__ ε __V__(__G__) is said to be a degree‐preserving vertex if its degree in __T__ is the same as its degree in __G__. The degree‐preserving spanning tree problem is to find a spanning tree __T__ of a conn

On connectivities of tree graphs

✍ Guizhen Liu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 289 KB

Let T(G) be the tree graph of a graph G with cycle rank r. Then K ( T ( G ) ) 3 m ( G ) -r, where K(T(G)) and m(G) denote the connectivity of T ( G ) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m ( G ) -r is best possible.

On set intersection representations of g

On set intersection representations of graphs

✍ Stasys Jukna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 1 views

## Abstract The intersection dimension of a bipartite graph with respect to a type __L__ is the smallest number __t__ for which it is possible to assign sets __A__~__x__~⊆{1, …, __t__} of labels to vertices __x__ so that any two vertices __x__ and __y__ from different parts are adjacent if and only

Complexity of approximating the oriented

Complexity of approximating the oriented diameter of chordal graphs

✍ Fedor V. Fomin; Martín Matamala; Ivan Rapaport 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract The oriented diameter of a bridgeless connected undirected (__bcu__) graph __G__ is the smallest diameter among all the diameters of strongly connected orientations of __G__. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐