Enumerating threshold graphs and some related graph classes

zbMATH Open1490.05115arXiv2110.08953MaRDI QIDQ5080334FDOQ5080334

Authors: David Galvin, Greyson Wesley, Bailee Zacovic 

Publication date: 31 May 2022

Abstract: We give combinatorial proofs of some enumeration formulas involving labelled threshold, quasi-threshold, loop-threshold and quasi-loop-threshold graphs. In each case we count by number of vertices and number of components. For threshold graphs, we also count by number of dominating vertices, and for loop-threshold graphs we count by number of looped dominating vertices. We also obtain an analog of the Frobenius formula (connecting Eulerian numbers and Stirling numbers of the second kind) in the context of labelled threshold graphs.

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

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

Recommendations

• Threshold graphs and related topics
• scientific article; zbMATH DE number 5575414
• Publication:4724665
• Counting Labeled Threshold Graphs with Eulerian Numbers
• Some notes on the threshold graphs
• scientific article; zbMATH DE number 4033780
• Thresholds for classes of intersection graphs
• On a class of graphs between threshold and total domishold graphs
• Interval count of generalizations of threshold graphs
• Some complexity results about threshold graphs

zbMATH Keywords

Stirling number of the second kindset partitionthreshold graphEulerian numberquasi-threshold graphloop-threshold graphquasi-loop-threshold graph

Mathematics Subject Classification ID

Bell and Stirling numbers (11B73) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Trivially perfect graphs
• Combinatorics of permutations
• The Comparability Graph of a Tree
• Title not available (Why is that?)
• Über die Bernoullischen Zahlen und die Eulerschen Polynome
• An Alternate Approach to Alternating Sums: A Method to DIE for
• The number of spanning trees in \(K_ n\)-complements of quasi-threshold graphs
• Extremal graphs for homomorphisms
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Enumerative aspects of certain subclasses of perfect graphs
• Proofs from THE BOOK. Including illustrations by Karl H. Hofmann
• Extremal graphs for homomorphisms. II
• Counting Labeled Threshold Graphs with Eulerian Numbers

Cited In (7)

• On dynamic threshold graphs and related classes
• Oriented threshold graphs
• Counting Labeled Threshold Graphs with Eulerian Numbers
• Recognizing cographs and threshold graphs through a classification of their edges
• Title not available (Why is that?)
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Title not available (Why is that?)

Uses Software

• OEIS

This page was built for publication: Enumerating threshold graphs and some related graph classes

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