EUVIMEDEUVIMED entdecken
Crossref

On the edge reconstruction of the characteristic and permanental polynomials of a simple graph

Jingyuan Zhang, Xian'an Jin, Weigen Yan, Qinghai Liu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →