##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 679.05061

**Autor: ** Alavi, Yousef; Malde, Paresh J.; Schwenk, Allen J.; Erdös, Paul

**Title: ** The vertex independence sequence of a graph is not constrained. (In English)

**Source: ** Combinatorics, graph theory, and computing, Proc. 18th Southeast. Conf., Boca Raton/Fl. 1987, Congr. Numerantium 58, 15-23 (1987).

**Review: ** [For the entire collection see Zbl 638.00009.]

We consider a sequence of parameters a_{1},a_{2},...,a_{m} associated with a graph G. For example, m can be the maximum number of independent vertices in G and each a_{i} is then the number of independent sets of order i. Sorting this list into nondecreasing order determines a permutation \pi on the indices so that a_{\pi (1)} \leq a_{\pi (2)} \leq ... \leq a_{\pi (m)}. We call a sequence constrained if certain permutations \pi cannot be realized by any graph. It is well known that the edge independence sequence is constrained to be unimodal. The vertex independence sequence was conjectured to be likewise, but we show that, quite the contrary, it is totally unconstrained. That is, every permutation is realized by some graph.

**Reviewer: ** R.C.Read

**Classif.: ** * 05C75 Structural characterization of types of graphs

05C99 Graph theory

**Keywords: ** vertex independence sequence

**Citations: ** Zbl 638.00009

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag