Geodesic
Upward-closed hereditary families in the dominance order
Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.5666
Classification : 05C07, 05C69 
@article{DMTCS_2021_23_3_a16,
     author = {Barrus, Michael D. and Guillaume, Jean A.},
     title = {Upward-closed hereditary families in the dominance order},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2021-2022},
     doi = {10.46298/dmtcs.5666},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5666/}
}
TY  - JOUR
AU  - Barrus, Michael D.
AU  - Guillaume, Jean A.
TI  - Upward-closed hereditary families in the dominance order
JO  - Discrete mathematics & theoretical computer science
PY  - 2021-2022
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5666/
DO  - 10.46298/dmtcs.5666
LA  - en
ID  - DMTCS_2021_23_3_a16
ER  - 
%0 Journal Article
%A Barrus, Michael D.
%A Guillaume, Jean A.
%T Upward-closed hereditary families in the dominance order
%J Discrete mathematics & theoretical computer science
%D 2021-2022
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5666/
%R 10.46298/dmtcs.5666
%G en
%F DMTCS_2021_23_3_a16
Barrus, Michael D.; Guillaume, Jean A. Upward-closed hereditary families in the dominance order. Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3. doi : 10.46298/dmtcs.5666. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5666/

Cité par Sources :