A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas

Sample Entries from the Sixth Edition

19 January 1998, 17 July 1998

Compiled by Thomas Zaslavsky; manuscript prepared with Marge Pratt.

Department of Mathematical Sciences
Binghamton University
Binghamton, New York, U.S.A. 13902-6000

Some Definitions:

Gamma: A graph.
Sigma: A signed graph (Gamma, sigma): sigma is the edge signature.
balanced: Every polygon (i.e., graph circuit) has positive sign.
antibalanced: The negative of a balanced signed graph.
A(Sigma): The adjacency matrix of Sigma.

Robert P. Abelson and Milton J. Rosenberg
(1958a) Symbolic psycho-logic: a model of attitudinal cognition. Behavioral Sci. 3 (1958), 1-13.

Analyzes switching via Hadamard product with ``passive T-matrices''. Proposes frustration index (``complexity'', p. 12) l(Sigma) as measure of imbalance. (Cf. Harary (1959b).) Thm. 14: max l(Sigma), over all Sigma of order n, equals floor{(n - 1)²/4}. (Proof omitted. [Proved by Petersdorf (1966a) and Tomescu (1973a) for signed K_n's and hence for all signed simple graphs of order n.]) Defines an algebra for determining balance via per(I + A(Sigma)).
(PsS)(SG:A,B,sw,Fr)

M. Bánkfalvi and Zs. Bánkfalvi
(1968a) Alternating Hamiltonian circuit in two-coloured complete graphs. In: P. Erdös and G. Katona, eds., Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 11-18. Academic Press, New York, 1968.
MR 38 #2052. Zbl. 159, 542 (e: 159.54202).

Let Sigma be a bidirected -K_2n which has a coherent 2-factor. (``Coherent'' means that, at each vertex in the 2-factor, one edge is directed inward and the other outward.) Thm. 1: B has a Hamiltonian cycle (that is, a coherent Hamiltonian polygon) iff, for every k in {2, 3, ..., n-2}, s_k > k², where s_k := the sum of the k smallest indegrees and the k smallest outdegrees. Thm. 2: The number of k's for which s_k = k² equals the smallest number p of polygons in any coherent 2-factor of B. Moreover, the p values of k for which equality holds imply a partition of V into p vertex sets, each inducing B_i consisting of a bipartite [i.e., balanced] subgraph with a Hamiltonian cycle and in one color class only introverted edges, while in the other only extroverted edges. [Problem. Generalize these remarkable results to an arbitrary bidirected complete graph. The all-negative case will be these theorems; the all-positive case will give the smallest number of cycles in a covering by vertex-disjoint cycles of a tournament that has any such covering.]
(p:o:Polygons)

Richard A. Brualdi and Bryan L. Shader
(1995a) Matrices of Sign-Solvable Linear Systems. Cambridge Tracts in Math., Vol. 116. Cambridge University Press, Cambridge, Eng., 1995.
MR 97k:15001. Zbl. 833.15002.

Innumerable results and references on signed digraphs are contained herein.
(QM,SD:Sol,Sta)
(Exp,Ref,Alg)

P.J. Cameron, J.M. Goethals, J.J. Seidel, and E.E. Shult
(1976a) Line graphs, root systems, and elliptic geometry. J. Algebra 43 (1976), 305-327.
MR 56 #182. Zbl. 337.05142. Reprinted in Seidel (1991a), pp. 208-230.

The essential idea is that graphs with least eigenvalue lambda₁ >= -2 are represented by the angles of root systems. It follows that line graphs are so represented [since graphs are represented by subsets of A_n]. [Similarly, signed graphs with lambda₁ >= -2 are represented by the inner products of root systems. (See Vijayakumar et al.) These include the line graphs of signed graphs (see Zaslavsky (1984c, 19xxb)), since signed graphs are represented by B_n or C_n.]
(LG:sg:A,G,Sw)

A. Ehrenfeucht, T. Harju, and G. Rozenberg
(1997a) 2-Structures--A framework for decomposition and transformation of graphs. In: Grzegorz Rozenberg, ed., Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 1: Foundations, Ch. 6, pp. 401-478. World Scientific, Singapore, 1997.

A tutorial (with some new proofs). Sect. 6.7: ``Dynamic labeled 2-structures''. Sect. 6.8: ``Dynamic l 2-structures with variable domains''. Sect. 6.9: ``Quotients and plane trees''. Sect. 6.10: ``Invariants''.
(gg:sw:Exp,Ref)

Frank Harary
See also L.W. Beineke, A. Blass, F. Buckley, D. Cartwright, G. Chartrand, O. Frank, and P. Hage.
(1953a) On the notion of balance of a signed graph. Michigan Math. J. 2 (1953-1954), 143-146. Addendum, ibid., preceding p. 1.
MR 16, 733. Zbl. 56, 421 (e: 056.42103).

[The birth of signed graph theory. Although Thm. 3 was anticipated by König (1936a) (Thm. 11, for finite and infinite graphs) without the terminology of signs, here is the first recognition of the crucial fact that labelling edges by elements of a group--specifically, the sign group--can lead to a general theory.] The main theorem (Thm. 3) characterizes balanced signings as those for which there is a bipartition of the vertex set such that an edge is positive iff it lies within a part [I call this a Harary bipartition]. Thm. 2: A signing of a simple [or a loop-free] graph is balanced iff, for each pair of vertices, every path joining them has the same sign. Discussion of the number of nonisomorphic signed graphs with specific numbers of vertices and positive and negative edges.
(SG:B,E)

Shyi-Long Lee
See also I. Gutman.
(1989b) Net sign analysis of eigenvectors and eigenvalues of the adjacency matrices in graph theory. Bull. Inst. Chem., Academica Sinica No. 36 (1989), 93-104.

Expounds principally Lee, Lucchese, and Chu (1987a) and Lee and Gutman (1989a). Examples include all connected, simple graphs of order <= 4 and some aromatics.
(MG,SGw,Exp,Chem)

Steven R. Pagano
(1998a) Separability and Representability of Bias Matroids of Signed Graphs. Ph.D. thesis, Dept. of Mathematical Sciences, Binghamton University, 1998.

The bias matroid of every signed graph is representable over all fields with characteristic not = 2. For which signed graphs is it representable in characteristic 2 (and therefore representable over GF(4), by the theorem of Geoff Whittle, A characterization of the matroids representable over GF(3) and the rationals. J. Combin. Theory Ser. B 65 (1995), 222-261. MR 96m:05046.)? Solved (for signed graphs having vertex-disjoint negative polygons and hence nonregular matroid). There are two essentially different types: (i) Two balanced graphs joined by three independent unbalanced digons; (ii) cylindrical signed graphs with balanced graphs adjoined by 3-sums. [See notes on Seymour (1995a) for definition of (ii) and for Lovász's structure theorem in the case without vertex-disjoint negative polygons.]
(SG:M:Str)

Richard P. Stanley
See also P. Doubilet.
(1985a) Reconstruction from vertex-switching. J. Combin. Theory Ser. B 38 (1985), 132-138.
MR 86f:05096. Zbl. 572.05046.

From the 1-vertex switching deck (the multiset of isomorphism types of signed graphs resulting by separately switching each vertex) of Sigma = (K_n, sigma), Sigma can be reconstructed, provided that 4 does not divide n. The same for i-vertex switchings, provided that the Krawtchouk polynomial K_iⁿ(x) has no even zeros from 0 to n. When i = 1, the negative-subgraph degree sequence is always reconstructible. All done in terms of Seidel (graph) switching of unsigned simple graphs. [See Ellingham; Ellingham and Royle; Krasikov; Krasikov and Roditty for further developments. Problem 1. Generalize to signings of other highly symmetric graphs. Problem 2. Prove a similar theorem for switching of a bidirected K_n.]
(k:sw,TG)

Gérard Toulouse
See also B. Derrida and J. Vannimenus.
(1977a) Theory of the frustration effect in spin glasses: I. Commun. Phys. 2 (1977), 115-119.

(SG:Phys,Sw,B)

Thomas Zaslavsky
See also C. Greene, P. Hanlon, and P. Solé.
(1982b) Signed graph coloring. Discrete Math. 39 (1982), 215-228.
MR 84h:05050a. Zbl. 487.05027.

A ``proper k-coloring'' of Sigma partitions V into a special ``zero'' part, possibly void, that induces a stable subgraph, and up to k other parts (labelled from a set of k colors), each of which induces an antibalanced subgraph. A ``zero-free proper k-coloring'' is similar but without the ``zero'' part. [The suggestion is that the signed analog of a stable vertex set is one that induces an antibalanced subgraph. Problem. Use this insight to develop generalizations of stable-set notions, such as cliques and perfection. Example. Let alpha(Sigma), the ``antibalanced vertex set number'', be the largest size of an antibalance-inducing vertex set. Then alpha(Gamma) = alpha(+Gamma union -K_n.]
One gets two related chromatic polynomials. The chromatic polynomial, chi_Sigma(2k+1), counts all proper k-colorings; it is essentially the characteristic polynomial of the bias matroid. It can often be most easily computed via the zero-free chromatic polynomial, chi^*_Sigma(2k), which counts proper zero-free colorings: see (1982c).
(SG,GG:M,Col,N,Cov,O,G)