✦ LIBER ✦

Graphs omitting a bushy tree

✍ Scribed by Cherlin, G.; Shi, N.; Tallgren, L.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 152 KB
Volume: 26
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199712)26:4<203::aid-jgt4>3.0.co;2-u

No coin nor oath required. For personal study only.

✦ Synopsis

A tree is called bushy if it has no vertex of degree 2. Theorem: the class of countable graphs omitting a fixed finite bushy tree with at least 5 vertices has no universal element.

📜 SIMILAR VOLUMES

Graphs omitting a finite set of cycles

✍ Cherlin, Gregory; Shi, Niandong 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 2 views

We prove that for C a finite set of cycles, there is a universal C-free graph if and only if C consists precisely of all the odd cycles of order less than same specified bound.

Metric characterizations of proper inter

Metric characterizations of proper interval graphs and tree-clique graphs

✍ Gutierrez, M.; Oubi�a, L. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real

The largest induced tree in a sparse ran

The largest induced tree in a sparse random graph

✍ W. Fernandez de la Vega 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 2 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar

Solving Steiner tree problems in graphs

Solving Steiner tree problems in graphs to optimality

✍ Koch, T.; Martin, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 2 views

In this paper, we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics. We are able to solve nea

Remarks on the placeability of isomorphi

Remarks on the placeability of isomorphic trees in a complete graph

✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 2 views

Let Tp be any tree of order p and A ( T p ) stand for the maximum degree of the vertices of Tp. We prove the following theorem. "If A(Tp) 5 pi, where p > 2i, then Tp is i-placeable in Kp" is true if and only if i = 1, 2, and 3. 0 1996 John Wiley & Sons, Inc. Suppose G is a graph and V ( G ) , E ( G

Calculating the number of spanning trees

Calculating the number of spanning trees in a labeled planar molecular graph whose inner dual is a tree

✍ P. E. John; R. B. Mallion 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 496 KB 👁 2 views

The quantum mechanical relevance of the concept of a spanning tree extant within a given molecular graph-specifically, one that may be considered to represent the carbon-atom connectivity of a particular (planar) conjugated system-was first explicitly pointed out by Professor Roy McWeeny in his now-