𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decreasing the diameter of bounded degree graphs

✍ Scribed by Noga Alon; András Gyárfás; Miklós Ruszinkó

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
118 KB
Volume
35
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Extremal graphs of diameter two and give
Extremal graphs of diameter two and given maximum degree, embeddable in a fixed surface
✍ Knor, Martin; ?ir�?, Jozef 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 2 views

It is known that for each d there exists a graph of diameter two and maximum degree d which has at least (d/2) (d + 2)/2 vertices. In contrast with this, we prove that for every surface S there is a constant d S such that each graph of diameter two and maximum degree d ≥ d S , which is embeddable in

On low bound of degree sequences of span
On low bound of degree sequences of spanning trees inK-edge-connected graphs
✍ Zhenhong, Liu; Baoguang, Xu 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 3 views

[•] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d k -tree, and α = 1 for k = 2, α = 2 for k ≥ 3.

On the superconnectivity and the conditi
On the superconnectivity and the conditional diameter of graphs and digraphs
✍ Carmona, A.; F�brega, J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

It has been proved that if the diameter D of a digraph G satisfies D Յ 2ᐉ Ϫ 2, where ᐉ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D Յ 2ᐉ Ϫ 1, then G is edge-superconnected. In this paper, we studied some similar condi

The degree sequence of a random graph. I
The degree sequence of a random graph. I. The models
✍ Brendan D. McKay; Nicholas C. Wormald 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 2 views

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of 1 random graphs with n vertices and m edges. Fo

On some simple degree conditions that gu
On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
✍ Vu, Van H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 2 views

It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/ log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-menti