Premium
The Reverse H ‐free Process for Strictly 2‐Balanced Graphs
Author(s) -
Makai Tamás
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21821
Subject(s) - combinatorics , mathematics , null graph , graph , random regular graph , discrete mathematics , complement graph , line graph , random graph , voltage graph , 1 planar graph
Consider the random graph process that starts from the complete graph on n vertices. In every step, the process selects an edge uniformly at random from the set of edges that are in a copy of a fixed graph H and removes it from the graph. The process stops when no more copies of H exist. When H is a strictly 2‐balanced graph we give the exact asymptotics on the number of edges remaining in the graph when the process terminates and investigate some basic properties namely the size of the maximal independent set and the presence of subgraphs.