The sequential generation of random f-graphs. Distributions and predominant types of edge maximal f-graphs with f>4

DOI10.1016/0012-365X(93)90352-TMaRDI QIDQ685646zbMATH OpenOpenAlexFDO

Authors Krystyna T. Balińska, Louis V. Quintas

Publication date 24 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)90352-t

zbMATH Keywords

\(f\)-graphedge-maximal \(f\)-graphprobabilitiesrandom \(f\)-graphsvertex degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Review text

An \(f\)-graph is a graph whose vertices are all of degree no greater than \(f\); an edge-maximal \(f\)-graph is an \(f\)-graph such that adding any edges will make one of the vertices of degree \(f+1\). One can generate random edge-maximal \(f\)-graphs by adding edges randomly, one at a time, until it is an edge-maximal \(f\)-graph. This note lists some of the facts known and problems for the probabilities \(P(m;n;f)=\) the probability that such a randomly generated edge-maximal \(f\)-graph on \(n\) vertices has \(m\) vertices of degree \(<f\).

Recommendations

• scientific article; zbMATH DE number 434917
• The classification of f-coloring of random graphs
• scientific article; zbMATH DE number 1890147
• Degrees in a digraph whose nodes are graphs
• A kinetic approach to the random \(f\)-graph process. Paths, cycles and components

Cited in

(5)

• Degrees in a digraph whose nodes are graphs
• A kinetic approach to the random \(f\)-graph process. Paths, cycles and components
• scientific article; zbMATH DE number 434917 (Why is no real title available?)
• scientific article; zbMATH DE number 2188439 (Why is no real title available?)
• The maximum number of one-edge extensions for graphs with bounded degree.

This page was built for publication: The sequential generation of random \(f\)-graphs. Distributions and predominant types of edge maximal \(f\)-graphs with \(f>4\)

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