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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page