S. L. Hakimi
Encyclopedia
S. Louis Hakimi is a mathematician
, a professor emeritus of mathematics at Northwestern University
, IL. He is known for his work with V. J. Havel
independently on realizing a set of integers as a degree sequence
of a graph. This algorithm was found out at the same time Erdos
-Gallai
gave their mathematical criteria.
Hakimi received his Ph.D. from University of Illinois at Urbana-Champaign
, in 1959.
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
, a professor emeritus of mathematics at Northwestern University
Northwestern University
Northwestern University is a private research university in Evanston and Chicago, Illinois, USA. Northwestern has eleven undergraduate, graduate, and professional schools offering 124 undergraduate degrees and 145 graduate and professional degrees....
, IL. He is known for his work with V. J. Havel
V. J. Havel
V. J. Havel is a Czech mathematician known for his work with S. L. Hakimi independently on realizing a set of integers as a degree sequence of a graph. This algorithm was found out at the same time Erdős–Gallai gave their mathematical criteria.-References:...
independently on realizing a set of integers as a degree sequence
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
of a graph. This algorithm was found out at the same time Erdos
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
-Gallai
Tibor Gallai
Tibor Gallai was a Hungarian mathematician. He worked in combinatorics, especially in graph theory, and was a lifelong friend and collaborator of Paul Erdős. He was a student of Dénes König and an advisor of László Lovász...
gave their mathematical criteria.
Hakimi received his Ph.D. from University of Illinois at Urbana-Champaign
University of Illinois at Urbana-Champaign
The University of Illinois at Urbana–Champaign is a large public research-intensive university in the state of Illinois, United States. It is the flagship campus of the University of Illinois system...
, in 1959.
See also
- Star (graph theory)Star (graph theory)In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph II. Uniqueness, SL Hakimi - Journal of the Society for Industrial and Applied …, 1963 - jstor.org
- Recognizing tough graphs is NP-hardNP-hardNP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
, D Bauer, SL Hakimi, E Schmeichel - Discrete Applied Mathematics, 1990 - portal.acm.org