Enumerating threshold graphs and some related graph classes

MaRDI QIDQ5080334zbMATH OpenFDO

Authors David Galvin, Greyson Wesley, Bailee Zacovic

Publication date 31 May 2022

Full work available at URL https://arxiv.org/abs/2110.08953, https://cs.uwaterloo.ca/journals/JIS/VOL25/Galvin/galvin2.html

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

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)

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.

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

Cites work

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

Cited in

(7)

• Oriented threshold graphs
• On dynamic threshold graphs and related classes
• Counting Labeled Threshold Graphs with Eulerian Numbers
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• scientific article; zbMATH DE number 3997845 (Why is no real title available?)
• scientific article; zbMATH DE number 5575414 (Why is no real title available?)
• Recognizing cographs and threshold graphs through a classification of their edges

Describes a project that uses

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)