A classification of isomorphism-invariant random digraphs

DOI10.11575/CDM.V15I3.62742MaRDI QIDQ5149414zbMATH OpenOpenAlexFDO

Authors Selim Bahadır, Elvan Ceyhan

Publication date 11 February 2021

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

zbMATH Keywords

probability spacerandom graphs and digraphsnearest neighbor digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We classify isomorphism-invariant random digraphs according to where randomness resides, namely, arcs, vertices, and vertices and arcs together which in turn yield arc random digraphs (ARD), vertex random digraphs (VRD) and vertex-arc random digraphs (VARD), respectively. This digraph classification can be viewed as an extension of the classification of isomorphism-invariant random graphs. We introduce randomness in the direction of the edges of a given graph and obtain direction random digraphs (DRD) as well. We classify DRDs according to which component is random in addition to the direction and study the relations of DRDs with VARDs, VRDs and ARDs. We also consider random nearest neighbor digraphs and determine their membership with respect to these digraph families.

Recommendations

• A random intersection digraph: indegree and outdegree distributions
• scientific article; zbMATH DE number 4029600
• Connectivity of a general class of inhomogeneous random digraphs
• On vertex, edge, and vertex-edge random graphs
• On vertex, edge, and vertex-edge random graphs (extended abstract)

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 4153728 (Why is no real title available?)
• scientific article; zbMATH DE number 3719745 (Why is no real title available?)
• scientific article; zbMATH DE number 3551712 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• A note on thresholds and connectivity in random directed graphs
• A random intersection digraph: indegree and outdegree distributions
• Birth of a strongly connected giant in an inhomogeneous random digraph
• Central limit theorems for some graphs in computational geometry.
• Comparison of relative density of two random geometric digraph families in testing spatial clustering
• Finding induced acyclic subgraphs in random digraphs
• Graph-theoretic measures of multivariate association and prediction
• Longest cycles in sparse random digraphs
• On nearest-neighbor graphs
• On vertex, edge, and vertex-edge random graphs (extended abstract)
• Random Geometric Graphs
• Random Graphs
• Relative density of the random \(R\)-factor proximity catch digraph for testing spatial patterns of segregation and association
• The critical behavior of random digraphs
• The phase transition in the evolution of random digraphs
• The transitive closure of a random digraph

This page was built for publication: A classification of isomorphism-invariant random digraphs

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