Probability recurrences on simple graphs in a forest building process

Date
2019-01-01
Authors
Alameda, Joseph
Major Professor
Steve Butler
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
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.

Comments
Description
Keywords
Citation
DOI
Source