Structural and Spectral Properties of Strictly Interval Graphs
cs.DM, math.CO
Submitted: 2025-12-01
Updated: 2026-11-01
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this paper we deal with a subclass of chordal graphs, which are simultaneously strictly chordal and interval, the strictly interval graphs.
Terminology
Abstract
In this paper we deal with a subclass of chordal graphs, which are simultaneously strictly chordal and interval, the strictly interval graphs. We present a new characterization of the class that leads to a simple linear recognition algorithm. Next we introduce a new subclass of strictly interval graphs, the SI-core graphs, that are non-split and non-cograph graphs and show that several elements of the new class are Laplacian integral
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns