Professor Information

Alexander Kelmans

Address College of Natural Sciences
Department of Mathematics
17 University Ave. Ste 1701
San Juan, PR 00925-2537
Office NCN II A-119
Office Hours
Program MATE 4995 (023) PA A-227
MATE 8986: TEMA: Introduction to Graph Theory
Telephone (787) 764-0000 88256
E-Mail ude.sregtur.roctur@snamlek moc.liamg@rednaxela.snamlek
MathSciNet Link

Education

PhD, Soviet Academy of Sciences, 1968

Research

Graph Theory; Combinatorics; Discrete Optimization and Algorithms; Networks Reliability; Random Graphs; Matroids and Polymatroids; Algebraic Graph Theory; Algorithm Complexity

Selected Publications

  1. Deng Aiping and Alexander Kelmans, Laplacian Spectra of Digraph Transformations, Linear and Multilinear Algebra, 1 – 39. Published online: 12 July 2016 http://dx.doi.org/10.1080/03081087.2016.1202183
  2. José F. De Jesús and Alexander Kelmans, K-circular Matroids of Graphs, Online publication: 14 April 2017, DOI information: 10.1016/j.dam.2017.02.026. See also ArXiv: math.CO/ 1508.05364 v1 (2015) 1-38.
  3. Deng Aiping, Mengyu Feng, and Kelmans Alexander, Adjacency Polynomials of Digraph- Transformations, Discrete Applied Mathematics (2016), 15-38.
  4. José F. De Jesús and Alexander Kelmans, On Graphs Uniquely Defined by Their k- Circular Matroids, Discrete Applied Mathematics, Online publication: 20 October 2016, DOI information: 10.1016/j.dam.2016.09.046. See also: ArXiv: math.CO/ 1508.07627 v1 (2015) 1-21.
  5. Deng Aiping and Kelmans Alexander, Spectra of Digraph Transformations, Linear Algebra and its Applications, 439 (2013) 106-132.
  6. Kelmans A.K. and Rubinov A.R., On convex polytopes in Rn containing and avoiding zero, European Journal of Combinatorics, 34 (2013) 764-769.
  7. Deng Aiping, Kelmans Alexander, and Juan Meng, Laplacian Spectra of Regular Graph Transformations, Discrete Applied Mathematics, Online publication: 10-SEP-2012 DOI information: 10.1016/j.dam.2012.08.020 and 161(2013) 118-133.
  8. Kelmans A.K., Operations on Graphs Increasing Some Graph Parameters, ArXiv: math.CO/ 1109.4622v2 (2011) 1-59.
  9. Kelmans A.K., Does a cubic 3-connected graph have a P3-packing that avoids at most two vertices ? ArXiv: math.CO/ 0910.2766v1 (2011) 1-29.
  10. Kelmans A.K., Packing 3-vertex paths in claw-free graphs and related topics, Discrete Applied Mathematics, Online publication: doi:10.1016/j.dam.2010.05.001 and 159 (2011) 112-127.
  11. Kelmans A.K., Packing 3-vertex paths in cubic 3-connected graphs, Discrete Mathematics, doi:10.1016/j.disc.2009.08.007.
  12. Kelmans A.K. and Postnikov A., Generalizations of Abel’s and Hurwitz’s identities, European Journal of Combinatorics (2008) 1535-1543.
  13. Kelmans A.K., Packing 3-vertex paths in 2-connected graphs, ArXiv: math.CO/ 0712.4151v1 (2007) 1-13.
  14. Kelmans A.K., Packing 3-vertex paths in claw-free graphs, ArXiv: math.CO/0711.3871v1, (2007) 1-13.
  15. Kelmans A.K., Packing k-edge trees in graphs of restricted vertex degrees, Journal of Graph Theory, 55 (2007) 306-324.
  16. Kelmans A.K., On Hamiltonicity of {claw, net}-free graphs, Discrete Mathematics 306, (2006) 2755-2761.
  17. Kelmans A.K., On the Cycle Space of a 3-Connected Graph, ArXiv: math.CO/0609219v1 (2006).
  18. Kelmans A.K., Counterexamples to the cubic graph domination conjecture, ArXiv: math.CO/0607512v1 (2006).
  19. Kelmans A.K., Simple and direct proof of MacLane’s planarity criterion, ArXiv: math.CO/0607172v1 (2006).
  20. Kelmans A.K., On Λ-packings in 3-connected graphs, RUTCOR Research Report 23-2005, Rutgers University (2005).
  21. Kelmans A.K., Mubayi D., How many disjoint 2-edge paths must a cubic graph have ? Journal of Graph Theory, 45 (2004) 57-79.
  22. Kelmans A.K., On graph closures, Discrete Mathematics 271, (2003) 141–168.
  23. A. Collado, A. Kelmans, D. Krasner, On convex polytopes in the plane “containing” and “avoiding” zero, DIMACS Report 2002-33, July 2002, p. 1-10.
  24. Kelmans A.K., On the Laplacian spectrum of (α, ω)–graphs, Europian Journal of Combinatorics, 23 (2002) 673–682.
  25. Kelmans A.K., Mubayi D., and Sudakov B., Packing trees in a regular graph, Electronic Journal of Combinatorics, vol. 8 (1) (2001).
  26. A. K. Kelmans, On homotopy of connected graphs having the same degree function, Discrete Mathematics 230, 1-3, (2001) 167-187.
  27. Kelmans A.K., On graph planarity and semi-duality, Discrete Mathematics 230, 1-3, (2001) 149-166.
  28. Kaneko A., Kelmans A., Nishimura T., On packing 3-vertex paths in a graph, J. Graph Theory 36 (2001) 175-197.
  29. Kelmans A.K., Crossing properties of reliability functions of a graph, J. Graph Theory 35 (2000) 206-221.
  30. Kelmans A.K., On convex embedding of 3-connected planar graphs, J. Graph Theory 33 (2000) 120-124.
  31. Kelmans A.K., On homotopy of connected graphs having the same degree function RUTCOR Research Report 39–98, Rutgers University (1999).
  32. Kelmans A.K., Pak I., Postnikov A., Tree and forest volumes of graphs, RUTCOR Research Report 47–99, Rutgers University (1999).
  33. Kelmans A.K. and Xuerong Yong, On the distribution of eigenvalues of graphs, Discrete Mathematics 199 (1999), 251-258.
  34. Kelmans A.K., On claw – and net-free graphs, RUTCOR Research Report 18–99, Rutgers University (1999).
  35. Kelmans A.K., A new axiom for the bases of a matroid, Included in the paper of A. Borovik, I. Gelfand, N. White, On exchange properties for Coxeter matroids and oriented matroids, Discrete Mathematics 179 (1998) 59-72.
  36. Kelmans A.K., More about graph planarity, RUTCOR Research Report 32-97, Rutgers University (1997).
  37. Egawa Y., Kano M., Kelmans A.K. Star partitions of graphs, Journal of Graph Theory, 25 No. 3, (1997) 185-190.
  38. Kelmans A.K., Optimal packing of induced stars in a graph, Discrete Mathematics, 173, (1997) 97-127.
  39. Kelmans A.K., Transformations of a graph increasing its Laplacian polynomials and the number of trees, Europian Journal of Combinatorics, 18 (1997) 35-48.
  40. Kelmans A.K., On graphs with the maximum number of spanning trees, Random Structures and Algorithms, 9 (1996) 177-192.
  41. Hartsfield N., Kelmans A.K., and Yun-Qiu Shen, On the Laplacian polynomial of a k–cube extension, Congressus Numeratium, 119 (1996) 73-77.
  42. Hammer P.L. and Kelmans A.K., Laplacian spectra and spanning trees of threshold graphs, Discrete Applied Mathematics, 65 (1996) 255-273.
  43. Kelmans A.K., On a duality theorem for packing induced stars in a graph, RUTCOR Research Report 43-96, Rutgers University (1996). [48] Kelmans A.K., On all-terminal reliability of random graphs, RUTCOR Research Report 41-96, Rutgers University (1996). [49] Kelmans A.K., On two-terminal reliability of random graphs, RUTCOR Research Report 40-96, Rutgers University (1996).
  44. Dean N., Keh-Wei Lih, Kelmans A.K., Massey W.A., Winkler P. The spanning tree enumeration problem for digraphs, in Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Volume 1, Edited by Y. Alavi and A. Schwenk, (1995) 277-287.
  45. Kelmans A.K., Operations on graphs increasing their Laplacian polynomials RUTCOR Research Report 18-95, Rutgers University (1995).
  46. Kelmans A.K., On semi-isomorphisms and semi-dualities of graphs, Graphs and Combinatorics 10 (1994) 337–352.
  47. Kelmans A.K., Multiple crossings of network reliability functions, RUTCOR Research Report 43-94, Rutgers University (1994).
  48. Hammer P.L. and Kelmans A.K., On universal threshold graphs, Combinatorics, Probability and Computing 3 (1994) 327-344.
  49. Kelmans A.K., Graph planarity and related topics, Contemporary Mathematics 147 (1993), 635-667.
  50. Kelmans A.K., Spanning trees of extended graphs, Combinatorica 12 (1) (1992) 45-51.
  51. Kelmans A.K., From Whitney to Whitney. RUTCOR Lecture Notes 1-90, Rutgers University (1990) 1-11.
  52. Bogmér, Joó. I. and Kelmans A.K. Spanning trees of of a graph and network reliability Annals Univ. Sci 33 (1) (1990) 239-246.
  53. Kelmans A.K., Matroids and combinatorial optimization problems. Institute of Control Sciences, Moscow (1989) [in Russian].
  54. Kelmans A.K., For any finite subset T of at least 14 elements there exist infinitly many cyclically 4-connected graphs with a vertex subset T and having no cycle containing T. (1981) (unpublished, describe by M.V. Lomonosov in his lecture to the Workshop on VLSI, Bonn, Yune, 1988).
  55. Kelmans A.K., Matroids and Whitney theorems on 2-isomorphism and planarity of graphs. Uspehi Mat. Nauk 43 (5), (1988) 199-200 [in Russian].
  56. Kelmans A.K., Cubic bipartite and cyclically 4-connected graphs without hamiltonian cycles. Uspehi Mat. Nauk 43 (3), (1988) 181-182 [in Russian].
  57. Kelmans A.K., On network reliability, Proceedings of the 5-th All–Union School–Seminar on distributed automatic systems, IPU, CNII ASU, Moscow, 1988.
  58. Kelmans A.K., Non-separating cycles and planarity of 3-connected graphs without essential 3-cuts or triangles. In Problemi Diskretnoy Optimizacii i Metodi ih Resheniya, AN SSSR, CEMI, Moscow (1987) 224-233 [in Russian].
  59. Kelmans A.K., A short proof and strengthenings of the Whitney 2-isomorphism theorem on graphs. Discrete Mathematics 64 (1987) 13-25.
  60. Kelmans A.K., On 3-skeins in a 3-connected graph. Studia Scientarum Mathematicarum Hungarica 22 (1987) 265-273.
  61. Kelmans A.K., Polessky B.P., Extremal sets and covering and packing problems in a matroid. In Issled. po prikladnoy teorii grafov, Novosibirsk (1986) 140-168 [in Russian](Amer. Math. Soc. Transl. (2) Vol. 158, (1994) 149-173).
  62. Kelmans A.K., Constructions of cubic bipartite and 3-connnected graphs without hamil- tonian cycles. In Analiz Zadach Formirovaniya i Vybora Alternativ, VNIISI, Moscow 10 (1986) 64-72 [in Russian].
  63. Kelmans A.K., On 3-connected graphs without essential 3-cuts or triangles. Soviet Math. Dokl. 33 (1986) 698-703.
  64. Kelmans A.K., On the existence of a “most complex” problem in a class of problems verifiable in nonpolynomial time. Soviet Math. Dokl. 311 (1985) 576–582.
  65. Kelmans A.K., Finding special subdivisions of K4 in a graph. In Finite and Infinite Sets (Eger, Hungary, 1981), Colloq. Math. Sci. Ja ́nos Bolyai, Vol. 37, North–Holland (1984), 487-508.
  66. Kelmans A.K., On edge semi-isomorphisms of graphs induced by their isomorphisms. In Models of Operations Research in Computational Systems Yarosl. Gos. Universitet, Yaroslavl (1985) 80-95 [in Russian], Amer. Math Transl. (2) 158 (1994) , 101-111.
  67. Kelmans A.K., On homeomorphic imbeddings of graphs with given properties. Soviet Math. Dokl. 29 (1984) 130-135.
  68. Kelmans A.K., On edge map of graphs preserving the subgraphs of a given type. In Modeli i Algoritmy Issledovaniya Operaciy i ih Primenenie k Organizacii Raboty v Vichislitelnih Systemah. Yarosl. Gos. Universitet, Yaroslavl (1984) 19-30 [in Russian](Amer. Math. Soc. Transl. (2) Vol. 158, (1994) 101-111). Presented at the Moscow Discrete Mathematics Seminar in Febduary 1976.
  69. Kelmans A.K., On planarity of 3-connected graphs without essential 3-vertex cuts and triangles. Methods for solving optimization graph problems (1984) 59-61.
  70. Kelmans A.K., A strengthening of the Kuratowski planarity criterion for 3-connected graphs. Discrete Mathematics 51 (1984) 215-220.
  71. Kelmans A.K., Edge maps and isomorphisms of graphs, Annals of Discrete Mathematics 20 (1984).
  72. Kelmans A.K., Lomonosov M.V., Problems on cycles through prescribed vertices in a graph. In Finite and Infinite Sets, Vol. 2, Colloq. Math. Soc. Ja ́nos Bolyai (Eger, Hungary, 1981), North-Holland, 37 (1984) 882-884.
  73. Kelmans A.K., A problem on 3-skeins of a graph containing prescribed edges. In Finite and Infinite Sets, Vol. 2, Colloq. Math. Soc. J ́anos Bolyai (Eger,Hungary, 1981), North-Holland, 37 (1984) 880-882.
  74. Kelmans A.K., On existence of given subgraphs in a graph. In Algoritmy Diskretnoy Optimizacii i ih Primeneiya v Vychislitelnih Systemah, Yarosl. Gos. Universitet, Yaroslavl (1983) 3-20 [in Russian].
  75. Kelmans A.K., A criterion for the existence of two disjoint and overlapping chord-chains of a given cycle in a graph. In Algoritmicheskie Konstrukcii i ih Effectivnost, Yarosl. Gos. Universitet, Yaroslavl (1983) 50-60 [in Russian].
  76. Kelmans A.K., Lomonosov M.V. On cycles through prescribed vertices in weakly sepa- rable graphs. Discrete Mathematics 46 (1983) 183-189.
  77. Kelmans A.K., Kimelfeld B.N. Multiplicative submodularity of a matrix’s principal minor as a function of the set of the rows and some combinatorial applications. Discrete Mathematics 44 (1983) 113-116.
  78. Hemminger R.L., Jung H.A, Kelmans A.K., On 3–skein isomorphisms of a graph, Combinatorica 2 (4), (1982) 373-376.
  79. Kelmans A.K., Lomonosov M.V., A cubic 3–connected graph having no cycle through given 10 vertices has the “Petersen form”. J. Graph Theory 6 (1982) 495-496.
  80. Kelmans A.K., Lomonosov M.V., When m vertices in a k-connected graph cannot be walked round along a simple cycle. Discrete Mathematics 38, (1982) 317-322.
  81. Kelmans A.K., Lomonosov M.V., On cycles through prescribed vertices in a graph, In 27. Intern. Wiss. Koll. TM Ilmenau, 1982.
  82. Kelmans A.K., Finding special subdivisions of K4 in a graph. In Finite and Infinite Sets, Colloq. Math. Soc. J ́anos Bolyai, (Szeged, Hungary, 1981) 487-508.
  83. Kelmans A.K., On 3-skeins in a graph. In All–Union Conference on Statistical and Discrete Analysis of Non-digital Information, Moscow – Alma Ata (1981) [in Russian].
  84. Kelmans A.K., The concept of a vertex in a matroid, the non-separating cycles and a new criterion for graph planarity. In Algebraic Methods in Graph Theory, Vol. 1, Colloq. Math. Soc. Ja ́nos Bolyai, (Szeged, Hungary, 1978) North–Holland 25 (1981) 345-388.
  85. Kelmans A.K., Graph expansion and reduction. In Algebraic Methods in Graph Theory, Vol. 1, Colloq. Math. Soc. Ja ́nos Bolyai, (Szeged, Hungary, 1978) North-Holland 25 (1981) 318-343.
  86. Kelmans A.K., Lomonosov M.V., On the maximal number of disjoint paths connecting given terminals in a graph. Abstract, San Francisco Annual Meeting of the AMS, January 7-11 (1981).
  87. Kelmans A.K., On graphs with randomly deleted edges. Acta Math.Acad. Sci. Hung. 37 (1-3), (1981) 259-267.
  88. Kelmans A.K., A new planarity criterion for 3-connected graphs. J. Graph Theory 5 (1981) 259-267.
  89. Kelmans A.K., Zaitcev M.A., Non-isomorphic trees with the same probability of con- nectivity. In Syst. Issl. Metall. Processov i Proizvod. MISIS, Nauka, 22 (1980) 87-90 [in Russian]. [96] Kelmans A.K., Graphs with an extremal number of spanning trees. J. Graph Theory 4 (1980) 119-122.
  90. Kelmans A.K., Concept of a vertex in a matroid and 3-connected graphs. J. Graph Theory 4 (1), (1980) 13-19.
  91. Kelmans A.K., A rigid graph is a graph of the edge intersections of subtrees of a tree with the vertices of degree at most 3. Graph Theory Newsletters 9 (1), September (1979).
  92. Kelmans A.K., Zaitcev M.A., On non-isomorphic trees with the same probability of their connectivity. Graph Theory Newsletters 8 (3), (1979).
  93. Kelmans A.K., The graph with the maximum probability of connectivity depends on the edge removal probability. Graph Theory Newsletters 9 (1), (1979) 2–3.
  94. Kelmans A.K., Graph constructing. In Grafy, Hipergrafy i Algebraicheskie systemy. Proceedings of All-Union seminar on discrete mathematics, Odessa, 1977. AN MSSR, Kishinev (1979) [in Russian].
  95. Kelmans A.K., A minimal imperfect graph distinct from an odd cycle and from a com- plement to an odd cycle has no vertex of degree at most six. XX. Internationales Wissenschaftliches Kolloquium Technische Hochshule Ilmenau – 1978, Ilmenau (1978) Techn. Hochschule.
  96. Kelmans A.K., Zaitcev M.A., On trees with randomly deleted vertices. In Algorithm. Issl. v Kombinatorike Nauka, Moscow (1978) 107-118 [in Russian].
  97. Dinic E.A., Kelmans A.K., Zaitcev M.A., Non-isomorphic trees with the same T-poly- nomials. Information Processing Letters 6 (3), (1977) 73-76.
  98. Kelmans A.K., Comparison of graphs by their probability of connectivity. In Kombinator. Asympt. Analiz, Krasnoyarsk (1977) 69–81 [in Russian].
  99. Kelmans A.K., The number of graph spanning trees containing a given forest. Acta Math. Acad. Sci. Hungar. 27 (1-2) (1976) 89-95.
  100. Kelmans A.K., Operations on graphs that increase the number of their spanning trees. In Issledovanie po Discretnoy Optimizacii, Nauka, Moscow (1976) 406-424 [in Russian](MR 56 # 3342).
  101. Kelmans A.K., Comparison of graphs by their number of spanning trees. Discrete Mathematics 16 (1976) 241-261.
  102. Kelmans A.K., Lomonosov M.V., Polessky V.P. On the minimal covering in a matroid. Problemi peredachi informacii 12 (3) (1976) 94–107 [in Russian].
  103. Kelmans A.K., Chelnokov V.M. A certain polynomials of a graph and graphs with an extremal number of trees. J. Combinatorial Theory (B) 16 (1974) 197-214.
  104. Kelmans A.K., On optimal vertex in a graph. In Issled. po diskretnoi matematike, Nauka, Moscow (1973) 151-158 [in Russian].
  105. Kelmans A.K., Graphs with the same numbers of chains of length two between adjacent and non-adjacent vertices. In Voprosy Kibernetiki, Moscow (1973) 70-75 [in Russian].
  106. Kelmans A.K., On the determination of the eigenvalues of some special matrices. Ekonomika i Matematicheskie Metodi 8 (2), (1972) 266-272 [in Russian].
  107. Kelmans A.K., Asymptotic formulae for the probability of k-connectedness of random graphs. Theory Prob. Appl. 17 (2) (1972) 253–265 [in Russian](MR 45 # 7772).
  108. Kelmans A.K., The connectivity of graphs with randomly deleted vertices. Automat. Remote Control 33, 4 (1972) [in Russian](MR 54 # 7124).
  109. Kelmans A.K., On analysis and synthesis of probabilistic networks. In Adaptive Systems. Large Systems., Nauka, Moscow (1971) 264-273 [in Russian].
  110. Kelmans A.K., On estimating of probabilistic characteristics of random graphs. Automat. Remote Control 32 (1970) 1833-1839 [in Russian](MR #5056).
  111. Kelmans A.K., Probabilistic networks and randomly deleted elements. In Dokl. Vses. Sovesc. po Statist. Metodam Teorii Upravlenija, Moscow (1970) 18-27 [in Russian].
  112. Kelmans A.K., On Steiner trees. In Kibernetica i Upravlenie, Nauka, Moscow (1967) [in Russian].
  113. Kelmans A.K., On metric properties of a tree. In Kibernetica i Upravlenie, Nauka, Moscow (1967) 98-107 [in Russian].
  114. Kelmans A.K., On the connectivity of probabilistic networks. Avtomat. i Telemeh. (Automat. Remote Control) 28 (3) (1967) 98-116 [in Russian].
  115. Kelmans A.K., On properties of the characteristic polynomial of a graph. In Kiber. na Sl. Kom. 4, Energiya, Moscow–Leningrad (1967) [in Russian].
  116. Kelmans A.K., The number of trees in a graph II. Avtomat. i Telemeh. (Automat. Remote Control) 2 (1966) 56-65 [In Russian] (English translation in Automat. Remote Control, 27 (1966)).
  117. Kelmans A.K., Some problems of the analysis of the net reliability. Avtomat. i Telemeh. (Automat. Remote Control) 26 (1965) 567-574 [in Russian].
  118. Kelmans A.K., The number of trees in a graph I. Avtomat. i Telemeh. (Automat. Remote Control) 12 (1965) 2194-2204 [in Russian](En- glish translation in Automat. Remote Control, 26 (1965)).
  119. Kelmans A.K., Mamikonov A.G. Constructing optimal networks. Avtomat. i Telemeh. 25 (2), (1964) 207-212 [in Russian].
  120. Kelmans A.K., On optimization problems in theory of information curcuit reliability. Avtomat. i Telemeh. 25 (5), (1964) 661-667 [in Russian].
  121. Kelmans A.K., The capability of distinguishing of the characteristic polynomial of the conductive matrix of a graph, manuscript, 1964 (described by Cvetkovi ́c D.M. Graphs and their spectra. Elektrohn. Fak., Ser. Mat. Fiz., No. 354 — No. 356. (1971) 1-50.

Selected Grants and Awards

Additional Information