Structural and Spectral Properties of Strictly Interval Graphs
By: Lilian Markenzon, Claudia Justel
Potential Business Impact:
Finds patterns in networks faster.
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.
Similar Papers
Interval Graphs are Reconstructible
Combinatorics
Finds hidden patterns in connected things.
Interval H-graphs : Recognition and forbidden obstructions
Discrete Mathematics
Maps connections between groups using number lines.
Forbidden Induced Subgraph Characterization of Word-Representable Split Graphs
Combinatorics
Helps understand how words form pictures.