pith. sign in

arxiv: 2512.01175 · v2 · pith:TSRFXADPnew · submitted 2025-12-01 · 💻 cs.DM · math.CO

Structural and Spectral Properties of Strictly Interval Graphs

Claudia Justel , Lilian Markenzon This is my paper

Pith reviewed 2026-05-21 18:51 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords strictly interval graphschordal graphsinterval graphslinear recognition algorithmLaplacian integralSI-core graphsspectral properties
0
0 comments X

The pith

Strictly interval graphs can be recognized in linear time via a new structural characterization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines strictly interval graphs as the intersection of strictly chordal graphs and interval graphs within the broader chordal class. It supplies a fresh characterization of the class that immediately supports a straightforward linear-time recognition procedure. The authors further define the SI-core graphs as a subclass that is neither split nor cograph and establish that several members of this subclass possess entirely integral Laplacian spectra.

Core claim

We present a new characterization of strictly interval graphs that leads to a simple linear recognition algorithm. We introduce the SI-core graphs, a new subclass of strictly interval graphs that are non-split and non-cograph, and show that several elements of the new class are Laplacian integral.

What carries the argument

The new characterization of strictly interval graphs, which supplies the structural description enabling both the linear recognition algorithm and the subsequent definition of the SI-core subclass.

If this is right

  • Membership in the strictly interval class can be decided by a simple linear-time algorithm based on the structural characterization.
  • SI-core graphs supply explicit examples of graphs that remain outside the split and cograph families while still belonging to the strictly interval class.
  • Several SI-core graphs have Laplacian spectra consisting solely of integer eigenvalues.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear recognition procedure could be adapted to decide membership in other related subclasses of chordal graphs.
  • The observed Laplacian integrality in SI-core examples may point to broader connections between interval structure and spectral properties across chordal families.
  • Efficient recognition opens the possibility of using strictly interval graphs as a modeling tool in applications that require both chordal and interval constraints.

Load-bearing premise

The proposed characterization is both correct and complete for the class of strictly interval graphs.

What would settle it

Discovery of a graph that satisfies every condition in the new characterization yet is not strictly interval, or a strictly interval graph that violates one of the characterization conditions.

Figures

Figures reproduced from arXiv: 2512.01175 by Claudia Justel, Lilian Markenzon.

Figure 1
Figure 1. Figure 1: 2-net and bipartite claw graphs 2. Graph Basic Concepts All graphs mentionned in this paper are connected graphs. Basic concepts about chordal graphs are assumed to be known and can be found in Blair and Peyton [2] and Golumbic [6]. Let G = (V, E) be a graph, with |E| = m, |V | = n > 0. The set of neighbors of a vertex v ∈ V is denoted by N(v) = {w ∈ V | {v, w} ∈ E} and its closed neighborhood by N[v] = N(… view at source ↗
Figure 2
Figure 2. Figure 2: Gem and dart graphs. Theorem 3. [3] Let G be a connected graph. G is strictly chordal iff CC(G) is a block graph. Strictly chordal graphs can also be characterized in terms of the structure of their minimal vertex separators. Theorem 4. [14] Let G = (V, E) be a chordal graph. The following state￾ments are equivalent: 1. G is a strictly chordal graph. 2. For any distinct S, S′ ∈ S, S ∩ S ′ = ∅. 3. G is a {g… view at source ↗
Figure 3
Figure 3. Figure 3: A SI-core graph in G(2, 3) [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The min and max SI-core graphs in G(2, 3) For the new class we will show that an element can have many integer Lapla￾cian eigenvalues and even be an integral graph. It is interesting to observe that the class of SI-core graphs is P5-free, it is not a subclass of cographs and it is not a subclass of split graphs. Actually the SI-core graph is a multi-core graph [16]. Two special graphs belonging to G(s, p) … view at source ↗
Figure 5
Figure 5. Figure 5: A SI-core graph in G(3, 10) 9. Answering some questions Question 1: Given n, is it possible to build a SI-core graph with n vertices? Firstly n must be even; with any pair s ≥ 2 and p ≥ 2 such that 2s + 2p = n it is possible to build G ∈ G(s, p). The 2s vertices form the maximal clique of mvss S1 and S2; p vertices are adjacent to S1 and p vertices are adjacent to S2. These vertices can form mutually exclu… view at source ↗
Figure 6
Figure 6. Figure 6: Two SI-core graphs in G(2, 5) If a = s, the solution is immediate. Actually, the value a = s can appear 2(p − 1) times in the spectra of G. Let us consider a ̸= s, that is a > s. • a must be greather or equal s + 2; • a must appear k(a − s − 1) times, k = 1, 2, . . .; • each eigenvalue corresponds to a clique of simplicial vertices of size a − s; the sum of these elements must be less or equal p. Actually,… view at source ↗
read the original 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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces strictly interval graphs as the intersection of strictly chordal and interval graphs. It presents a new characterization of this class that yields a linear-time recognition algorithm, defines the SI-core subclass consisting of non-split non-cograph members, and proves that several SI-core graphs are Laplacian integral.

Significance. A correct characterization would supply an efficient recognition procedure for this graph class and new examples of Laplacian-integral graphs outside split and cograph families. The SI-core construction and integrality results could interest researchers working on chordal-graph algorithms and spectral graph theory, provided the equivalence is fully established.

major comments (2)
  1. [Section 3 (Characterization and Algorithm)] The equivalence between the new characterization and the standard definition (simultaneously strictly chordal and interval) is the load-bearing step for both the linear algorithm and the SI-core claims. The manuscript must supply a complete if-and-only-if argument, including explicit handling of the direction that every graph satisfying the new structural conditions is interval (and vice versa).
  2. [Section 5 (Spectral Properties)] The Laplacian-integrality statements for SI-core graphs rest on the same characterization. The paper shows the property for several concrete members; a general theorem or a clear criterion identifying which SI-core graphs are integral would strengthen the spectral contribution.
minor comments (2)
  1. [Abstract] The abstract states that SI-core graphs are 'non-split and non-cograph' but does not indicate whether this is by definition or by theorem; a clarifying sentence would help readers.
  2. [Section 2 (Preliminaries)] Notation for the new characterization (e.g., the precise forbidden substructures or forbidden induced paths) should be introduced once and used consistently in all subsequent sections and figures.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We respond to each major comment below and describe the revisions we will make.

read point-by-point responses

  1. Referee: [Section 3 (Characterization and Algorithm)] The equivalence between the new characterization and the standard definition (simultaneously strictly chordal and interval) is the load-bearing step for both the linear algorithm and the SI-core claims. The manuscript must supply a complete if-and-only-if argument, including explicit handling of the direction that every graph satisfying the new structural conditions is interval (and vice versa).

    Authors: We agree that the equivalence proof requires explicit treatment of both directions. The manuscript presents the characterization and derives the linear-time algorithm from it, but we will revise Section 3 to include a complete, self-contained if-and-only-if argument. This will explicitly verify that any graph meeting the new structural conditions is an interval graph (and hence strictly interval when combined with the strictly chordal property) and that every strictly interval graph satisfies the new conditions. The expanded proof will address the referee's specific request for clarity on the interval direction. revision: yes

  2. Referee: [Section 5 (Spectral Properties)] The Laplacian-integrality statements for SI-core graphs rest on the same characterization. The paper shows the property for several concrete members; a general theorem or a clear criterion identifying which SI-core graphs are integral would strengthen the spectral contribution.

    Authors: The integrality claims for the listed SI-core graphs rely on the characterization established earlier. While a single general theorem covering all SI-core graphs would be desirable, the structural variety within the class makes a uniform criterion nontrivial. In the revision we will add an explicit structural criterion (based on the forbidden induced subgraphs that define the SI-core) under which integrality holds, together with proofs for two further concrete members. This will strengthen the section while remaining within the scope of the present work; a complete classification is left for future investigation. revision: partial

Circularity Check

0 steps flagged

New characterization of strictly interval graphs relies on standard definitions of chordal and interval graphs without self-referential reductions or fitted inputs.

full rationale

The paper defines strictly interval graphs as the intersection of strictly chordal and interval graphs, then offers a new characterization from which a linear recognition algorithm follows. No equations, parameters, or predictions appear that reduce by construction to the inputs; the equivalence proof (if present) is a standard if-and-only-if argument against external graph classes rather than a self-definition or self-citation chain. Downstream claims about SI-core graphs and Laplacian integrality inherit the same independent foundation. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The abstract relies on standard definitions from graph theory and introduces one new named subclass without additional free parameters or invented entities beyond the class name itself.

axioms (1)
  • domain assumption Strictly interval graphs are exactly the graphs that are simultaneously strictly chordal and interval.
    This is the opening definition used to delimit the class under study.
invented entities (1)
  • SI-core graphs no independent evidence
    purpose: A new subclass of strictly interval graphs required to be non-split and non-cograph.
    Introduced explicitly in the abstract as a fresh subclass whose members are then shown to satisfy the Laplacian-integral property.

pith-pipeline@v0.9.0 · 5581 in / 1240 out tokens · 49350 ms · 2026-05-21T18:51:45.747983+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Abreu, N., Justel, C.M., Markenzon, L.Strictly chordal graphs: Struc- tural properties and integer Laplacian eigenvalues, Linear Algebra and its Applications682(2024) 351-362

    work page 2024

  2. [2]

    R., Liu, J

    Blair, J.R.S., Peyton, B.,An introduction to chordal graphs and clique trees, In: George, J.A., Gilbert, J. R., Liu, J. W. H. (Eds.),Graph theory and sparse matrix computation. Springer Verlag, IMA56, 1-30, 1993

    work page 1993

  3. [3]

    Brandstädt, A., Wagner, P.,Characterising (k,ℓ)-leaf powers, Discrete Applied Mathematics158(2010) 110-122

    work page 2010

  4. [4]

    Cardoso, D.M., Rojo, O.Edge perturbation on graphs with clusters: Ad- jacency, Laplacian and signless Laplacian eigenvalues, Linear Algebra and its Applications512(2017) 113-128

    work page 2017

  5. [5]

    Gilmore, P.C., Hoffman, A.J.,A characterization of comparability graphs and of interval graphs, Canad. J. Math.16(1964) 539-548

    work page 1964

  6. [6]

    Golumbic, M.C.,Algorithmic graph theory and perfect graphs(2nd edi- tion), Academic Press, New York, 2004

    work page 2004

  7. [7]

    Math.124(2002) 67-71

    Golumbic, M.C., Peled, U.N.,Block duplicate graphs and a hierarchy of chordal graphs, Discrete Appl. Math.124(2002) 67-71

    work page 2002

  8. [8]

    Hara, H., Takemura, A.,Boundary cliques, clique trees and perfect se- quences of maximal cliques of a chordal graph, METR 2006-41, Depart- ment of Mathematical Informatics, University of Tokyo, 2006

    work page 2006

  9. [9]

    Harary, F.,A characterization of block graphs, Canad. Math. Bull.6(1) (1963) 1-6

    work page 1963

  10. [10]

    Kennedy, W.,Strictly chordal graphs and phylogenetic roots, Master Thesis, University of Alberta, 2005. 19

    work page 2005

  11. [11]

    Kirkand, S., de Freitas, M. A. A., Del Vecchio, R., Abreu, N.M.M.,Split Nonthreshold Laplacian Integral GraphsLinear and Multilinear Algebra 58(2) (2010) 221-233

    work page 2010

  12. [12]

    (Eds.) Algorithms and Computation (ISAAC 2000)LNCS1969(2000) 539-551

    Lin, G., Kearney, P.E., Jiang, T.Phylogenetick-Root and Steinerk- Root, In Lee, D.T., Teng, S.H. (Eds.) Algorithms and Computation (ISAAC 2000)LNCS1969(2000) 539-551

    work page 2000

  13. [13]

    Markenzon, L., Pereira, P.R.C.,One-phase algorithm for the determi- nation of minimal vertex separators of chordal graphs, Int. Trans. Oper. Res.17(2010) 683-690

    work page 2010

  14. [14]

    Math.196(2015), 135-140

    Markenzon, L., Waga, C.F.E.M.,New results on ptolemaic graphs, Dis- crete Appl. Math.196(2015), 135-140

    work page 2015

  15. [15]

    Markenzon, L., Waga, C. F. E. M.,Strictly interval graphs: charac- terization and linear time recognition, Electr. Notes Discrete Math.52 (2016), 181–188

    work page 2016

  16. [16]

    In: Hoffman, F., Holliday, S., Rosen, Z., Shahrokhi, F., Wierman, J

    Markenzon, L., Paciornik, N.,Multicore Graphs: Characterization and Properties. In: Hoffman, F., Holliday, S., Rosen, Z., Shahrokhi, F., Wierman, J. (eds) Combinatorics, Graph Theory and Computing. SE- ICCGTC 2021. Springer Proceedings in Mathematics & Statistics,448 (2024) Springer

    work page 2021

  17. [17]

    (2025), Entry A000041 in The On-Line Encyclo- pedia of Integer Sequences, https://oeis.org/A000041

    OEIS Foundation Inc. (2025), Entry A000041 in The On-Line Encyclo- pedia of Integer Sequences, https://oeis.org/A000041

    work page 2025

  18. [18]

    Graph The- ory12(1988) 421-428

    Shibata, Y.,On the tree representation of chordal graphs, J. Graph The- ory12(1988) 421-428

    work page 1988

  19. [19]

    So, W., Xi, W.,On the spectrum of an equitable quotient matrix, Linear Algebra Appl.577(2019), 21-40

    You, L., Yang, M., W. So, W., Xi, W.,On the spectrum of an equitable quotient matrix, Linear Algebra Appl.577(2019), 21-40. 20

    work page 2019