Publications and Preprints by Topics

Tilings

  1. (With Zhujun Zhang) On the Undecidability of Tiling the 3-dimensional Space with a Set of 3 Polycubes. (in Chinese) arXiv:2508.00192
  2. (With Zhujun Zhang) Undecidability of Translational Tiling of the Plane with Four Tiles. arXiv:2506.19295
  3. (With Zhujun Zhang) Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes. arXiv:2506.12726
  4. (With Zhujun Zhang) Translational Aperiodic Sets of 7 Polyominoes. arXiv:2412.17382
    ChinaXiv:202412.00304
  5. (With Zhujun Zhang) Undecidability of Translational Tiling with Three Tiles. arXiv:2412.10646
  6. (With Zhujun Zhang) Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes. arXiv:2409.00846
    Journal version: SCIENCE CHINA Mathematics. 68(9)(2025), 2173-2188. https://doi.org/10.1007/s11425-024-2365-2
    《中国科学：数学》公众号发布此论文的新闻稿：密铺的非周期性与不可判定性
  7. (With Zhujun Zhang) Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes. arXiv:2408.02196
    Journal version: Proceedings of the AMS. 153(2025), 3541-3554. https://doi.org/10.1090/proc/17186
  8. (With Zhujun Zhang) NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles. arXiv:2405.01017
  9. (With Zhujun Zhang) Undecidability of tiling the plane with a fixed number of Wang bars. arXiv:2404.04504
    Journal version: to appear in Journal of the Operations Research Society of China. https://doi.org/10.1007/s40305-025-00666-0
  10. (With Zhujun Zhang) A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of 8 polyominoes. arXiv:2403.13472
    Journal version: Translational tiling with 8 polyominoes is undecidable. to appear in Discrete & Computational Geometry. https://doi.org/10.1007/s00454-024-00706-1
  11. On the Undecidability of Tiling the plane with a Set of 9 Polyominoes (in Chinese). SCIENTIA SINICA Mathematica.（《中国科学：数学》中文版） 55(6)(2025), 1113-1122. https://doi.org/10.1360/SSM-2024-0035
  12. Wang Tiles: Connectivity when Tiling a Plane. Thai Journal of Mathematics. 21(4)(2023), 991–1009. https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1561 https://thaijmath.com/index.php/thaijmath/article/view/1561
  13. Tiling the Plane with a Set of Ten Polyominoes. International Journal of Computational Geometry & Applications. 33(03n04)(2023), 55-64. https://doi.org/10.1142/S0218195923500012

Combinatorial Game Thoery

  1. (With Zhujun Zhang) Atropos-k is PSPACE-complete. arXiv:2403.01662
    Journal version: PSPACE-completeness of k-Atropos. Discrete Applied Mathematics. 368(2025), 190-198. https://doi.org/10.1016/j.dam.2025.03.010

Motion Planning on Graphs/Puzzles

  1. (With Zhujun Zhang) 1-PushingMachine is PSPACE-complete. Journal of Information Processing. 33(12)(2025), 1071-1076. https://doi.org/10.2197/ipsjjip.33.1071 Special Issue of the 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2024)
  2. (With Zhujun Zhang) Modify is PSPACE-complete. Journal of Information Processing. 33(11)(2025), 801-803. https://doi.org/10.2197/ipsjjip.33.801
  3. (With Zhujun Zhang) Friends-and-strangers is PSPACE-complete. arXiv:2402.03685
    Journal version: Information Processing Letters. 190(2025), 106573. https://doi.org/10.1016/j.ipl.2025.106573
  4. On the Computational Complexity of Pushing Machine. In: Akiyama, J., Ito, H., Sakai, T. (eds) Discrete and Computational Geometry, Graphs, and Games. JCDCGGG 2022. Lecture Notes in Computer Science, vol 14364 (2026), Springer, Cham. 415-425.
    https://doi.org/10.1007/978-3-032-00281-5_25
  5. On the Complexity of Motion Planning Problem of a Forklift. Thai Journal of Mathematics. 21(4)(2023), 785-798. https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1545 https://thaijmath.com/index.php/thaijmath/article/view/1545
  6. On the Complexity of Jelly-no-Puzzle. In: Akiyama J., Marcelo R.M., Ruiz MJ.P., Uno Y. (eds) Discrete and Computational Geometry, Graphs, and Games. JCDCGGG 2018. Lecture Notes in Computer Science, vol 13034 (2021), Springer, Cham. 165-174. https://doi.org/10.1007/978-3-030-90048-9_13
  7. Hanano Puzzle is NP-hard. Information Processing Letters. 145 (2019), 6-10. (With Ziwen Liu)
  8. The Non-Deterministic Constraint Logic and Its Applications in Computational Complexity. Computer Science and Application. 7(5) (2017), 407-413. (With Ziwen Liu)
  9. SNOWMAN is PSPACE-complete. Theoretical Computer Science. 677 (2017) 31-40. (With Weihua He and Ziwen Liu)
  10. Sliding puzzles and rotating puzzles on graphs , Discrete Mathematics. 311 (2011), 1290–1294 .

Misc. (Graph Curvature, Spectral Graph Theory, etc.)

  1. The Spectral Distribution of Random Mixed Graphs. Axioms. 11(3) (2022), 126. https://doi.org/10.3390/axioms11030126 (With Yue Guan, Bo Cheng, Minfeng Chen, Meili Liang, Jianxi Liu, Jinxun Wang and Li Zeng)
  2. The linear k-arboricity of digraphs. AIMS Mathematics. 7(3) (2022), 4137-4152. https://doi.org/10.3934/math.2022229 (With Xiaoling Zhou and Weihua He)
  3. The linear k-arboricity of symmetric directed trees. AIMS Mathematics. 7(2) (2022), 1603-1614. https://doi.org/10.3934/math.2022093 (With Xiaoling Zhou and Weihua He)
  4. Ricci-flat graphs with girth four. Acta Mathematica Sinica, English Series. 37(11) (2021), 1679-1691. https://doi.org/10.1007/s10114-021-9546-y (With Weihua He, Jun Luo, Wei Yuan and Hui Chun Zhang)
  5. On the Upper Bound of Modular Chromatic Number of Graphs. Advances in Applied Mathematics. 9(8) (2020), 1309-1312.
  6. Unified extremal results of topological indices and spectral invariants of graphs. Discrete Applied Mathematics. 271 (2019), 218-232. (With Yuedan Yao, Muhuo Liu, Francesco Belardo)

Math Education

  1. Teaching Design Practice of Virtual 3-Dimensional Software in Mathematical Education—A Case Study of vZome. to appear in Creative Education Studies. 14(2)(2026). (With Ze Long)
  2. A Brief Discussion on L'Hôpital's Rule and Its Application in Solving Problems in High School Mathematics. Pure Mathematics. 15(12)(2025), 41-47. (With Guangjie Li and Junwei Wang)
  3. Practice of Ideological and Political Teaching in “Mathematical Statistics” Course. Advances in Education. 13(11) (2023), 8679-8683.
  4. Teaching Advanced Mathematics with the New Technological Achievements of China—Using the Tianwen-1 Spacecraft as an Example. Advances in Education. 11(1) (2021), 68-72.

Connectivity of Graphs/Combinatorial Networks

  1. Connectivity of lexicographic product and direct product of graphs, Ars Combinatoria. 111 (2013), 3-12. (With Jun-Ming Xu)
  2. Connectivity and super-connectivity of Cartesian product graphs, Ars Combinatoria. 95 (2010), 235-245. (With Jun-Ming Xu)
  3. Diameter vulnerability of graphs by edge deletion. Discrete Mathematics. 309 (2009), 1001-1006. (With He-Xi Ye and Jun-Ming Xu)
  4. Forwarding index of cube-connected cycles. Discrete Applied Mathematics. 157(1) (2009), 1-7. (With Jun Yan and Jun-Ming Xu)
  5. Reliability of interconnection networks modeled by Cartesian product digraphs. Networks, 52(4) (2008), 202-205. (With Jun-Ming Xu)
  6. Connectivity and Edge-connectivity of Strong Product Graphs, Journal of University of Science and Technology of China, 38(5) (2008), 449- 455. (With Jun-Ming Xu)
  7. Cover pebbling number of some product graphs, Journal of University of Science and Technology of China, 38(9) (2008), 1030- 1035. (With Wei Kong, Yong-Liang Pan)
  8. Fault Diameter of Product Graphs, Information Processing Letters. 102 (2007), 226-228. (With Jun-Ming Xu)
  9. Feedback Number of Kautz Digraph, Discrete Mathematics, 307 (2007), 1589-1599. (With Jun-Ming Xu, Ye-Zhou Wu, Jia Huang)
  10. Some graphs with minimum Hosoya index and Maximum Merrifield-Simmons index, MATCH Communications in Mathematical and in Computer Chemistry. 57(1) (2007), 235-242. (With Xiang-Feng Pan, Jun-Ming Xu and Min-Jie Zhou)
  11. On the Randic index of unicyclic graphs with k pendant vertices, MATCH Communications in Mathematical and in Computer Chemistry. 55(2) (2006), 409417. (With Xiang-Feng Pan, Jun-Ming Xu)
  12. Connectivity of Cartesian product graphs, Discrete Mathematics, 306(1) (2006), 159-165. (With Jun-Ming Xu)
Last modified: February 06, 2026. 08:26:33.