Related Research Articles
The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
In mathematics, a knot is an embedding of the circle S1 into three-dimensional Euclidean space, R3. Often two knots are considered equivalent if they are ambient isotopic, that is, if there exists a continuous deformation of R3 which takes one knot to the other.
Hassler Whitney was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration theory.
Béla Bollobás FRS is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory, and percolation. He was strongly influenced by Paul Erdős since the age of 14.
In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).
In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k − 1 independent sets.
Richard Kenneth Guy was a British mathematician. He was a professor in the Department of Mathematics at the University of Calgary. He is known for his work in number theory, geometry, recreational mathematics, combinatorics, and graph theory. He is best known for co-authorship of Winning Ways for your Mathematical Plays and authorship of Unsolved Problems in Number Theory. He published more than 300 scholarly articles. Guy proposed the partially tongue-in-cheek "strong law of small numbers", which says there are not enough small integers available for the many tasks assigned to them – thus explaining many coincidences and patterns found among numerous cultures. For this paper he received the MAA Lester R. Ford Award.
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.
In the mathematical field of graph theory, a Smith graph is either of two kinds of graph.
Raymond Edward Alan Christopher Paley was an English mathematician who made significant contributions to mathematical analysis before dying young in a skiing accident.
Andrew Mattei Gleason (1921–2008) was an American mathematician who made fundamental contributions to widely varied areas of mathematics, including the solution of Hilbert's fifth problem, and was a leader in reform and innovation in mathematics teaching at all levels. Gleason's theorem in quantum logic and the Greenwood–Gleason graph, an important example in Ramsey theory, are named for him.
In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.
In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.
In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.
András Hajnal was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.
Jon Hal Folkman was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation.
Derek Gordon Corneil is a Canadian mathematician and computer scientist, a professor emeritus of computer science at the University of Toronto, and an expert in graph algorithms and graph theory.
References
- 1 2 Math faculty listing, Boston College, retrieved 2011-03-28.
- ↑ John Howard Smith at the Mathematics Genealogy Project.
- ↑ Smith, J.H. (1973), "Aggregation of Preferences with Variable Electorates", Econometrica, 41 (6): 1027–1041, doi:10.2307/1914033, JSTOR 1914033 .
- ↑ Smith, John H. (1970), "Some properties of the spectrum of a graph", Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), New York: Gordon and Breach, pp. 403–406, MR 0266799 .
- ↑ Fein, Burton; Gordon, Basil; Smith, John H. (1971), "On the representation of −1 as a sum of two squares in an algebraic number field", Journal of Number Theory, 3 (3): 310–315, doi:10.1016/0022-314X(71)90005-9, MR 0319940 .
   | This article about an American mathematician is a stub. You can help Wikipedia by expanding it. |