Paperlane

no. 16 · Tuesday 17 November 2026

On Semi-interval and Para-interval Graphs

Chenxi Lv, Yiming Lei and Chunlei Xu

math.CO

Abstract

Bau and Johnson introduced semi-interval graphs and asked whether one of the two extremal sets can always be replaced by a single vertex. A negative answer to this question is given by a tree which has no such representation. It is also shown that a finite connected graph with at least two vertices is a semi-interval graph if and only if it is bipartite. Para-interval graphs, for which one extremal set consists of a single vertex, are characterized by necessary and sufficient conditions on their distance matrices. A characterization of para-interval trees is obtained, and a relation between para-interval graphs and shortest-path interval graphs is established by identifying the vertices of an extremal set. Finally, leveled graphs and the corresponding Hasse diagrams of finite partially ordered sets are considered.

fields
Combinatorics
pdf ↗ page arXiv:2611.19711 ↗