Skip to Content

Shen, Jian

Contact Information
Jian Shen, Ph.D.
Associate Chair, Professor

Office: MCS 581
Phone: 512.245.3421
Research Interests
Graph Theory, Combinatorics, Combinatorial Matrix Theory, Additive Number Theory, Probabilistic Methods, Algorithm, Game Theory, and Theoretical Computer Science.

Dr. Shen received his Ph.D. from Queens University, Canada in 1998. He has been working on combinatorial matrix theory, a subject which connects linear algebra with combinatorics. He has proved a few conjectures on the exponents of primitive matrices. Dr. Shen's current research is focused on graph theory and algorithm. He has made substantial contributions to the research of a number of conjectures, including the Caccetta-Haggkuist conjecture (1978), on the cycle structure of directed graphs. He proved the up-to-date strongest result to support the Frame-Stewart conjecture (1941) on the towers of Hanoi. Dr. Shen plans to extend his research to networks design and probabilistic methods in discrete mathematics.

Selected Publications:

  • The Locus of points with equal sum of relative distances to three points, Journal of Mathematics (PRC) . (With X. Li, S. Zhang, and G. Zhang) Early View Published Online DOI: 10.13548/j.sxzz.20140409001
  • On the Chudnovsky-Seymour-Sullivan conjecture on cycles in triangle-free digraphs, Electronic J. Linear Algebra. 28(1):117-123, 2015. (With K. Chen, S. Karson, and D. Liu)
  • The (normalized) Laplacian eigenvalue of signed graphs, Taiwanese J. Math. 19(2):505-517, 2015. (With Y. Liu)
  • On the relative distances of eleven points in the boundary of a plane convex body, Discrete Math. 317(2):14-18, 2014. (With Z. Su, X. Wei, and S. Li)
  • On fractional metric dimension of graphs , Discrete Mathematics, Algorithms and Applications. 5(4) 1350037 (8 Pages), 2013. (With S. Arumugan and V. Mathew)
  • A Survey on bases of sign pattern matrices , Linear Algebra and its Applications 439(2):346-357, 2013. (With L. You)
  • The triangle inequality and its applications in the relative metric space , Open Journal of Discrete Mathematic. 5(3):127-129, 2013. (With Z. Su and S. Li)
  • Three layer Q2-free families in the Boolean lattice, Order. 30(2):585-592, 2013. (With J. Manske) pdf
  • Bounds on the spectral radii of digraphs in terms of walks , Appl. Math. Comput. 219:3721-3728, 2012. (With G. Xu and K. Fang)
  • The kth upper and lower bases of primitive non-powerful minimally strong signed digraphs, Linear and Multilinear Algebra 60(9):1093-1113, 2012. (With Y. Shao and Y. Gao)
  • Opinion dynamics with stubborn vertices, Electronic Journal of Linear Algebra . (With Y. Wu)
  • On the relative distances of nine or ten points in the boundary of a plane convex body, Discrete Applied Math., 160:303-305, 2012. (With Z. Su, S. Li, and L. Yuan) pdf
  • Enhanced Delegation Forwarding in Delay Tolerant Networks, International Journal of Parallel, Emergent and Distributed Systems, 26(5):331-345, 2011. (With X. Chen and J. Wu) pdf
  • Improving Routing Protocol Performance in Delay Tolerant Networks using Extended Information, Journal of Systems and Software, 83:1301-1309, 2010. (With X. Chen and J. Wu) pdf
  • Analyzing of the Accuracy of the Fitch Method for Reconstructing Ancestral States on Ultrametric Phylogenetic Trees, Bulletin of Mathematical Biology, 72(7):1760-1782, 2010. (With L. Zhang, J. Yang and G. Li) pdf
  • Some Inequalities in Functional Analysis, Combinatorics, and Probability Theory, Electronic Journal of Combinatorics, 17, Research Paper 58, 12 pages, 2010. (With C. Feng and L. Li). pdf
  • A sum-division estimate of reals, Proceedings of the American Mathematical Society, 138:101-104, 2010. (With L. Li)
  • On the Borel-Cantelli lemma and its generalization, Comptes Rendus Mathematique, 347:1313-1316, 2009. (With C. Feng and L. Li).
  • A bound on the scrambling index of a primitive matrix using Boolean rank, Linear Algebra and its Applications, 431(10):1923-1931, 2009. (With M. Akelbek and S. Fital).
  • The k-th upper bases of primitive non-powerful signed digraphs, Discrete Mathematics 309:2682-2686 (2009). (With Y. Gao and Y. Shao)
  • Bounds on the local bases of primitive non-powerful nearly reducible sign patterns, Linear and Multilinear Algebra 57(2):205-215 (2009). (With Y. Gao and Y. Shao) pdf
  • On the spectrum of middle-cubes, Congressus Numerantium, 195:195-204, 2009. (With K. Qiu, R. Qiu, and Y. Jiang).
  • Approximating the Spanning Star Forest Problem and Its Applications to Genomic Sequence Alignment, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 645-654 (2007). Revised journal version appeared in SIAM Journal on Computing, 38:946-962 (2008). (With T. Nguyen, M. Hou, L. Sheng, W. Miller, and L. Zhang) pdf
  • Extension of strongly regular graphs, Electronic Journal of Combinatorics, 15, Note 3, 5 pages, 2008. (With R. Gera) pdf
  • On the largest eigenvalue of non-regular graphs, Journal of Combinatorial Theory, Series B, 97(6):1010-1018, 2007. (With B. Liu and X. Wang) pdf
  • Characterization of [1,k]-Bar Visibility Trees, Electronic Journal of Combinatorics, 13, Research Paper 90, 12 pages, 2006. (with G. Chen, J. Hutchinson, and K. Keating) pdf
  • Density conditions for triangles in multipartite graphs, Combinatorica, 26(2):121-131, 2006. (with J. Bondy, S. Thomasse, and C. Thomassen) pdf
  • On two Turan numbers, Journal of Graph Theory, 51(3):244-250, 2006. pdf
  • Improved schemes for power-efficient broadcast in Ad Hoc networks, International Journal of High Performance Computing and Networking, 4(3/4):198-206, 2006. (with X. Chen) pdf
  • r-indecomposable and r-nearly decomposable matrices, Linear Algebra and its Applications, 407:105-116, 2005. (with L. You and B. Liu) pdf
  • Maximum possible hop count for package routing in MANET, in: Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks, Auerbach Publications, pp. 43-52, 2005. (with X. Chen) pdf
  • On the Frame-Stewart conjecture about the towers of Hanoi, SIAM Journal on Computing, 33(3):584-589, 2004. (with X. Chen) pdf
  • Searching for sorted sequences of kings in tournaments, SIAM Journal on Computing, 32(5):1201-1209, 2003. (With L. Sheng and J. Wu) pdf
  • Short cycles in digraphs with local average outdegree at least two, Electronic Journal of Combinatorics, 10(1), Research Paper 26, 2003. pdf
  • Second neighborhood via first neighborhood in digraphs, Annals of Combinatorics, 7(1):15-20, 2003. (With G. Chen and R. Yuster) pdf
  • On the number of arcs in primitive digraphs with large exponents, Linear Algebra and its Applications, 364:243-251, 2003. (With C. J. Wyels) pdf
  • A note on the number of edges guaranteeing a C_4 in Eulerian bipartite digraphs, Electronic Journal of Combinatorics, 9(1), Note 6, 6 pages, 2002. (With R. Yuster) pdf
  • Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs, Journal of Combinatorial Theory, Series B, 85(2):189--196, 2002. (With R. Brualdi) pdf
  • On the Caccetta-Häggkvist conjecture, Graphs and Combinatorics, 18(3):645-654, 2002. pdf
  • On generalized exponents of tournaments, Taiwanese Journal of Mathematics, 6(4):565-572, 2002. (With B. Zhou) pdf