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 a1,a2,...,am associated with a graph G. For example, m can be the maximum number of independent vertices in G and each ai 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