Probability recurrences on simple graphs in a forest building process

Thumbnail Image
Date
2019-01-01
Authors
Alameda, Joseph
Major Professor
Steve Butler
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
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.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article
Comments
Rights Statement
Copyright
Tue Jan 01 00:00:00 UTC 2019
Funding
Supplemental Resources
Source