Given a finite loopless graph G (resp. digraph D), let ~r(G), q~(G) and ~k(D) denote the minimal cardinalities of a completely separating system of (3, a separating system of G and a separating system of D, respectively. The main results of this paper are: (i) o'(G) =rain m Lm/2J ~'y(G) and ~0(G)= ['log 2 "y(G)] where 3'(G) denotes the chromatic number of (3. (ii) All the problems of determining o-(G), ~o(G) and q~(D) are NP-complete.
1. Pre "lmainmies
The graphs and the digraphs considered in this paper are all finite. No loops are permitted.
In order to state our problems we need to generalize the definitions of separating systems of a finite set.
Let G =(V,E) be a graph with vertex-set V(G) and edge-set E(G), and F={XI ..... X,,} a family of subsets of V(G).
Call F a total separating system of G if for any adjacent vl, v i ~ V(G) there exist disjoint Xk, X~ ~ F such that vl ~ Xk and v i ~ X~.
Similarly, F is called a completely separating system of G if for any adjacent vi, v i ~ V(G) there exist Xk, Xz ~ F such that v~ ~ Xk, vj ~ X, vi ~ XI and vj ~ Xk.
Define F as a separating system of G if for any adjacent v~, v i ~ V(G) there is Xk ~ F containing exactly one of them.
Clearly, when G = (V, E) is a complete graph, the total separating system, the completely separating system and the separating system of G defined above become those corresponding to the set V(G) (see , [3] and [5] for the terminology).
Let -r(G), tr(G) and q~(G) denote the minimal cardinalities of a total separating system, a completely separating system and a separating system of G, respectively.
Given a digraph D =(V, A) with vertex-set V(D) and arc-set A(D), a family F ={X1, β’ β’., X,,} of subsets of V(D) is called a separating system of D if for any arc (v~,vi)~A(D) there is Xk~F such that v~C:Xk and vi~Xk. Let ~k(D) denote the minimal cardinality IF] of such a system of D.