| The idea of independent sets, sets of vertices which contain no edges between them, has been widely studied in many classes of graphs. A b-independent set is similar except that the vertices in a b-independent set are not even connected by short paths of length b or less. This thesis places probabilistic bounds of the size of the largest b-independent set in three classes of random graph: Gn,p where the random generation of each edge is an independent event, random regular graphs Gn,r, and Gk-out where each vertex has minimum degree k. It also analyzes the greedy algorithm for finding large b-independent sets in Gk-out, showing the with high probability the greedy algorithm will discover a b-independent set of about half maximum size. |
