|
|
Pure Mathematics 2025
半折叠n-立方体图的度量维数的上界
|
Abstract:
令图
是简单的无向连通图，图
的解析集
是指对于任意两个不同点
，总存在
使得
。图
的度量维数是所有解析集基数的最小值。本文针对直径
的半折叠n-立方体图，在
时构造了一个解析集，从而证明了
是该图度量维数的上界。最后，将所得上界与Babai的上界进行对比，发现所得上界在一定情况下更优。
Let
be a simple, undirected, connected graph. A resolving set
for graph
satisfies for any two vertices
| [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. https://doi.org/10.1016/0166-218x(95)00106-2 |
| [3] | Babai, L. (1980) On the Complexity of Canonical Labeling of Strongly Regular Graphs. SIAM Journal on Computing, 9, 212-216. https://doi.org/10.1137/0209018 |
| [4] | Babai, L. (1981) On the Order of Uniprimitive Permutation Groups. The Annals of Mathematics, 113, 553-568. https://doi.org/10.2307/2006997 |
| [5] | Chvátal, V. (1983) Mastermind. Combinatorica, 3, 325-329. https://doi.org/10.1007/bf02579188 |
| [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. https://doi.org/10.1137/050641867 |
| [7] | Bailey, R.F. and Meagher, K. (2012) On the Metric Dimension of Grassmann Graphs. Discrete Mathematics & Theoretical Computer Science, 13, 97-104. https://doi.org/10.46298/dmtcs.532 |
| [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. https://doi.org/10.1112/blms/bdq096 |
| [9] | Bailey, R.F., Cáceres, J., Garijo, D., González, A., Márquez, A., Meagher, K., et al. (2013) Resolving Sets for Johnson and Kneser Graphs. European Journal of Combinatorics, 34, 736-751. https://doi.org/10.1016/j.ejc.2012.10.008 |
| [10] | Feng, M. and Wang, K. (2012) On the Metric Dimension of Bilinear Forms Graphs. Discrete Mathematics, 312, 1266-1268. https://doi.org/10.1016/j.disc.2011.11.020 |
| [11] | Guo, J., Wang, K. and Li, F. (2012) Metric Dimension of Some Distance-Regular Graphs. Journal of Combinatorial Optimization, 26, 190-197. https://doi.org/10.1007/s10878-012-9459-x |
| [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. https://doi.org/10.1016/j.disc.2012.09.023 |
| [13] | Lindström, B. (1964) On a Combinatory Detection Problem. A Magyar Tudományos Akadémia. Matematikai Kutató Intézetének Közleményei, 9, 195-207. |
| [14] | Hertz, A. (2017) An Ip-Based Swapping Algorithm for the Metric Dimension and Minimal Doubly Resolving Set Problems in Hypercubes. Optimization Letters, 14, 355-367. https://doi.org/10.1007/s11590-017-1184-z |
| [15] | Zhang, Y., Hou, L., Hou, B., Wu, W., Du, D. and Gao, S. (2019) On the Metric Dimension of the Folded N-Cube. Optimization Letters, 14, 249-257. https://doi.org/10.1007/s11590-019-01476-z |
| [16] | Kelenc, A., Masa Toshi, A.T., Škrekovski, R. and Yero, I.G. (2022) On Metric Dimensions of Hypercubes. Ars Mathematica Contemporanea, 23, #P2.08. https://doi.org/10.26493/1855-3974.2568.55c |
| [17] | 田毅, 王魏, 任子涵, 等. 一类半折叠n-立方体图的度量维数[J]. 应用数学进展, 2025, 14(7): 54-58. |
| [18] | Simó, E. and Yebra, J.L.A. (1997) The Vulnerability of the Diameter of Folded N-Cubes. Discrete Mathematics, 174, 317-322. https://doi.org/10.1016/s0012-365x(97)80334-2 |
| [19] | 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. https://doi.org/10.1016/s0166-218x(00)00198-0 |
| [20] | Bailey, R.F. (2015) The Metric Dimension of Small Distance-Regular and Strongly Regular Graphs. The Australasian Journal of Combinatorics, 62, 18-34. |
| [21] | Brouwer, A.E., Cohen, A.M. and Neumaier, A. (1989) Distance-Regular Graphs. Springer-Verlag. |
