|
|||||
|
|
A forest building process on simple graphs |
|
| Authors: | Zhanar Berikkyzy Steve Butler Jay Cummings Kristin Heysse Paul Horn Ruth Luo Brent Moran |
| Institution: | 1. Department of Mathematics, University of California, Riverside, Riverside, CA, USA;2. Department of Mathematics and Statistics, Sacramento State University, Sacramento, CA, USA;3. Department of Mathematics, Statistics, and Computer Science, Macalester College, St. Paul, MN, USA;4. Department of Mathematics, University of Denver, Denver, CO, USA;5. Department of Mathematics, University of Illinois at Urbana-Champaign, Champaign, IL, USA;6. Berlin Mathematical School, Freie Universität Berlin, Germany |
| Abstract: | Consider the following process on a simple graph without isolated vertices: order the edges randomly and keep an edge if and only if it contains a vertex which is not contained in some preceding edge. The resulting set of edges forms a spanning forest of the graph.The probability of obtaining components in this process for complete bipartite graphs is determined as well as a formula for the expected number of components in any graph. A generic recurrence and some additional basic properties are discussed. |
| Keywords: | Forests Graph polynomial Edge flipping |
| 本文献已被 ScienceDirect 等数据库收录！ | |