On the edge reconstruction of the characteristic and permanental polynomials of a simple graph
Discrete Mathematics · 2024-09 · 347 (9) · 114063
DOI: 10.1016/j.disc.2024.114063 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics, 2024-09. Verfasst von Jingyuan Zhang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 25 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
As a variant of the Ulam's vertex reconstruction conjecture and the Harary's edge reconstruction conjecture, Cvetkovi\'c and Schwenk posed independently the following problem: Can the characteristic polynomial of a simple graph $G$ with vertex set $V$ be reconstructed from the characteristic polynomials of all subgraphs in $\{G-v|v\in V\}$ for $|V|\geq 3$? This problem is still open. A natural problem is: Can the characteristic polynomial of a simple graph $G$ with edge set $E$ be reconstructed from the characteristic polynomials of all subgraphs in $\{G-e|e\in E\}$? In this paper, we prove that if $|V|\neq |E|$, then the characteristic polynomial of $G$ can be reconstructed from the characteristic polynomials of all subgraphs in $\{G-uv, G-u-v|uv\in E\}$, and the similar result holds for the permanental polynomial of $G$. We also prove that the Laplacian (resp. signless Laplacian) characteristic polynomial of $G$ can be reconstructed from the Laplacian (resp. signless Laplacian) characteristic polynomials of all subgraphs in $\{G-e|e\in E\}$ (resp. if $|V|\neq |E|$).
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Zhang, J., Jin, X., Yan, W., & Liu, Q. (2024). On the edge reconstruction of the characteristic and permanental polynomials of a simple graph. Discrete Mathematics, 347(9), 114063. https://doi.org/10.1016/j.disc.2024.114063
Vancouver
Zhang J, Jin X, Yan W, Liu Q. On the edge reconstruction of the characteristic and permanental polynomials of a simple graph. Discrete Mathematics. 2024;347(9):114063. doi:10.1016/j.disc.2024.114063
BibTeX
@article{Zhang2024,
author = {Zhang, Jingyuan and Jin, Xian'an and Yan, Weigen and Liu, Qinghai},
title = {On the edge reconstruction of the characteristic and permanental polynomials of a simple graph},
journal = {Discrete Mathematics},
year = {2024},
volume = {347},
number = {9},
pages = {114063},
doi = {10.1016/j.disc.2024.114063}
}
EUVIMED