𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The insulation sequence of a graph

✍ Scribed by Elena Grigorescu

Book ID
104294230
Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
419 KB
Volume
134
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In a graph G, a k-insulated set S is a subset of the vertices of G such that every vertex in S is adjacent to at most k vertices in S, and every vertex outside S is adjacent to at least k + 1 vertices in S. The insulation sequence i0; i1; i2; : : : of a graph G is deΓΏned by setting i k equal to the maximum cardinality of a k-insulated set in G. We determine the insulation sequence for paths, cycles, fans, and wheels. We also study the e ect of graph operations, such as the disjoint union, the join, the cross product, and graph composition, upon k-insulated sets. Finally, we completely characterize all possible orderings of the insulation sequence, and prove that the insulation sequence is increasing in trees.

πŸ“œ SIMILAR VOLUMES

On the power sequence of a graph
On the power sequence of a graph
✍ A. Ramachandra Rao; S. B. Rao πŸ“‚ Article πŸ“… 1970 πŸ› The Hebrew University Magnes Press 🌐 English βš– 202 KB
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