Probability recurrences on simple graphs in a forest building process

Date
2019-01-01
Authors
Alameda, Joseph
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

Consider the following process on a simple graph with no isolated vertices: Randomly order the edges and remove an edge if and only if the edge is incident to two vertices already incident to some preceding edge. This process results in a spanning forest of the graph.

Recurrences are given for the process for multiple families of graphs, and the probability of obtaining $k$ components in the above process is given by a new method for the Fan graph $F_{n-2,2}$. An approach to proving a previously published conjecture is also discussed.

Description
Keywords
graphs, forests, trees, recurrence, probability
Citation