Stephen Hedetniemi

Stephen Travis Hedetniemi (* 7. Februar 1939) ist ein US-amerikanischer Mathematiker und Informatiker.

Hedetniemi studierte an der University of Michigan mit dem Bachelor-Abschluss in Mathematik 1960, dem Master-Abschluss 1962 und der Promotion 1966 in Communication Sciences bei Frank Harary (Homomorphisms of Graphs and Automata). Er war in der Gruppe für Computerlogik der University of Michigan und wurde 1967 Assistant Professor und 1969 Associate Professor in Informatik an der University of Iowa. Ab 1972 war er Associate Professor an der University of Virginia. Außerdem war er 1972 zwei Monate am Naval Weapons Laboratory in Dahlgren und 1975/76 Gastprofessor an der University of Victoria. 1977 bis 1982 war er Professor und Leiter der Abteilung für Informatik an der University of Oregon. Ab 1982 war er Professor an der Clemson University.

Er befasst sich mit Entwurf und Analyse von Algorithmen und Graphentheorie. Unter anderem befasste er sich mit dominierenden Mengen in Graphen (das heisst einer Untermenge D der Knoten, so dass jeder Knoten des Graphen zu einem Element von D benachbart ist) und gilt in diesem Gebiet als Pionier.

Von ihm stammt die in seiner Dissertation aufgestellte Vermutung von Hedetniemi, dass die chromatische Zahl des Tensorprodukts zweier Graphen G, H gleich dem Minimum der chromatischen Zahlen von G und H ist. Sie wurde 2019 durch ein Gegenbeispiel durch Yaroslav Shitov widerlegt.

• Homomorphisms of Graphs and Automata, University of Michigan Communications Sciences Program, Technical Report 03105-44-T, 1966 (Dissertation)
• mit E. J. Cockayne: Towards a theory of domination in graphs, Networks, Band 7, 1977, S. 247–261
• mit E. J. Cockayne, R. M. Dawes: Total domination in graphs, Networks, Band 10, 1980, S. 211–219
• mit P. J. Slater, E. J. Cockayne: Information dissemination in trees, SIAM Journal on Computing, Band 10, 1981, S. 692–701
• mit S. M. Hedetniemi, A. L. Liestman: A survey of gossiping and broadcasting in communication networks, Networks, Band 18, 1988, S. 319–349
• mit T. W. Haynes, P. Slater: Fundamentals of domination in graphs, CRC Press1998
• mit T. W. Haynes, P. J. Slater: Domination in Graphs: Advanced Topics,Monographs and Textbooks in Pure and Applied Mathematics 209, Marcel Dekker 1998
• mit T. W. Haynes, S. M. Hedetniemi, M. A. Henning: Domination in graphs applied to electric power networks, SIAM Journal on Discrete Mathematics, Band 15, 2002, S. 519–529

• Gary Chartrand, Teresa W. Haynes, Michael A. Henning, Ping Zhang (Hrsg.):From Domination to Coloring - Stephen Hedetniemi’s Graph Theory and Beyond, Springer 2019 (zum 80. Geburtstag von Hedetniemi)