Article ID Journal Published Year Pages File Type
4649060 Discrete Mathematics 2007 4 Pages PDF
Abstract

Given a graph G   and field FF, the well-covered vector space of G   is the vector space of all functions f:V(G)→Ff:V(G)→F such that ∑v∈If(v) is constant for all maximal independent sets I  . We show here that, over all fields FF, almost all graphs G∈Gn,pG∈Gn,p has well-covered dimension 0 over FF. As a corollary, we prove that almost no graphs G∈Gn,pG∈Gn,p are well-covered.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,