Random threshold digraphs

MaRDI QIDQ405260zbMATH OpenFDO

Authors Yiguang Zhang, Elizabeth Reilly, Edward Scheinerman

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p48

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

directed graphsrandom graphsthreshold graphs

Mathematics Subject Classification ID

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

Review text

Summary: This paper introduces a notion of a random threshold directed graph, extending the work of Reilly and Scheinerman in the undirected case and closely related to random Ferrers digraphs.{ }We begin by presenting the main definition: \(D\) is a threshold digraph provided we can find a pair of weighting functions \(f,g:V(D)\to\mathbb{R}\) such that for distinct \(v,w\in V(D)\) we have \(v\to w\) iff \(f(v)+g(w)\geq1\). We also give an equivalent formulation based on an order representation that is purely combinatorial (no arithmetic). We show that our formulations are equivalent to the definition in the work of Cloteaux, LaMar, Moseman, and Shook in which the focus is on the degree sequence, and present a new characterization theorem for threshold digraphs. { }We then develop the notion of a random threshold digraph formed by choosing vertex weights independently and uniformly at random from \([0,1]\). We show that this notion of a random threshold digraph is equivalent to a purely combinatorial approach, and present a formula for the probability of a digraph based on counting linear extensions of an auxiliary partially ordered set. We capitalize on this equivalence to develop exact and asymptotic properties of random threshold digraphs such as the number of vertices with in-degree (or out-degree) equal to zero, domination number, connectivity and strong connectivity, clique and independence number, and chromatic number.

Recommendations

• Random threshold graphs
• scientific article; zbMATH DE number 2188468
• A note on thresholds and connectivity in random directed graphs
• An exact threshold theorem for random graphs and the node-packing problem
• scientific article; zbMATH DE number 4029600

Cites work

• A Class of Statistics with Asymptotically Normal Distribution
• Approximation Theorems of Mathematical Statistics
• Counting linear extensions
• Directed Random Dot Product Graphs
• Ferrers digraphs and threshold graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• Properties of random difference graphs
• Random threshold graphs
• The strong perfect graph theorem
• Threshold graph limits and random threshold graphs
• Threshold graphs and related topics

Cited in

(10)

• On small subgraphs in a random intersection digraph
• Random threshold graphs
• The transitive closure of a random digraph
• scientific article; zbMATH DE number 4029600 (Why is no real title available?)
• Oriented threshold graphs
• A note on thresholds and connectivity in random directed graphs
• scientific article; zbMATH DE number 2188468 (Why is no real title available?)
• The threshold for combs in random graphs
• scientific article; zbMATH DE number 7650133 (Why is no real title available?)
• On relations between neighborhoods of threshold and Ferrers digraphs

This page was built for publication: Random threshold digraphs

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