Oriented threshold graphs

MaRDI QIDQ4616091zbMATH OpenFDO

Authors Derek Boeckner

Publication date 30 January 2019

Full work available at URL https://arxiv.org/abs/1511.01008, http://ajc.maths.uq.edu.au/pdf/71/ajc_v71_p043.pdf

zbMATH Keywords

Fibonacci numberstransitive orientations of threshold graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Abstract: Threshold graphs are a prevalent and widely studied class of simple graphs. They have several equivalent definitions which makes them a go-to class for finding examples and counter examples when testing and learning. This versatility has led to many results about threshold graphs and similar structures. We look to generalize this class of graphs to oriented graphs (directed simple graphs.) We give generalizations to four of the most versatile definitions and show their equivalence in the oriented case. We finish with a proof enumerating the number of these oriented threshold graphs which relates to the Fibonacci numbers.

Recommendations

• Enumerating threshold graphs and some related graph classes
• Counting Labeled Threshold Graphs with Eulerian Numbers
• On Universal Threshold Graphs
• Random threshold digraphs
• scientific article; zbMATH DE number 3997845

Cites work

• Random threshold digraphs
• Split digraphs
• Threshold graph limits and random threshold graphs
• Threshold graphs and related topics

Cited in

(12)

• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Oriented coloring on recursively defined digraphs
• On characterizations for subclasses of directed co-graphs
• Comparing linear width parameters for directed graphs
• Counting Labeled Threshold Graphs with Eulerian Numbers
• scientific article; zbMATH DE number 3997845 (Why is no real title available?)
• Oriented incidence energy and threshold graphs
• Vertex deletion on split graphs: beyond 4-hitting set
• Targeting in social networks with anonymized information
• Comparability digraphs: an analogue of comparability graphs
• Core-periphery and nested networks emerging from a simple model of network formation
• Permutations représentatives d'un graphe à seuil

This page was built for publication: Oriented threshold graphs

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