We characterise edges in mixed graphs that get a iabel 0 for every labeling with a constant index (index 0, respectively). We use this to investigate the magicity of disconnected mixed graphs with magic components. For the undirected case a necessary and sufficient condition is derived.
We consider only finite graphs, allowing loops and multiple edges. In a mixed graph directed as well as undirected edges may occur. Otherwise we will speak emphatically of a directed graph or an undirected graph. Let G be a mixed graph with point set P = (x1, . . . , xp} and edge set E = (m,, . . . , mq}. Its incidence matrix Ic is a p X 4 matrix (yij) with yij = +l (-1) if q is the endpoint (initial point) of the directed edge, non-loop mj, rij = 1 if Xi is one of the endpoints of the undirected edge, non-loop mj, yij = 2 if V+ is an undirected loop at xi, yij = 0 otherwise. We consider IG as a matrix over an infegral domain F. An element r = ( rI, . . . , rp) of FP is identified with the map r : P + F with r(q) = ri, and called an index-vector.
Likewise s E Fq is identified with a map s : E -+ F and called a labeling. We call s a labeling for r if I& = r': the 'index' ri of q one gets by adding the 'labels' of the edges having q as an endpoint and subtracting those of the edges having q as initial point, adding twice in case of an undirected loop. We trust that the reader who wants to restrict himself to undirected graphs or to F =Z will find no difficulties in doing so.
Let A E F. A labeling for (the index) A is a labeling for the index-vector (A, l . . , A). (Examples in Figs. 2 and3). S(G, F) is the F-module consisting of all such labelings, for any A. It is a union of cosets of Z(G, F), the F-module of labelings for the index 0. G is called semi-magic if there exists a labeling for an index A # 0 with F = Z, i.e. if S(G, Z) # Z(G, Z), magic if there is such a labeling with non-negative pairwise different labels (a magic labeling). The corresponding index is a magic index. The sum of the indices of the points is twice that of the labels of the undirected edges, so a magic index is positive, and a directed graph is not semi-magic. (For examples of magic labelings see Figs. 4 and5.