Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 38 min ago
PreprintarXiv licencearXiv

One-Vertex Lifts of Looped Circle Graphs: Obstructions and Interlace Polynomials

  • Qingying Deng
  • Yexiang Yan
Open at sourcePDFDOICite

Abstract

Let M be the adjacency matrix of a looped simple graph over ๐”ฝ2 and let t=diag M. We study the one-vertex lift with adjacency matrix (M+ttT&t tT&0). A looped circle graph is called stable if its lift is a circle graph. We prove that stability is equivalent to the existence of a pseudo-orientable bouquet realizing the given looped circle graph. We then obtain a finite excluded toggle-minor characterization by applying two rooted constructions to the known excluded pivot-minors for circle graphs. An exact enumeration yields $22$ minimal toggle-equivalence classes: one of order $5$, twelve of order $6$, and nine of order $7$. The enumeration is accompanied by independently checkable linear-algebra and minor certificates. Finally, we prove q(Gโ€ ;y)=yq(G;y) for the vertex-nullity interlace polynomial of every looped simple graph, and derive quasi-tree counting and real determinant formulas.

Related

  1. Hyperbolicity and obstructions to PL actions of the circle
    Leonardo Dinamarca, Maximiliano Escayola, Sang-hyun Kim +1
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryDynamical systemsarXiv
  2. Spectral moments and characteristic polynomials of vertex expansion hypergraphs of graphs
    Ge Lin, Changjiang Bu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Sobolev Orthogonal Polynomials on the unit circle with varying inner product
    Sourav Majumder, A. Swaminathan
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. Same path, different walk: a mechanistic comparison of looped and stacked transformer encoders on 12-lead ECG
    Pawel Olszowiec, Michal Byra, Grzegorz Gruszczynski +2
    arXivPreprintarXiv licenceFull textDynamical systemsarXiv
  5. Rotate the Loop: Blockwise Conformality for Looped Transformers
    Alexey Zemtsov, Albina Klepach, Vadim Lomshakov +5
    arXivPreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{deng2026onevertex,
  title = {{One-Vertex Lifts of Looped Circle Graphs: Obstructions and Interlace Polynomials}},
  author = {Qingying Deng and Yexiang Yan},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05961},
  eprint = {2611.05961},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05961},
}
RIS
TY  - UNPB
TI  - One-Vertex Lifts of Looped Circle Graphs: Obstructions and Interlace Polynomials
AU  - Qingying Deng
AU  - Yexiang Yan
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.05961
UR  - https://arxiv.org/abs/2611.05961
AB  - Let M be the adjacency matrix of a looped simple graph over ๐”ฝ_2 and let t=diag M. We study the one-vertex lift with adjacency matrix (M+tt^T&t t^T&0). A looped circle graph is called stable if its lift is a circle graph. We prove that stability is equivalent to the existence of a pseudo-orientable bouquet realizing the given looped circle graph. We then obtain a finite excluded toggle-minor characterization by applying two rooted constructions to the known excluded pivot-minors for circle graphs. An exact enumeration yields $22$ minimal toggle-equivalence classes: one of order $5$, twelve of order $6$, and nine of order $7$. The enumeration is accompanied by independently checkable linear-algebra and minor certificates. Finally, we prove q(G^โ€ ;y)=yq(G;y) for the vertex-nullity interlace polynomial of every looped simple graph, and derive quasi-tree counting and real determinant formulas.
ER  -