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

Adjacency-degree algebras and spectral determination of graphs

  • Zhipeng Lu
  • Pengxiang Li
Open at sourcePDFDOICite

Abstract

Let G be a graph with adjacency matrix A and degree matrix D. Applying A and D repeatedly to the all-ones vector produces a space MG of functions on the vertices, and these functions are constant on the orbits of the automorphism group. We call G AD-observable if MG contains the indicator vector of every orbit, and AD-separable if the functions in MG separate the orbits. Forests are AD-observable, by McKay's leaf-pruning argument. Our main result is that for every cograph, MG is spanned by the indicator vectors of the cells of the stable partition of color refinement. Hence a cograph is AD-observable, or equivalently AD-separable, exactly when color refinement finds its orbits, and we describe these cographs by their cotrees. We also show that two cographs with the same number of vertices and the same homomorphism counts from all caterpillars have the same counts from all trees. The main result does not extend to distance-hereditary graphs: we give two such graphs on nine vertices that are AD-separable but not AD-observable.

Related

  1. Degree Adjacency Diametrical Matrix of Graphs Spectral Properties and Energy Bounds
    Celine Prabha S, Dhivviyanandam I
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Punctured adjacency-degree algebras of Cartesian products
    Zhipeng Lu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A Unified Spectral Framework for Weighted Adjacency-Degree Matrices of Dendrimer and Bethe Trees
    Metrose Metsidik
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Connected graphs with minimum adjacency spectral gap
    Lele Liu, Michael Tait, Yi Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Extremal Graphs with Prescribed Parameters for the Spectral Radius of Weighted Adjacency Matrices with Property P∗
    Swathi Shetty, B. R. Rakshith, Sayinath Udupa N. V
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lu2026adjacencydegree,
  title = {{Adjacency-degree algebras and spectral determination of graphs}},
  author = {Zhipeng Lu and Pengxiang Li},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2607.21494},
  eprint = {2607.21494},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.21494},
}
RIS
TY  - UNPB
TI  - Adjacency-degree algebras and spectral determination of graphs
AU  - Zhipeng Lu
AU  - Pengxiang Li
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2607.21494
UR  - https://arxiv.org/abs/2607.21494
AB  - Let G be a graph with adjacency matrix A and degree matrix D. Applying A and D repeatedly to the all-ones vector produces a space M_G of functions on the vertices, and these functions are constant on the orbits of the automorphism group. We call G AD-observable if M_G contains the indicator vector of every orbit, and AD-separable if the functions in M_G separate the orbits. Forests are AD-observable, by McKay's leaf-pruning argument. Our main result is that for every cograph, M_G is spanned by the indicator vectors of the cells of the stable partition of color refinement. Hence a cograph is AD-observable, or equivalently AD-separable, exactly when color refinement finds its orbits, and we describe these cographs by their cotrees. We also show that two cographs with the same number of vertices and the same homomorphism counts from all caterpillars have the same counts from all trees. The main result does not extend to distance-hereditary graphs: we give two such graphs on nine vertices that are AD-separable but not AD-observable.
ER  -