✦ LIBER ✦

Constructing trees in graphs with no K2,s

✍ Scribed by Suman Balasubramanian; Edward Dobson

Book ID: 102345562
Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 150 KB
Volume: 56
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20261

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let s ≥ 2 be an integer and k > 12(s − 1) an integer. We give a necessary and sufficient condition for a graph G containing no K~2,s~ with $\delta(G)\ge{k}/2$ and $\Delta(G)\ge k$ to contain every tree T of order k + 1. We then show that every graph G with no K~2,s~ and average degree greater than k − 1 satisfies this condition, improving a result of Haxell, and verifying a special case of the Erdős—Sós conjecture, which states that every graph of average degree greater than k − 1 contains every tree of order k + 1. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 301–310, 2007

📜 SIMILAR VOLUMES

Constructing trees in bipartite graphs

✍ U. Schulte 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 227 KB

In this paper we shall show that if G = (V,E) is a bipartite graph with more than (a -1)j YJ + (b -1)1X1 -(a -l)(b -1) edges, where (X, Y) is a vertex-partition for G and a < b are natural numbers with a < 1x1, b < 1 YI, then G contains every tree T with bipartitenumbers a < b. This result is relate

Graphs with no induced C4 and 2K2

✍ Zoltán Blázsik; Mihály Hujter; András Pluhár; Zsolt Tuza 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 274 KB

We characterize the structure of graphs containing neither the 4-cycle nor its complement as an induced subgraph. This self-complementary class B of graphs includes split graphs, which are graphs whose vertex set is the union of a clique and an independent set. In the members of Q, the number of cli

Infinite connected graphs with no end-pr

Infinite connected graphs with no end-preserving spanning trees

✍ Carsten Thomassen 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 189 KB

Construction of Large Graphs with No Opt

Construction of Large Graphs with No Optimal Surjective L (2,1)-Labelings

✍ Král', Daniel; Skrekovski, Riste; Tancer, Martin 📂 Article 📅 2006 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 147 KB

Multicolored trees in complete graphs

✍ S. Akbari; A. Alipour 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

## Abstract A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph __K__~2__n__~(__n__ > 2) with 2__n__ − 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize thi

Approximating Steiner trees in graphs wi

Approximating Steiner trees in graphs with restricted weights

✍ Halld�rsson, Magn�s M.; Ueno, Shuichi; Nakao, Hiroshi; Kajitani, Yoji 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 2 views

We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d °2. The improvement over other analyzed algorithms is a fac