Michael D. Barrus ; Jean A. Guillaume - Upward-closed hereditary families in the dominance order

dmtcs:5666 - Discrete Mathematics & Theoretical Computer Science, January 20, 2022, vol. 23, no. 3 - https://doi.org/10.46298/dmtcs.5666
Upward-closed hereditary families in the dominance orderArticle

Authors: Michael D. Barrus ; Jean A. Guillaume

    The majorization relation orders the degree sequences of simple graphs into posets called dominance orders. As shown by Ruch and Gutman (1979) and Merris (2002), the degree sequences of threshold and split graphs form upward-closed sets within the dominance orders they belong to, i.e., any degree sequence majorizing a split or threshold sequence must itself be split or threshold, respectively. Motivated by the fact that threshold graphs and split graphs have characterizations in terms of forbidden induced subgraphs, we define a class $\mathcal{F}$ of graphs to be dominance monotone if whenever no realization of $e$ contains an element $\mathcal{F}$ as an induced subgraph, and $d$ majorizes $e$, then no realization of $d$ induces an element of $\mathcal{F}$. We present conditions necessary for a set of graphs to be dominance monotone, and we identify the dominance monotone sets of order at most 3.


    Volume: vol. 23, no. 3
    Section: Graph Theory
    Published on: January 20, 2022
    Accepted on: November 5, 2021
    Submitted on: August 2, 2019
    Keywords: Mathematics - Combinatorics,05C07

    Consultation statistics

    This page has been seen 466 times.
    This article's PDF has been downloaded 227 times.