pith. machine review for the scientific record. sign in

arxiv: 1608.00335 · v2 · submitted 2016-08-01 · 🧮 math.CO

Recognition: unknown

A forest building process on simple graphs

Authors on Pith no claims yet
classification 🧮 math.CO
keywords graphprocesscomponentsedgeedgesforestgraphssimple
0
0 comments X
read the original 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 $k$ 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.