“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 623
School of Mathematics
  Title:   Greedy defining sets of graphs
  Author(s):  M. Zaker
  Status:   Published
  Journal: Australas. J. Combin.
  Vol.:  23
  Year:  2001
  Pages:   231-235
  Supported by:  IPM
  Abstract:
For a graph G and an order σ on V(G), we define a greedy defining set as a subset S of V(G) with an assignment of colors to vertices in S, such that the pre-coloring can be extended to a X(G)-coloring of G by the greedy coloring of (G,σ). A greedy defining set of a X(G)-coloring C of G is a greedy defining set, which results in the coloring C (by the greedy procedure). We denote the size of a greedy defining set of C with minimum cardinality by GDN(G,σ,C). In this paper we show that the problem of determining GDN(G,σ,C), for an instance (G,σ,C) is an NP-complete problem.

Download TeX format
back to top
scroll left or right