Compiled by
Mathematical Subject Classifications (1991): Primary 05-02, 05C99; Secondary 05B20, 05B25, 05B35, 05C10, 05C15, 05C20, 05C25, 05C30, 05C35, 05C38, 05C45, 05C50, 05C60, 05C65, 05C70, 05C75, 05C80, 05C85, 05C90, 05E25, 05E30, 06A07, 06A09, 05C10, 15A06, 15A15, 15A39, 15A99, 20B25, 20F55, 34C11, 51D20, 51E20, 52B12, 52B30, 52B40, 52C07, 68Q15, 68Q25, 68Q35, 68R10, 82B20, 82D30, 90A08, 90B10, 90C08, 90C27, 90C35, 90C60, 92D40, 92E10, 92H30, 92J10, 92K10, 94B25.
A signed graph is a graph whose edges are labeled by signs. This is a bibliography of signed graphs and related mathematics. I regard as fundamental the notion of balance of a circuit (sign product equals +, the sign group identity) and the vertex-edge incidence matrix (whose column for a negative edge has two +1's or two -1's, for a positive edge one +1 and one -1, the rest being zero). Hence I have included work on gain graphs (where the edge labels are taken from any group) and ``consistency'' in vertex-signed (or ``marked'') graphs (where the vertices are signed), and generalizable work on two-graphs (the set of unbalanced triangles of a signed complete graph) and on even and odd polygons and paths in graphs and digraphs.
Nevertheless, it was not always easy to decide what belongs. I have employed the following principles:
Only works with mathematical content are included, except for a few representative purely applied papers and surveys. I do try to include:
As for applications, besides works with appropriate mathematical content I include a few (not very carefully) selected representatives of less mathematical papers and surveys, either for their historical importance (e.g., Heider (1946a)) or as entrances to the applied literature (e.g., Taylor (1970a) and Wasserman and Faust (1993a) for psychosociology and Trinajstic (1983a) for chemistry). Particular difficulty is presented by spin glass theory in statistical physics--that is, Ising models and generalizations. Here one usually averages random signs and weights over a probability distribution; the problems and methods are rarely graph-theoretic, the topic is very specialized and hard to annotate properly, but it clearly is related to signed (and gain) graphs and suggests some interesting lines of graph-theoretic research. See M$eacute;zard, Parisi, and Virasoro (1987a) and citations in its annotation.
Plainly, judgment is required to apply these criteria. I have employed mine freely, taking account of suggestions from my colleagues. Still I know that the bibliography is far from complete, due to the quantity and even more the enormous range and dispersion of work in the relevant areas. I will continue to add both new and old works to future editions and I heartily welcome further suggestions.
There are certainly many errors, some of them egregious. For these I hand over responsibility to Sloth, Pride, Ambition, Envy, and Confusion. Corrections, however, will be gratefully accepted by me.
Authors' names are given usually in only one form, even should the name appear in different (but recognizably similar) forms on different publications. Journal abbreviations follow the style of Mathematical Reviews (MR) with minor `improvements'. Reviews and abstracts are cited from MR and its electronic form MathSciNet, from Zentralblatt für Mathematik (Zbl.) and its electronic form MATH Database (For early volumes, ``Zbl. VVV, PPP'' denotes printed volume and page; the electronic item number is ``(e VVV.PPPNN)''.), and occasionally from Chemical Abstracts (CA). A review marked (q.v.) has significance, possibly an insight, a criticism, or a viewpoint orthogonal to mine.
Some--not all--of the most fundamental works are marked with a dagger. This is a personal selection.
I try to describe the relevant content in a consistent terminology and notation, in the language of signed graphs despite occasional clumsiness (hoping that this will suggest generalizations), and sometimes with my [bracketed] editorial comments. I sometimes try also to explain idiosyncratic terminology, in order to make it easier to read the original item. Several of the annotations incorporate open research problems (of varying degrees of importance). I use these standard symbols:
I cannot name all the people who have contributed advice and criticism, but many of the annotations have benefited from suggestions by the authors or others and a number of items have been brought to my notice by helpful correspondents. I am very grateful to you all. Thanks also to the people who maintain the invaluable MR and Zbl. indices. However, I insist on my total responsibility for the final form of all entries, including such things as my restatement of results in signed or gain graphic language and, of course, all the praise and criticism (but not errors; see above) that they contain.
A code in lower case means the topic appears implicitly but not explicitly.
A suffix w on SG, SD, VS denotes signs used as weights, i.e., treated as the numbers +1 and -1, added, and (usually) the sum compared to 0.
In a string of codes a colon indicates subcategorization.
Last modified 1998 Sep 14