Sandwich Monotonicity and the Recognition of Weighted Graph Classes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915434672947200 |
|---|---|
| author | Beisegel, Jesse Chiarelli, Nina Köhler, Ekkehard Krnc, Matjaž Milanič, Martin Pivač, Nevena Scheffler, Robert Strehler, Martin |
| author_facet | Beisegel, Jesse Chiarelli, Nina Köhler, Ekkehard Krnc, Matjaž Milanič, Martin Pivač, Nevena Scheffler, Robert Strehler, Martin |
| contents | Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from an edge-weighted graph by removing all sufficiently light edges. This suggest a natural way of associating to any class $\mathcal{G}$ of unweighted graphs a corresponding class of edge-weighted graphs, namely by requiring that all level graphs belong to $\mathcal{G}$. We show that weighted graphs for which all level graphs are split, threshold, or chain graphs can be recognized in linear time using special edge elimination orderings. We obtain these results by introducing the notion of degree sandwich monotone graph classes. A graph class $\mathcal{G}$ is sandwich monotone if every edge set which may be removed from a graph in $\mathcal{G}$ without leaving the class also contains a single edge that can be safely removed. Furthermore, if we require the safe edge to fulfill a certain degree property, then $\mathcal{G}$ is called degree sandwich monotone. We present necessary and sufficient conditions for the existence of a linear-time recognition algorithm for any weighted graph class whose corresponding unweighted class is degree sandwich monotone and contains all edgeless graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06216 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sandwich Monotonicity and the Recognition of Weighted Graph Classes Beisegel, Jesse Chiarelli, Nina Köhler, Ekkehard Krnc, Matjaž Milanič, Martin Pivač, Nevena Scheffler, Robert Strehler, Martin Discrete Mathematics Data Structures and Algorithms Combinatorics Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from an edge-weighted graph by removing all sufficiently light edges. This suggest a natural way of associating to any class $\mathcal{G}$ of unweighted graphs a corresponding class of edge-weighted graphs, namely by requiring that all level graphs belong to $\mathcal{G}$. We show that weighted graphs for which all level graphs are split, threshold, or chain graphs can be recognized in linear time using special edge elimination orderings. We obtain these results by introducing the notion of degree sandwich monotone graph classes. A graph class $\mathcal{G}$ is sandwich monotone if every edge set which may be removed from a graph in $\mathcal{G}$ without leaving the class also contains a single edge that can be safely removed. Furthermore, if we require the safe edge to fulfill a certain degree property, then $\mathcal{G}$ is called degree sandwich monotone. We present necessary and sufficient conditions for the existence of a linear-time recognition algorithm for any weighted graph class whose corresponding unweighted class is degree sandwich monotone and contains all edgeless graphs. |
| title | Sandwich Monotonicity and the Recognition of Weighted Graph Classes |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2508.06216 |