Weakly threshold graphs

MaRDI QIDQ4560238zbMATH OpenFDO

Authors Michael D. Barrus

Publication date 10 December 2018

Full work available at URL https://arxiv.org/abs/1608.01358, https://dmtcs.episciences.org/4524/pdf

zbMATH Keywords

degree sequenceErdős-Gallai inequalitythreshold graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75)

Abstract: We define a weakly threshold sequence to be a degree sequence $d=(d_1,dots,d_n)$ of a graph having the property that $su{m}_{ileqk}{d}_{i}geqk(k-1)+su{m}_{i>k}mink,d_i-1$ for all positive $kleqmaxi:d_{i}geqi-1$. The weakly threshold graphs are the realizations of the weakly threshold sequences. The weakly threshold graphs properly include the threshold graphs and satisfy pleasing extensions of many properties of threshold graphs. We demonstrate a majorization property of weakly threshold sequences and an iterative construction algorithm for weakly threshold graphs, as well as a forbidden induced subgraph characterization. We conclude by exactly enumerating weakly threshold sequences and graphs.

Recommendations

• The polytope of degree sequences
• Degree sequences and majorization
• Multithreshold graphs
• Adjacency relationships forced by a degree sequence
• The realization graph of a degree sequence with majorization gap 1 is Hamiltonian

Cited in

(6)

• Degree sequences and majorization
• Mock threshold graphs
• The principal Erdős-Gallai differences of a degree sequence
• Optimization problems on threshold graphs
• Upward-closed hereditary families in the dominance order
• Linear-time recognition of double-threshold graphs

This page was built for publication: Weakly threshold graphs

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