一类半折叠n-立方体图的度量维数
The Metric Dimension of a Class of Halved Folded n-Cube
DOI: 10.12677/aam.2025.147346, PDF,    科研立项经费支持
作者: 田 毅*, 王 魏, 任子涵, 杨斯媛, 段天宇, 王 奥, 张城源, 蔡嘉怡：河北金融学院统计与数据科学学院，河北 保定
关键词: 度量维数；半折叠n-立方体图；距离正则图；Metric Dimension； Halved Folded n-Cube； Distance-Regular Graph
摘要: 图的度量维数在通信网络中的有效寻址系统、标尺模型和雷达脉冲码等方面都有重要的应用。本文关于n = 4d (d ≥ 3)的半折叠n-立方体图，通过构造解析集的方式证明了n − 1是该类图的度量维数的上界。最后，将该上界与Babai的上界进行了对比，发现本文所得上界更优。
Abstract: The metric dimension of the graph has important applications in the effective addressing system, scale model and radar pulse code in communication networks. In this paper, for the halved folded n-cube with n = 4d (d ≥ 3), we prove that n − 1 is an upper bound on the metric dimension of this graph by constructing a resolving set. Finally, we compare the upper bound with Babai’s upper bounds, and obtain that the upper bound above is better.
文章引用：田毅, 王魏, 任子涵, 杨斯媛, 段天宇, 王奥, 张城源, 蔡嘉怡. 一类半折叠n-立方体图的度量维数[J]. 应用数学进展, 2025, 14(7): 54-58. https://doi.org/10.12677/aam.2025.147346

参考文献

[1] Slater, P.J. (1975) Leaves of Trees. Congressus Numerantium, 14, 549-559.
[2] Khuller, S., Raghavachari, B. and Rosenfeld, A. (1996) Landmarks in Graphs. Discrete Applied Mathematics, 70, 217-229. [Google Scholar] [CrossRef] 
[3] Babai, L. (1980) On the Complexity of Canonical Labeling of Strongly Regular Graphs. SIAM Journal on Computing, 9, 212-216. [Google Scholar] [CrossRef] 
[4] Babai, L. (1981) On the Order of Uniprimitive Permutation Groups. The Annals of Mathematics, 113, 553-568. [Google Scholar] [CrossRef] 
[5] Chvátal, V. (1983) Mastermind. Combinatorica, 3, 325-329. [Google Scholar] [CrossRef] 
[6] Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., et al. (2007) On the Metric Dimension of Cartesian Products of Graphs. SIAM Journal on Discrete Mathematics, 21, 423-441. [Google Scholar] [CrossRef] 
[7] Bailey, R.F. and Meagher, K. (2012) On the Metric Dimension of Grassmann Graphs. Discrete Mathematics & Theoretical Computer Science, 13, 97-104. [Google Scholar] [CrossRef] 
[8] Bailey, R.F. and Cameron, P.J. (2011) Base Size, Metric Dimension and Other Invariants of Groups and Graphs. Bulletin of the London Mathematical Society, 43, 209-242. [Google Scholar] [CrossRef] 
[9] Bailey, R.F., Cáceres, J., Garijo, D., González, A., Márquez, A., Meagher, K. and Puertas M.L. (2013) Resolving Sets for Johnson and Kneser Graphs. European Journal of Combinatorics, 34, 736-751.
[10] Feng, M. and Wang, K. (2012) On the Metric Dimension of Bilinear Forms Graphs. Discrete Mathematics, 312, 1266-1268. [Google Scholar] [CrossRef] 
[11] Guo, J., Wang, K. and Li, F. (2013) Metric Dimension of Some Distance-Regular Graphs. Journal of Combinatorial Optimization, 26, 190-197. [Google Scholar] [CrossRef] 
[12] Guo, J., Wang, K. and Li, F. (2013) Metric Dimension of Symplectic Dual Polar Graphs and Symmetric Bilinear Forms Graphs. Discrete Mathematics, 313, 186-188. [Google Scholar] [CrossRef] 
[13] Lindström, B. (1964) On a Combinatory Detection Problem. I. A Magyar Tudományos Akadémia. Matematikai Kutató Intézetének Közleménye, 9, 195-207.
[14] Hertz, A. (2020) An IP-Based Swapping Algorithm for the Metric Dimension and Minimal Doubly Resolving Set Problems in Hypercubes. Optimization Letters, 14, 355-367. [Google Scholar] [CrossRef] 
[15] Zhang, Y., Hou, L., Hou, B., Wu, W., Du, D. and Gao, S. (2020) On the Metric Dimension of the Folded N-Cube. Optimization Letters, 14, 249-257. [Google Scholar] [CrossRef] 
[16] Simó, E. and Yebra, J.L.A. (1997) The Vulnerability of the Diameter of Folded N-Cubes. Discrete Mathematics, 174, 317-322. [Google Scholar] [CrossRef] 
[17] Chartrand, G., Eroh, L., Johnson, M.A. and Oellermann, O.R. (2000) Resolvability in Graphs and the Metric Dimension of a Graph. Discrete Applied Mathematics, 105, 99-113. [Google Scholar] [CrossRef] 
[18] Bailey, R.F. (2015) The Metric Dimension of Small Distance-Regular and Strongly Regular Graphs. The Australasian Journal of Combinatorics, 62, 18-34.
[19] Brouwer, A.E., Cohen, A.M. and Neumaier, A. (1989) Distance-Regular Graphs. Springer-Verlag. [Google Scholar] [CrossRef] 
[20] Hernando, C., Mora, M., Pelayo, I.M., Seara, C. and Wood, D.R. (2010) Extremal Graph Theory for Metric Dimension and Diameter. The Electronic Journal of Combinatorics, 17, 1-28. [Google Scholar] [CrossRef] 

为你推荐