Michael D. Barrus - Weakly threshold graphs

dmtcs:3968 - Discrete Mathematics & Theoretical Computer Science, June 4, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-15
Weakly threshold graphs

Authors: Michael D. Barrus

    We define a weakly threshold sequence to be a degree sequence $d=(d_1,\dots,d_n)$ of a graph having the property that $\sum_{i \leq k} d_i \geq k(k-1)+\sum_{i > k} \min\{k,d_i\} - 1$ for all positive $k \leq \max\{i:d_i \geq i-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.


    Volume: Vol. 20 no. 1
    Section: Graph Theory
    Published on: June 4, 2018
    Accepted on: May 2, 2018
    Submitted on: September 30, 2017
    Keywords: Mathematics - Combinatorics,05C07, 05C30, 05C75

    2 Documents citing this article

    Consultation statistics

    This page has been seen 469 times.
    This article's PDF has been downloaded 285 times.