Upward-closed hereditary families in the dominance order

DOI10.46298/DMTCS.5666MaRDI QIDQ5024680zbMATH OpenOpenAlexWikidataFDO

Authors Michael D. Barrus, Jean A. Guillaume

Publication date 27 January 2022

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1905.09411, https://dmtcs.episciences.org/8958

zbMATH Keywords

degree sequencedominance orderforbidden subgraphmajorization

Mathematics Subject Classification ID

Vertex degrees (05C07) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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 $mathcalF$ of graphs to be dominance monotone if whenever no realization of $e$ contains an element $mathcalF$ as an induced subgraph, and $d$ majorizes $e$, then no realization of $d$ induces an element of $mathcalF$. 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.

Recommendations

• Degree sequences of graphs and dominance order
• The principal Erdős-Gallai differences of a degree sequence
• The polytope of degree sequences
• Degree sequences and majorization
• Pseudodomishold graphs

Cites work

• Degree sequences and majorization
• scientific article; zbMATH DE number 3720966 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Linear recognition of pseudo-split graphs
• Majorization and the number of bipartite graphs for given vertex degrees
• Realizability and uniqueness in graphs
• Split graphs
• The lattice of integer partitions
• The realization graph of a degree sequence with majorization gap 1 is Hamiltonian
• The structure of a linear chip firing game and related models
• Threshold graphs and related topics
• Weakly threshold graphs

Cited in

(1)

• Independent domination in hereditary classes

This page was built for publication: Upward-closed hereditary families in the dominance order

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