Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Upward-closed heredi ...
Article

Upward-closed hereditary families in the dominance order

Michael D. Barrus, Jean A. Guillaume ORCID
Download article
Open on arXiv
Submitted on
August 2, 2019
Accepted on
November 5, 2021
Published on
January 20, 2022
Last modified on
March 31, 2025
Volume 23
vol. 23:3
Graph Theory
DOI
10.46298/dmtcs.5666
License
arXiv.org - Non-exclusive license to distribute
Indicators
1102
Views
956
Downloads

Upward-closed hereditary families in the dominance order

Michael D. Barrus, Jean A. Guillaume ORCID
Abstract
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. Comment: 19 pages, 5 figures. Final accepted version
Keywords
  • Mathematics - Combinatorics
  • 05C07
Mathematics Subject Classification 2020
  • 05C07 - Vertex degrees
  • 05C69 - Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Preview
Loading PDF preview...