冠图 P n ∘ P m 的两种度结合边重构数
Two Kinds of Degree Associated Edge Reconstruction Numbers of Corona Graph P n ∘ P m
摘要: 本文研究了冠图 P n ∘ P m 的重构性及其两种度结合边重构数。通过分析冠图 P n ∘ P m 边主子图的结构，确定冠图 P n ∘ P m 所有可能的扩展及其度结合边主子图；利用图同构的必要条件和充分条件，探索冠图 P n ∘ P m 扩展的度结合边主子图与冠图 P n ∘ P m 度结合边主子图的同构情况；结合上下界逼近法证明了冠图 P n ∘ P m 的可重构性，确定了它的两种度结合边重构数。
Abstract: The investigation covers the reconfigurability of the corona graph P n ∘ P m and explores two kinds of degree associated edge reconstruction numbers. By analyzing the structure of the edge-card of the corona graph P n ∘ P m , determine all possible extensions of the corona graph P n ∘ P m and its degree associated edge-card. Explore the isomorphism between the degree associated edge-card of the corona graph P n ∘ P m extension and the corona graph P n ∘ P m by utilizing the necessary and sufficient conditions of graph isomorphism. Using the upper and lower bounds approximation method, the reconfigurability of the corona graph P n ∘ P m is proved, and its two kinds of degree associated edge reconstruction numbers are identified.
文章引用：杨盈意, 李鹏, 薛心怡. 冠图 P n ∘ P m 的两种度结合边重构数[J]. 应用数学进展, 2025, 14(4): 166-176. https://doi.org/10.12677/aam.2025.144149

参考文献

[1] Ulam, S.M. (1960) A Collection of Mathematical Problems. Interscience Publishers, 20.
[2] Kelly, P.J. (1942) On Isometric Transformations. University of Wisconsin-Madison.
[3] Kelly, P. (1957) A Congruence Theorem for Trees. Pacific Journal of Mathematics, 7, 961-968. [Google Scholar] [CrossRef] 
[4] Harary, F. (1964) On the Reconstruction of a Graph from a Collection of Subgraphs. In: Ed., Theory of Graphs and Its Applications (Proc. Sympos. Smolenice, 1963), Publishing House Czechoslovak Academy of Sciences, 47-52.
[5] Monikandan, S. and Raj, S.S. (2012) Degree Associated Edge Reconstruction Number. In: Arumugam, S. and Smyth, W.F., Eds., Lecture Notes in Computer Science, Springer, 100-109. [Google Scholar] [CrossRef] 
[6] Devi, P.A. and Monikandan, S. (2015) Degree Associated Edge Reconstruction Number of Graphs with Regular Pruned Graph. Electronic Journal of Graph Theory and Applications, 3, 146-161. [Google Scholar] [CrossRef] 
[7] 黄陈辰, 马美杰. 一类冠图的2种度结合边重构数[J]. 浙江师范大学学报(自然科学版), 2016, 39(3): 263-267.
[8] Priya, P.D. and Monikandan, S. (2021) Stronger Reconstruction of Distance-Hereditary Graphs. Journal of Applied and Engineering Mathematics, 11, 25-29.
[9] Anu, A. and Monikandan, S. (2019) Nearly All Biregular Graphs Have Degree Associated Edge Reconstruction Number at Most Three. Ars Combinatoria, 147, 263-279.
[10] Priya, P.D. and Monikandan, S. (2021) Reconstruction of 2-Connected Parity Graphs. Australasian Journal of Combinatorics, 80, 167-177.
[11] Devi, P.A. and Monikandan, S. (2022) Degree Associated Edge Reconstruction Parameters of Strong Double Brooms. Journal of Automata, Languages and Combinatorics, 27, 259-269.
[12] Spinoza, H. and West, D.B. (2020) Reconstruction of Graphs from the Deck of K-Vertex Induced Subgraphs. Journal of Graph Theory, 90, 497-522.
[13] Garamvölgyi, D. and Jordán, T. (2021) Graph Reconstruction from Unlabeled Edge Lengths. Discrete & Computational Geometry, 66, 344-385. [Google Scholar] [CrossRef] 
[14] Hosaka, T. (2022) The Reconstruction Conjecture for Finite Simple Graphs and Associated Directed Graphs. Discrete Mathematics, 345, Article 112893. [Google Scholar] [CrossRef] 
[15] Kapuhennayake, K.M.P.G.S.C., Perera, A.C.G., Dhananjaya, K.D.E. and Perera, A.A.I. (2022) Reconstruction of Helm Graph and Web Graph. Journal of Science, 13, 31-39. [Google Scholar] [CrossRef] 
[16] Clifton, A., Liu, X., Mahmoud, R. and Shantanam, A. (2024) Reconstruction and Edge Reconstruction of Triangle-Free Graphs. Discrete Mathematics, 347, Article 113753. [Google Scholar] [CrossRef] 
[17] Bouritsas, G., Frasca, F., Zafeiriou, S. and Bronstein, M.M. (2023) Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45, 657-668. [Google Scholar] [CrossRef] [PubMed]
[18] Hemaspaandra, E., Hemaspaandra, L.A., Spakowski, H. and Watanabe, O. (2020) The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. Computational Complexity, 29, Article No. 7. [Google Scholar] [CrossRef] 
[19] Singh, G.P., Borah, A. and Ray, S. (2020) A Review Paper on Corona Product of Graphs. Advances and Applications in Mathematical Sciences, 19, 1047-1054.
[20] West, D.B. (2001) Introduction to Graph Theory. Prentice Hall.
[21] Ren, J. and Li, T. (2024) Graph Isomorphism—Characterization and Efficient Algorithms. High-Confidence Computing, 4, Article 100224. [Google Scholar] [CrossRef] 

为你推荐