Graphs with Long Pseudosimilarity Chains under Consecutive Vertex Deletions

Abstract

Pseudosimilar vertices are vertices in distinct automorphism orbits whose deletions produce isomorphic graphs. Classical work has studied the existence, group-theoretic origin, and construction of large sets of such vertices. We ask a different recursive question: how long can one repeatedly delete a vertex that is pseudosimilar at the moment of deletion? We define the pseudosimilarity depth of a graph and construct connected graphs in which this process continues through all but a sublinear number of vertices. A two-clock construction gives a square-root deficit uniformly in the order, while a Chinese-remainder construction with many cyclic clocks yields an infinite family of asymmetric graphs with only a polylogarithmic number of vertices left outside the active chain. The mechanism realizes pseudosimilarity by breaking a long hidden automorphism orbit and enlarging the break one vertex at a time. Thus pseudosimilarity can persist through an asymptotically full sequence of vertex deletions, even though every graph encountered in the main construction is asymmetric.

Multi-Way Expansion, Laplacian Gaps, and Imprimitivity in Vertex-Transitive Graphs
Zejun Huang, Chenxi Yang
HAL11 Sep 2026PreprintLicence Ouverte 2.0Full textGeneral mathematicsHAL
Enumeration of small vertex-transitive directed strongly regular graphs
A. E. Brouwer, Š. Gyürki
arXiv16 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Non-isomorphic graphs have distinct vertex-Ramsey classes
Maria Axenovich, Patrick Schmitteckert
arXiv2 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Vertex-transitive strongly regular graphs in the switching class of doubly transitive two-graphs
Robert F. Bailey, Gábor P. Nagy, Valentino Smaldore
arXiv31 Aug 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs
Joel Bassil
arXiv6 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{ivanov2026graphs,
  title = {{Graphs with Long Pseudosimilarity Chains under Consecutive Vertex Deletions}},
  author = {Sergey Ivanov},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.00394},
  eprint = {2609.00394},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.00394},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Graphs with Long Pseudosimilarity Chains under Consecutive Vertex Deletions
AU  - Sergey Ivanov
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.00394
UR  - https://arxiv.org/abs/2609.00394
AB  - Pseudosimilar vertices are vertices in distinct automorphism orbits whose deletions produce isomorphic graphs. Classical work has studied the existence, group-theoretic origin, and construction of large sets of such vertices. We ask a different recursive question: how long can one repeatedly delete a vertex that is pseudosimilar at the moment of deletion? We define the pseudosimilarity depth of a graph and construct connected graphs in which this process continues through all but a sublinear number of vertices. A two-clock construction gives a square-root deficit uniformly in the order, while a Chinese-remainder construction with many cyclic clocks yields an infinite family of asymmetric graphs with only a polylogarithmic number of vertices left outside the active chain. The mechanism realizes pseudosimilarity by breaking a long hidden automorphism orbit and enlarging the break one vertex at a time. Thus pseudosimilarity can persist through an asymptotically full sequence of vertex deletions, even though every graph encountered in the main construction is asymmetric.
ER  -

Abstract

Related

Cite