Stephen T. Hedetniemi

  • Clemson University, USA

According to our database1, Stephen T. Hedetniemi authored at least 127 papers between 1963 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.



In proceedings 
PhD thesis 


Online presence:



Coalition graphs of paths, cycles, and trees.
Discuss. Math. Graph Theory, 2023

Performance Comparisons of Self-stabilizing Algorithms for Maximal Independent Sets.
CoRR, 2022

New resolvability parameters of graphs.
AKCE Int. J. Graphs Comb., 2020

The upper domatic number of a graph.
AKCE Int. J. Graphs Comb., 2020

Introduction to coalitions in graphs.
AKCE Int. J. Graphs Comb., 2020

Rainbow disconnection in graphs.
Discuss. Math. Graph Theory, 2018

Distribution centers in graphs.
Discret. Appl. Math., 2018

Client-server and cost effective sets in graphs.
AKCE Int. J. Graphs Comb., 2018

On ve-degrees and ev-degrees in graphs.
Discret. Math., 2017

Restricted optimal pebbling and domination in graphs.
Discret. Appl. Math., 2017

A Roman Domination Chain.
Graphs Comb., 2016

Domination number and Laplacian eigenvalue distribution.
Eur. J. Comb., 2016

Roman {2}-domination.
Discret. Appl. Math., 2016

Neighborhood-restricted [≤2]-achromatic colorings.
Discret. Appl. Math., 2016

Double Roman domination.
Discret. Appl. Math., 2016

A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets.
Theor. Comput. Sci., 2015

Very cost effective bipartitions in graphs.
AKCE Int. J. Graphs Comb., 2015

Downhill domination in graphs.
Discuss. Math. Graph Theory, 2014

Bounds on weak roman and 2-rainbow domination numbers.
Discret. Appl. Math., 2014

Independent [1, k]-sets in graphs.
Australas. J Comb., 2014

Self-stabilizing Algorithms for Unfriendly Partitions into Two Disjoint Dominating Sets.
Parallel Process. Lett., 2013

[1, 2]-sets in graphs.
Discret. Appl. Math., 2013

Linear-Time Self-Stabilizing Algorithms for Disjoint Independent Sets.
Comput. J., 2013

A self-stabilizing algorithm for optimally efficient sets in graphs.
Inf. Process. Lett., 2012

γ-graphs of graphs.
Discuss. Math. Graph Theory, 2011

Matchability and k-maximal matchings.
Discret. Appl. Math., 2011

Capacitated Domination.
Ars Comb., 2010

A note on trees, tables, and algorithms.
Networks, 2009

A linear-time algorithm for broadcast domination in a tree.
Networks, 2009

Powerful alliances in graphs.
Discret. Math., 2009

Distance- k knowledge in self-stabilizing algorithms.
Theor. Comput. Sci., 2008

Self-Stabilizing Graph Protocols.
Parallel Process. Lett., 2008

On domination and reinforcement numbers in trees.
Discret. Math., 2008

Braodcast Chromatic Numbers of Graphs.
Ars Comb., 2008

Anonymous Daemon Conversion in Self-stabilizing Algorithms by Randomization in Constant Space.
Proceedings of the Distributed Computing and Networking, 9th International Conference, 2008

Security in graphs.
Discret. Appl. Math., 2007

Broadcasts in graphs.
Discret. Appl. Math., 2006

Distance-<i>k</i> Information in Self-stabilizing Algorithms.
Proceedings of the Structural Information and Communication Complexity, 2006

An Anonymous Self-Stabilizing Algorithm for 1-Maximal Matching in Trees.
Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications & Conference on Real-Time Computing Systems and Applications, 2006

Self-Stabilizing Algorithms For Orderings And Colorings.
Int. J. Found. Comput. Sci., 2005

Self-Stabilizing Global Optimization Algorithms for Large Network Graphs.
Int. J. Distributed Sens. Networks, 2005

An algorithm for partial Grundy number on trees.
Discret. Math., 2005

Generalized subgraph-restricted matchings in graphs.
Discret. Math., 2005

Distance-two information in self-stabilizing algorithms.
Parallel Process. Lett., 2004

Self-Stabilizing Maximal K-Dependent Sets In Linear Time.
Parallel Process. Lett., 2004

A Self-stabilizing Algorithm for Maximal 2-packing.
Nord. J. Comput., 2004

An anonymous self-stabilizing algorithm for 1-maximal independent set in trees.
Inf. Process. Lett., 2004

Offensive alliances in graphs.
Discuss. Math. Graph Theory, 2004

Iterated colorings of graphs.
Discret. Math., 2004

Roman domination in graphs.
Discret. Math., 2004

Domination and irredundance in tournaments.
Australas. J Comb., 2004

Fault Tolerant Algorithms for Orderings and Colorings.
Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), 2004

Linear time self-stabilizing colorings.
Inf. Process. Lett., 2003

Defending the Roman Empire--A new strategy.
Discret. Math., 2003

<i>H</i>-forming sets in graphs.
Discret. Math., 2003

On the equality of the partial Grundy and upper ochromatic numbers of graphs.
Discret. Math., 2003

Global Defensive Alliances in Graphs.
Electron. J. Comb., 2003

Self-Stabilizing Algorithms for {k}-Domination.
Proceedings of the Self-Stabilizing Systems, 6th International Symposium, SSS 2003, 2003

A Synchronous Self-stabilizing Minimal Domination Protocol in an Arbitrary Network Graph.
Proceedings of the Distributed Computing, 2003

A Self-Stabilizing Distributed Algorithm for Minimal Total Domination in an Arbitrary System Grap.
Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 2003

Self-Stabilizing Protocols for Maximal Matching and Maximal Independent Sets for Ad Hoc Networks.
Proceedings of the 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), 2003

A Robust Distributed Generalized Matching Protocol that Stabilizes in Linear Time.
Proceedings of the 23rd International Conference on Distributed Computing Systems Workshops (ICDCS 2003 Workshops), 2003

Self-Stabilizing Distributed Algorithm for Strong Matching in a System Graph.
Proceedings of the High Performance Computing - HiPC 2003, 10th International Conference, 2003

Domination in Graphs Applied to Electric Power Networks.
SIAM J. Discret. Math., 2002

On <i>k</i>-dependent domination.
Discret. Math., 2002

Total irredundance in graphs.
Discret. Math., 2002

Fault Tolerant Distributed Coloring Algorithms that Stabilize in Linear Time.
Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS 2002), 2002

Maximal matching stabilizes in time O(m).
Inf. Process. Lett., 2001

Domination Subdivision Numbers.
Discuss. Math. Graph Theory, 2001

Stable and unstable graphs with total irredundance number zero.
Ars Comb., 2001

Domination and independence subdivision numbers of graphs.
Discuss. Math. Graph Theory, 2000

Extremal graphs for inequalities involving domination parameters.
Discret. Math., 2000

Acyclic domination.
Discret. Math., 2000

The even adjacency split problem for graphs.
Discret. Appl. Math., 2000

The complexity of approximating MAPs for belief networks with bounded probabilities.
Artif. Intell., 2000

On perfect neighborhood sets in graphs.
Discret. Math., 1999

Minus domination in graphs.
Discret. Math., 1999

Restrained domination in graphs.
Discret. Math., 1999

Irredundant and perfect neighbourhood sets in trees.
Discret. Math., 1998

Independence and Irredundance in k-Regular Graphs.
Ars Comb., 1998

Fundamentals of domination in graphs.
Pure and applied mathematics 208, Dekker, ISBN: 978-0-8247-0033-1, 1998

On weakly connected domination in graphs.
Discret. Math., 1997

Using maximality and minimality conditions to construct inequality chains.
Discret. Math., 1997

k-Path Partitions in Trees.
Discret. Appl. Math., 1997

Minus domination in regular graphs.
Discret. Math., 1996

Maximal Irredundant Functions.
Discret. Appl. Math., 1996

The Algorithmic Complexity of Minus Domination in Graphs.
Discret. Appl. Math., 1996

Computing Research Programs in the US.
Commun. ACM, 1996

Nearly perfect sets in graphs.
Discret. Math., 1995

Distance independence domination in graphs.
Ars Comb., 1995

Properties of minimal dominating functions of graphs.
Ars Comb., 1995

The Private Neighbor Cube.
SIAM J. Discret. Math., 1994

Periodic gossiping on trees.
Discret. Appl. Math., 1994

Efficient Sets in Graphs.
Discret. Appl. Math., 1993

Bibliography on domination in graphs and some basic definitions of domination parameters.
Discret. Math., 1990

Discret. Math., 1990

On the computational complexity of upper fractional domination.
Discret. Appl. Math., 1990

Centering a Spanning Tree of a Biconnected Graph.
Inf. Process. Lett., 1989

The subchromatic number of a graph.
Discret. Math., 1989

A survey of gossiping and broadcasting in communication networks.
Networks, 1988

Gallai theorems for graphs, hypergraphs, and set systems.
Discret. Math., 1988

On the equality of the grundy and ochromatic numbers of a graph.
J. Graph Theory, 1987

On the diagonal queens domination problem.
J. Comb. Theory, Ser. A, 1986

A linear algorithm for finding a minimum dominating set in a cactus.
Discret. Appl. Math., 1986

A note on total domination.
Discret. Math., 1984

Information Dissemination in Trees.
SIAM J. Comput., 1981

Partitioning trees: Matching, domination, and maximum diameter.
Int. J. Parallel Program., 1981

Rectilinear Steiner Trees in Rectangle Trees.
SIAM J. Algebraic Discret. Methods, 1980

Total domination in graphs.
Networks, 1980

Matchings and transversals in hypergraphs, domination and independence-in trees.
J. Comb. Theory, Ser. B, 1979

Linear Algorithms on Recursive Representations of Trees.
J. Comput. Syst. Sci., 1979

Linear Algorithms for Edge-Coloring Trees and Unicyclic Graphs.
Inf. Process. Lett., 1979

Minimum broadcast graphs.
Discret. Math., 1979

Disjoint cliques in regular graphs of degree seven and eight.
J. Comb. Theory, Ser. B, 1978

A linear algorithm for disjoint matchings in trees.
Discret. Math., 1978

Towards a theory of domination in graphs.
Networks, 1977

A property of trees in terms of unique connected subgraphs.
J. Graph Theory, 1977

b-Matchings in Trees.
SIAM J. Comput., 1976

On the optional hamiltonian completion problem.
Networks, 1976

Disjoint independent dominating sets in graphs.
Discret. Math., 1976

Advances on the Hamiltonian Completion Problem.
J. ACM, 1975

A Linear Algorithm for the Domination Number of a Tree.
Inf. Process. Lett., 1975

On Hamiltonian Walks in Graphs.
SIAM J. Comput., 1974

Eulerian Walks in Graphs.
SIAM J. Comput., 1973

S-Semigroups of Automata.
J. ACM, 1972

R70-36 Maximin Automata.
IEEE Trans. Computers, 1970

Determining fastest routes using fixed schedules.
Proceedings of the 1963 spring joint computer conference, 1963