The Home Page of Signed, Gain, and Biased Graphs

by Thomas Zaslavsky

Why is this picture appropriate?*

Illustration by Hugh Thomson, courtesy of Henry Churchyard

Mathematical Bibliography

A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas
Dynamic Surveys in Combinatorics of the Electronic Journal of Combinatorics, #DS8.

Sixth(a) Edition (PDF, 625 KB), 1998 July 20. vi + 124 pp.
Copyright ©1996–1999 Thomas Zaslavsky.
Seventh Edition (PDF, 750 KB), 1999 September 22. vi + 151 pp.
Copyright ©1996–1999 Thomas Zaslavsky.
Preliminary Eighth Edition, 2012. vi + 316 pp., in PostScript (2.3 MB) or PDF (1.4 MB), or the Tex file (plain TeX, not LaTeX; 1.1 MB) with searchable topic codes.
Copyright ©1996–2012 Thomas Zaslavsky.

A signed graph is a graph with signs labelling its edges. A gain graph has elements of any group as edge labels (called "gains"), with the understanding that reversing the sense in which you traverse the edge will invert the gain. A bidirected graph has both ends of each edge directed independently; it can be regarded as an oriented signed graph.

This is a classified and copiously annotated list of all the publications (and suitable unpublished manuscripts, theses, etc.) of mathematical interest related to signed graphs, vertex-signed graphs, gain graphs, and bidirected graphs that I've been able to find and examine and enter into the list. It includes all or part of the literature of signed digraphs, Dowling lattices, combinatorics of root systems, parity of cycles and paths and max-cut problems (these concern all-negative signatures), generalized networks (networks with gains), qualitative matrix theory, quadratic pseudo-Boolean functions, dynamic labeled 2-structures, etc., etc., as well as selected publications on applications to social science (psychology, sociology, anthropology, economics) and natural science (physics, chemistry, biology--sorry, no geology or astronomy---yet).

The Bibliography is published as Dynamic Survey 8 in the Dynamic Surveys in Combinatorics of the Electronic Journal of Combinatorics. The published version (7th edition, 1999) is also available here:

Download in dvi (650 kilobytes) or PostScript (1100 kB) or Compressed PS (415 kB) format.
If you want PDF or the Tex file, see the Dynamic Surveys Web page.
If you want a printed copy mailed to you, please send me a message.

Topical subsets

These are specialized sub-bibliographies for selected subtopics. They are not necessarily up to date; each has its preparation date on the title page.

Chemistry: Möbius molecules. PostScript (191 KB).
Clusterability (23 Sept 2009). PDF (140 KB), PostScript (260 KB).
Clutters and 0/1 optimization. Not ready yet! PostScript (106 KB).
Colored-graph Tutte polynomials and knots. PostScript (251 KB).
Frustration index. PostScript (276 KB).
Line graphs of signed graphs. PostScript (218 KB).
Matroids: Matroids of signed, gain, and biased graphs; Matroidal families; Signed matroids. 24 March 2008. PDF (335 KB) or PostScript (450 KB).
Physics: Spin glasses, Ising models. PostScript (298 KB).
Signed graphs in surfaces. PostScript (195 KB).

Glossary

Glossary of Signed and Gain Graphs and Allied Areas.
Second Edition, 1998 September 16. 43 pp.
Copyright © 1998 Thomas Zaslavsky

The Glossary has terminology, definitions, and notation; it is a companion to the Bibliography. The second edition is published as Dynamic Survey 9 in the Dynamic Surveys in Combinatorics of the Electronic Journal of Combinatorics. I will send you a printed copy upon request.

The working version, which is slightly more up to date, is available here but in fewer formats. View the second edition in HTML (98 kilobytes), or download either
... a topically arranged version in dvi (124 kB) or PostScript (488 kB) or
... an incomplete alphabetical version in dvi (?? kB) or PostScript (?? kB).

Problem List

A miscellany of research problems in PostScript or (smaller) in HTML. At present, tiny (especially the HTML version). PS version is to be expanded.

Links

The Matroids page of Steve Pagano: painlessly learn what a matroid is and what it has to do with signed graphs.

The Hamiltonian Page, by Pablo Moscato. So what does this have to do with signed graphs? An alternating path or circle in an edge 2-colored graph can be treated as a coherent cycle in an oriented all-negative signed graph, and this leads to unexpected generalizations--or at least, new questions.

The hyperplane arrangement that represents
the bias matroid of ±K₃^o, the complete signed graph of order 3;
also known as the hyperplane arrangement corresponding to the root system B₃

Courtesy of John Stembridge

* Answer to the caption at head of page: We see one family, in the same room but hardly together. The family of signed, gain, and biased graphs is a lot like that. The Bibliography and Glossary are supposed to lead the family members to talk to one another. May they do so! (If you want to know more about the picture, click on it.)

Best Viewed With Any Browser

Home page. E-mail: zaslav@math.binghamton.edu