Jian Shen Professor of Mathematics Office: Math/CS 451 Phone: 512-245-3740 Fax: 512-245-3425 Email: js48@txstate.edu Home Page

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:

• J. Shen, B. Liu and X. Wang; On the largest eigenvalue of non-regular graphs, J. Combin. Theory, Ser. B. 97(6):1010-1018 (2007).
• G. Chen, J. Hutchinson, K. Keating, and J. Shen. Characterization of [1,k]-Bar Visibility Trees. Electronic J. Combin. 13, Research Paper 90, 12 pages, 2006.
• J. Bondy, J. Shen, S. Thomasse, and C. Thomassen. Density conditions for triangles in multipartite graphs. Combinatorica, 26(2):121-131, 2006.
• J. Shen. On two Turan numbers. J. Graph Theory, 51(3):244-250, 2006.
• X. Chen and J. Shen. Improved schemes for power-efficient broadcast in Ad Hoc networks. International Journal of High Performance Computing and Networking, 4(2) Research paper 9, 2006.
• L. You, B. Liu, and J. Shen. r-indecomposable and r-nearly decomposable matrices. Linear Algebra Appl. 407:105-116, 2005.
• X. Chen and J. Shen. 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.
• X. Chen and J. Shen. On the Frame-Stewart conjecture about the towers of Hanoi. SIAM J. Computing, 33(3):584-589, 2004.
• J. Shen, L. Sheng, and J. Wu. Searching for sorted sequences of kings in tournaments. SIAM J. Computing, 32(5):1201-1209, 2003.
• J. Shen. Short cycles in digraphs with local average outdegree at least two. Electronic J. Combin. 10(1) Research paper 26, 11 pages. (electronic), 2003.
• G. Chen, J. Shen, and R. Yuster. Second neighborhood via first neighborhood in digraphs, Ann. Comb. 7(1):15-20, 2003.
• J. Shen and C. J. Wyels. On the number of arcs in primitive digraphs with large exponents. Linear Algebra Appl. 364:243-251, 2003.
• B. Zhou and J. Shen. On generalized exponents of tournaments. Taiwanese J. Math. 6(4):565-572, 2002.
• J. Shen. On the Caccetta-Haggkvist conjecture. Graphs Combin. 18(3):645-654, 2002.
• R. Brualdi and J. Shen. Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs. J. Combin. Theory B, 85(2):189-196, 2002.
• J. Shen and R. Yuster. A note on the number of edges guaranteeing a C4 in Eulerian bipartite digraphs. Electronic J. Combin. 9(1), Note 6, 6 pages. (electronic), 2002.
• R. Brualdi and J. Shen. Landau's inequalities for tournament scores and a short proof of a theorem on transitive sub-tournaments. J. Graph Theory, 38(4):244-254, 2001.
• D. Gregory and J. Shen. On the girth of digraphs with high connectivity. Ars Combin. 60:201-207, 2001.
• R. A. Brualdi and J. Shen. Diameter of the NEPS of bipartite graphs. Discrete Math., 226(1-3):373--376, 2001.
• B. Liu, Z. Bo, Q. Li, and J. Shen. Generalized index of Boolean matrices. Ars Combin., 57:247--255, 2000.
• J. Shen and D. Gregory. Exponents of vertex-transitive digraphs. Discrete Math. 212(3):245-255, 2000.
• J. Shen. Exponents of 2-regular digraphs. Discrete Math., 214(1-3):211--219, 2000.
• J. Shen. On the girth of digraphs. Discrete Math., 211(1-3):167--181, 2000.
• J. Shen, D. Gregory, and S. Neufeld. Exponents of indecomposability. Linear Algebra Appl., 288(1-3):229--241, 1999.
• R. A. Brualdi and J. Shen. Discrepancy of matrices of zeros and ones. Electron. J. Combin., 6(1): Research Paper 15, 12 pages. (electronic), 1999.
• S. Neufeld and J. Shen. Some results on generalized exponents. J. Graph Theory, 28(4):215--225, 1998.
• J. Shen. Directed triangles in digraphs. J. Combin. Theory Ser. B, 74(2):405--407, 1998.
• J. Shen and S. Neufeld. Local exponents of primitive digraphs. Linear Algebra Appl., 268:117--129, 1998.
• J. Shen and S. Neufeld. On a problem of Lewin. Linear Algebra Appl., 274:411--426, 1998.
• J. Xu, J. Shen, and Z. Li. Some results on arithmetic and balanced graphs. J. China Univ. Sci. Tech., 28(2):183--193, 1998.
• J. Shen. A bound on the exponent of primitivity in terms of diameter. Linear Algebra Appl., 244:21--33, 1996.
• J. Shen. An improvement of the Dulmage-Mendelsohn theorem. Discrete Math., 158(1-3):295--297, 1996.
• J. Shen. A problem on the exponent of primitive digraphs. Linear Algebra Appl., 244:255--264, 1996.
• J. Shen. Some estimated formulas for the Frobenius numbers. Linear Algebra Appl., 244:13--20, 1996.
• J. Shen and D. A. Gregory. Some eigenvalue inequalities for matrices with restricted entries. Linear and Multilinear Algebra, 41(2):107--112, 1996.
• J. Shen. Proof of a conjecture about the exponent of primitive matrices. Linear Algebra Appl., 216:185--203, 1995.
• J. Shen and Q. Li. Two theorems on double loop networks. J. China Univ. Sci. Tech., 25(2):127--132, 1995.