A forest building process on simple graphs

DOI10.1016/J.DISC.2017.09.017MaRDI QIDQ1686006zbMATH OpenOpenAlexFDO

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

Publication date 20 December 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.00335

zbMATH Keywords

graph polynomialforestsedge flipping

Mathematics Subject Classification ID

Graph polynomials (05C31)

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.

Recommendations

• Graphs with at most two trees in a forest-building process
• scientific article; zbMATH DE number 2066194
• Random two-component spanning forests
• The edge correlation of random forests
• Tree and forest weights and their application to nonuniform random graphs

Cites work

• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Edge flipping in graphs
• Edge flipping in the complete graph
• Graph polynomials and their applications. I: The Tutte polynomial
• Graph polynomials and their applications. II: Interrelations and interpretations
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• The isoperimetric number of random regular graphs

Cited in

(2)

• Graphs with at most two trees in a forest-building process
• On the distribution in a graph process

This page was built for publication: A forest building process on simple graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686006)