A forest building process on simple graphs

Zhanar Berikkyzy; Steve Butler; Jay Cummings; Kristin Heysse; Paul Horn; Ruth Luo; Brent Moran

doi:10.1016/j.disc.2017.09.017

Back

A forest building process on simple graphs

Journal article

Peer reviewed

A forest building process on simple graphs

Zhanar Berikkyzy, Steve Butler, Jay Cummings, Kristin Heysse, Paul Horn, Ruth Luo and Brent Moran

Discrete mathematics, Vol.341(2), pp.497-507

02/2018

DOI: https://doi.org/10.1016/j.disc.2017.09.017

Handle:

https://hdl.handle.net/20.500.12741/rep:5719

Abstract

Graph polynomial

Forests

Edge flipping

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.

Metrics

24 Record Views

Details

Title: A forest building process on simple graphs
Creators: Zhanar Berikkyzy - Department of Mathematics, University of California, Riverside, Riverside, CA, USA
Steve Butler - Department of Mathematics, University of California, Riverside, Riverside, CA, USA
Jay Cummings - Department of Mathematics and Statistics, Sacramento State University, Sacramento, CA, USA
Kristin Heysse - Department of Mathematics, Statistics, and Computer Science, Macalester College, St. Paul, MN, USA
Paul Horn - Department of Mathematics, University of Denver, Denver, CO, USA
Ruth Luo - Department of Mathematics, University of Illinois at Urbana-Champaign, Champaign, IL, USA
Brent Moran - Berlin Mathematical School, Freie Universität Berlin, Germany
Academic Unit: Mathematics/Statistics Department
Publisher: Elsevier B.V
Publication Details: 02/2018
Identifiers: 99257847148301671; https://hdl.handle.net/20.500.12741/rep:5719; https://doi.org/10.1016/j.disc.2017.09.017
Language: English

A forest building process on simple graphs

Abstract

Related links

Metrics

Details