Skip to content
DraconiticResearch
Search Sources API
194,161 studies31 sourcesUpdated 43 min ago
PreprintCC BY-NC-ND 4.0HAL

Some advances on stretching operations applied to cliques of edge intersection graphs of paths in trees

  • Mariana Escalante
  • Victoria Kaial
  • Annegret K Wagler
Open at sourcePDFCite

Abstract

Given a set P of paths over a graph (called the host graph), its edge intersection graph is a graph each of whose vertices corresponds to a path in P and where two vertices are connected if and only if the paths they correspond to share at least one edge. Restricting the host graph to trees gives the class of edge intersection graphs of paths in trees (EPT graphs), first introduced in [Golumbic, Jamison (1985) and Monma, Wei (1986)]. EPT graphs are a natural generalization of interval graphs but, in contrast to the latter, characterizing EPT graphs by minimal forbidden induced subgraphs remains an open problem. In this contribution, we prove that certain stretching operations preserve the property of not being EPT. We further introduce new families of minimal non-EPT graphs, constructed from known chordal minimal non-EPT graphs through the presented stretching operations, and study general necessary conditions for these to preserve the minimality when applied to minimal non-EPT graphs.

Related

  1. Normal approximation for subgraph counts in random intersection graphs: the case of cliques
    Katarzyna Rybarczyk, Grzegorz Serafin
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Counting t-wise L-intersecting cliques with prescribed intersection sizes
    Yiyan Zhan, Yichen Wang, Mei Lu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Artinian reduction applied to the Largest Intersection Problem
    Yuxin Lin
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. Cognitive Warfare, Hybrid Pressure, and Sovereign Resilience: An Operations Research Framework Applied to the Iranian Case (2017--2026)
    Rahimeh Neamatian Monemi, Shahin Gelareh, Nelson Maculan
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Turán number of three disjoint cliques of arbitrary sizes
    Alexandr Kostochka, Dadong Peng, Zimu Xiang +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{escalante2026some,
  title = {{Some advances on stretching operations applied to cliques of edge intersection graphs of paths in trees}},
  author = {Mariana Escalante and Victoria Kaial and Annegret K Wagler},
  howpublished = {HAL},
  year = {2026},
  month = sep,
  url = {https://hal.science/hal-05752060v1},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - Some advances on stretching operations applied to cliques of edge intersection graphs of paths in trees
AU  - Mariana Escalante
AU  - Victoria Kaial
AU  - Annegret K Wagler
PY  - 2026
DA  - 2026/09/16
PB  - HAL
UR  - https://hal.science/hal-05752060v1
AB  - Given a set P of paths over a graph (called the host graph), its edge intersection graph is a graph each of whose vertices corresponds to a path in P and where two vertices are connected if and only if the paths they correspond to share at least one edge. Restricting the host graph to trees gives the class of edge intersection graphs of paths in trees (EPT graphs), first introduced in [Golumbic, Jamison (1985) and Monma, Wei (1986)]. EPT graphs are a natural generalization of interval graphs but, in contrast to the latter, characterizing EPT graphs by minimal forbidden induced subgraphs remains an open problem. In this contribution, we prove that certain stretching operations preserve the property of not being EPT. We further introduce new families of minimal non-EPT graphs, constructed from known chordal minimal non-EPT graphs through the presented stretching operations, and study general necessary conditions for these to preserve the minimality when applied to minimal non-EPT graphs.
ER  -