%% An AMSTeX source file for a 157 page document \input amstex \documentstyle{amsppt} \def\skipline{\vskip 10pt} \def\newline{\hfil\break} \magnification\magstep1 \mathsurround=1pt \def\spitem{\par\hangone\textputone} \def\Spitem{\par\hangtwo\textputtwo} \def\hangone{\hangindent 3\parindent} \def\hangtwo{\hangindent 5\parindent} \def\textputone#1{\noindent \hbox to 3\parindent{\hss#1\enspace}\ignorespaces} \def\textputtwo#1{\noindent \hbox to 5\parindent{\hss#1\enspace}\ignorespaces} \def\endspitem{\par\noindent} \def\phi{\varphi} \def\macron#1{{\accent 22 #1}} \chardef\oslash=\o \chardef\Oslash=\O \def\Par{\mathhexbox27B} \def\Sect{\mathhexbox278} \def\Sects{\Sect\Sect} \def\author#1{\noindent {\bf #1}} \def\authorspace{\nopagebreak} \def\authref{\spitem{}} \def\authrefspace{\vskip 4pt} \def\bibitem#1{\spitem{#1}} \def\annot#1{\vskip 1pt \Spitem{#1}} \def\annotctd#1{\vskip 2pt \Spitem{#1}} \def\codes#1{ \hfill ({\bf #1})} \def\codesctd#1{({\bf #1})} \def\itemspace{\vskip 4pt} \font\Bigfont = cmb10 at 15pt \font\smcp=cmcsc8 \headline={\ifnum\pageno<-1 {\smcp the electronic journal of combinatorics \#DS8\hfill\folio} \fi} \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics \#DS8\hfill\folio} \fi} \hyphenation{Birk-hauser Dries-sche Fest-schrift Kesz-thely Kraw-tchouk Mos-cow Motz-kin Przy-tyc-ka Przy-tyc-ki Schrij-ver Sing-a-pore Thistle-thwaite Tho-mas com-bi-na-tor-ics la-bel-ling la-bel-lings re-print-ed semi-switch-ing} \def\Problem{{\it Problem}} \def\Problems{{\it Problems}} \def\Question{{\it Question}} \def\Questions{{\it Questions}} \def\Conjecture{{\it Conjecture}} \def\Conjectures{{\it Conjectures}} \def\sic{[{\it sic}]} \def\urltwiddle{\~\,\!} \def\textb{{\text{\rm b}}} \def\cupdot{\cup\!\!\!\!\cdot} \def\sgn{\text{\rm sgn}\,} \def\dist{\text{\rm dist}} \def\ind{\!\!:\!\!} \def\supp{\text{\rm supp}\,} \def\Aut{\text{\rm Aut}\,} \def\Ts{\text{\rm Ts}} \def\Cox{\text{\rm Cox}} \def\rk{\text{\rm rk}\,} \def\Lat{\text{\rm Lat}\,} \def\Latb{\text{\rm Lat}^\textb\,} \def\Circ{\text{\rm Circ}\,} \def\GF{\text{\rm GF}} \def\PG{\text{\rm PG}} \def\inv{^{-1}} \def\transpose{^{\text{\rm T}}} \def\per{\text{\rm per}\,} \def\A{{\bf A}} \def\a{{\bf a}} \def\Alg{{\bf Alg}} \def\alg{{\bf alg}} \def\Appl{{\bf Appl}} \def\Autom{{\bf Aut}} \def\aut{{\bf aut}} \def\autom{{\bf aut}} \def\B{{\bf B}} \def\b{{\bf b}} \def\Bases{{\bf Bases}} \def\bases{{\bf bases}} \def\Bic{{\bf Bic}} \def\bic{{\bf bic}} \def\Col{{\bf Col}} \def\col{{\bf col}} \def\Chem{{\bf Chem}} \def\Cl{{\bf Cl}} \def\cl{{\bf cl}} \def\Cov{{\bf Cov}} \def\cov{{\bf cov}} \def\Cycles{{\bf Cycles}} \def\cycles{{\bf cycles}} \def\D{{\bf D}} \def\d{{\bf d}} \def\dual{{\bf d}} \def\E{{\bf E}} \def\e{{\bf e}} \def\EC{{\bf EC}} \def\ec{{\bf ec}} \def\ECol{{\bf ECol}} \def\ecol{{\bf ecol}} \def\Exp{{\bf Exp}} \def\Exr{{\bf Exr}} \def\Flows{{\bf Flows}} \def\flows{{\bf flows}} \def\Fr{{\bf Fr}} \def\fr{{\bf fr}} \def\G{{\bf G}} \def\g{{\bf g}} \def\GD{{\bf GD}} \def\gd{{\bf gd}} \def\Gen{{\bf Gen}} \def\gen{{\bf gen}} \def\GG{{\bf GG}} \def\gg{{\bf gg}} \def\ggraph{{\bf gg}} \def\GN{{\bf GN}} \def\gn{{\bf gn}} \def\Hyp{{\bf Hyp}} \def\I{{\bf I}} \def\imat{{\bf i}} \def\Indep{{\bf Indep}} \def\indep{{\bf indep}} \def\K{{\bf K}} \def\k{{\bf k}} \def\Knot{{\bf Knot}} \def\LG{{\bf LG}} \def\lg{{\bf lg}} \def\M{{\bf M}} \def\m{{\bf m}} \def\N{{\bf N}} \def\n{{\bf n}} \def\O{{\bf O}} \def\o{{\bf o}} \def\OG{{\bf OG}} \def\og{{\bf og}} \def\P{{\bf P}} \def\p{{\bf p}} \def\Paths{{\bf Paths}} \def\paths{{\bf paths}} \def\Polygons{{\bf Polygons}} \def\polygons{{\bf polygons}} \def\Phys{{\bf Phys}} \def\PsS{{\bf PsS}} \def\QM{{\bf QM}} \def\qm{{\bf qm}} \def\Rand{{\bf Rand}} \def\Ref{{\bf Ref}} \def\S{{\bf S}} \def\Sgnd{{\bf S}} \def\s{{\bf s}} \def\Sc{{\bf Sc}} \def\sc{{\bf sc}} \def\sgndc{{\bf sc}} \def\SD{{\bf SD}} \def\sd{{\bf sd}} \def\SDc{{\bf SDc}} \def\sdc{{\bf sdc}} \def\SDw{{\bf SDw}} \def\sdw{{\bf sdw}} \def\SG{{\bf SG}} \def\sg{{\bf sg}} \def\SGc{{\bf SGc}} \def\sgc{{\bf sgc}} \def\SGw{{\bf SGw}} \def\sgw{{\bf sgw}} \def\sh{{\bf sh}} \def\Sol{{\bf Sol}} \def\Sta{{\bf Sta}} \def\Str{{\bf Str}} \def\str{{\bf str}} \def\Sw{{\bf Sw}} \def\sw{{\bf sw}} \def\T{{\bf T}} \def\t{{\bf t}} \def\TG{{\bf TG}} \def\tg{{\bf tg}} \def\VS{{\bf VS}} \def\vs{{\bf vs}} \def\VSc{{\bf VSc}} \def\vsc{{\bf vsc}} \def\VSw{{\bf VSw}} \def\vsw{{\bf vsw}} \def\WD{{\bf WD}} \def\wdigr{{\bf wd}} \def\WG{{\bf WG}} \def\wg{{\bf wg}} \def\X{{\bf X}} \def\x{{\bf x}} \pageheight{9truein} \pagewidth{6.5truein} \let\mathmacloaded=L \NoBlackBoxes \baselineskip = 10pt \baselineskip = 10 pt \pageno = -1 \centerline {\Bigfont A Mathematical Bibliography of} \vskip 5 pt \centerline {\Bigfont Signed and Gain Graphs and Allied Areas} \vskip 30 pt \centerline {Compiled by} \centerline {Thomas Zaslavsky} \skipline \centerline{Manuscript prepared with} \centerline{Marge Pratt} \vskip 30 pt \centerline {Department of Mathematical Sciences} \centerline {Binghamton University} \centerline {Binghamton, New York, U.S.A\. 13902-6000} \skipline \centerline {{\it E-mail}: {\tt zaslav\@math.binghamton.edu}} \skipline\skipline \centerline {Submitted: March 19, 1998; Accepted: July 20, 1998.} \vskip 40 pt \centerline{\bf Seventh Edition} \centerline{1999 September 22} \skipline \noindent Mathematics Subject Classifications (2000): {\it Primary} 05-00, 05-02, 05C22; {\it Secondary} 05B20, 05B35, 05C07, 05C10, 05C15, 05C17, 05C20, 05C25, 05C30, 05C35, 05C38, 05C40, 05C45, 05C50, 05C60, 05C62, 05C65, 05C70, 05C75, 05C80, 05C83, 05C85, 05C90, 05C99, 05E25, 05E30, 06A07, 15A06, 15A15, 15A39, 15A99, 20B25, 20F55, 34C99, 51D20, 51D35, 51E20, 51M09, 52B12, 52C07, 52C35, 57M27, 68Q15, 68Q25, 68R10, 82B20, 82D30, 90B10, 90C08, 90C27, 90C35, 90C57, 90C60, 91B14, 91C20, 91D30, 91E10, 92D40, 92E10, 94B75. \vskip 80 pt \centerline {Colleagues:} \centerline {\it HELP!} \noindent If you have any suggestions whatever for items to include in this bibliography, or for other changes, please let me hear from you. Thank you. \vskip 10 pt {\eightrm \centerline {Copyright \copyright 1996, 1998, 1999 Thomas Zaslavsky} } \newpage \def\vertpair#1#2{\newline\noindent{\hbox to .2truein{#1}\textputone{#2}}} \centerline{\bf Index} \hbox{ \vtop{\hsize = 1.8truein \vertpair{A}{1} \vertpair{B}{8} \vertpair{C}{23} \vertpair{D}{34} \vertpair{E}{40} \vertpair{F}{44} \vertpair{G}{58} } \vtop{\hsize = 1.8truein \vertpair{H}{59} \vertpair{I}{71} \vertpair{J}{72} \vertpair{K}{75} \vertpair{L}{84} \vertpair{M}{90} \vertpair{N}{99} } \vtop{\hsize = 1.8truein \vertpair{O}{101} \vertpair{P}{102} \vertpair{Q}{109} \vertpair{R}{109} \vertpair{S}{113} \vertpair{T}{126} \vertpair{U}{133} } \vtop{\hsize = 1.8truein \vertpair{V}{133} \vertpair{W}{135} \vertpair{X}{139} \vertpair{Y}{139} \vertpair{Z}{140} }} \skipline\skipline \centerline {\bf Preface} \skipline A {\it signed graph} is a graph whose edges are labeled by signs. This is a bibliography of signed graphs and related mathematics. Several kinds of labelled graph have been called ``signed'' yet are mathematically very different. I distinguish four types: \item{$\bullet$} {\it Group-signed graphs}: the edge labels are elements of a $2$-element group and are multiplied around a polygon (or along any walk). Among the natural generalizations are larger groups and vertex signs. \item{$\bullet$} {\it Sign-colored graphs}, in which the edges are labelled from a two-element set that is acted upon by the sign group: $-$ interchanges labels, $+$ leaves them unchanged. This is the kind of ``signed graph'' found in knot theory. The natural generalization is to more colors and more general groups---or no group. \item{$\bullet$} {\it Weighted graphs}, in which the edge labels are the elements $+1$ and $-1$ of the integers or another additive domain. Weights behave like numbers, not signs; thus I regard work on weighted graphs as outside the scope of the bibliography---except (to some extent) when the author calls the weights ``signs''. \item{$\bullet$} Labelled graphs where the labels have no structure or properties but are called ``signs'' for any or no reason. Each of these categories has its own theory or theories, generally very different from the others, so in a logical sense the topic of this bibliography is an accident of terminology. However, narrow logic here leads us astray, for the study of true signed graphs, which arise in numerous areas of pure and applied mathematics, forms the great majority of the literature. Thus I regard as fundamental for the bibliography the notions of {\it balance} of a polygon (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); this has led me to include work on {\it gain graphs} (where the edge labels are taken from any group) and ``consistency'' in {\it vertex-signed graphs}, 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 entered, except for a few representative purely applied papers and surveys. I do try to include: \item{$\bullet$}Any (mathematical) work in which signed graphs are mentioned by name or signs are put on the edges of graphs, regardless of whether it makes essential use of signs. (However, due to lack of time and in order to maintain ``balance'' in the bibliography, I have included only a limited selection of items concerning binary clutters and postman theory, two-graphs, signed digraphs in qualitative matrix theory, and knot theory. For clutters, see Cornu\'ejols (20xxa) when it appears; for postman theory, A\. Frank (1996a). For two-graphs, see any of the review articles by Seidel. For qualitative matrix theory, see e.g\. Maybee and Quirk (1969a) and Brualdi and Shader (1995a). For knot theory there are uncountable books and surveys.) \item{$\bullet$}Any work in which the notion of balance of a polygon plays a role. Example: gain graphs. (Exception: purely topological papers concerning ordinary graph embedding.) \item{$\bullet$}Any work in which ideas of signed graph theory are anticipated, or generalized, or transferred to other domains. Examples: vertex-signed graphs; signed posets and matroids. \item{$\bullet$}Any mathematical structure that is an example, however disguised, of a signed or gain graph or generalization, and is treated in a way that seems in the spirit of signed graph theory. Examples: even-cycle and bicircular matroids; bidirected graphs; binary clutters (which are equivalent to signed binary matroids); some of the literature on two-graphs and double covering graphs. \item{$\bullet$}And some works that have suggested ideas of value for signed graph theory or that have promise of doing so in the future. 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\'ezard, 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. As Diedrich Knickerbocker says: \vskip 5pt \item{}{\eightrm Should any reader find matter of offense in this [bibliography], I should heartily grieve, though I would on no acount question his penetration by telling him he was mistaken, his good nature by telling him he was captious, or his pure conscience by telling him he was startled at a shadow. Surely when so ingenious in finding offense where none was intended, it were a thousand pities he should not be suffered to enjoy the benefit of his discovery.} \vskip 5pt Corrections, however, will be gratefully accepted by me. \newpage {\bf Bibliographical Data.} 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 {\it Mathematical Reviews} (MR) with minor `improvements'. Reviews and abstracts are cited from MR and its electronic form MathSciNet, from {\it Zentralblatt f\"ur Mathematik} (Zbl\.) and its electronic version (For early volumes, ``Zbl\. VVV, PPP'' denotes printed volume and page; the electronic item number is ``(e VVV.PPPNN)''.), and occasionally from {\it Chemical Abstracts} (CA) or {\it Computing Reviews} (CR). 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 \dag\dag; some almost as fundamental have a \dag. This is a personal selection. \skipline {\bf Annotations.} 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 problems (of widely varying degrees of importance and difficulty). I use these standard symbols: \skipline \spitem{$\Gamma$} is a graph (undirected), possibly allowing loops and multiple edges. It is normally finite unless otherwise indicated. \spitem{$\Sigma$} is a signed graph. Its vertex and edge sets are $V$ and $E$; its order is $n = |V|$. $E_+$, $E_-$ are the sets of positive and negative edges and $\Sigma_+$, $\Sigma_-$ are the corresponding spanning subgraphs (unsigned). \spitem{$[\Sigma]$} is the switching class of $\Sigma$. \spitem{$A(\ )$} is the adjacency matrix. \spitem{$\Phi$} is a gain graph. \spitem{$\Omega$} is a biased graph. \spitem{$l(\ )$} is the frustration index (= line index of imbalance). \spitem{$G(\ )$} is the bias matroid of a signed, gain, or biased graph. \spitem{$L(\ ),L_0(\ )$} are the lift and extended lift matroids. \skipline Some standard terminology (much more will be found in the {\it Glossary} (Zaslavsky 1998c)): \skipline \Spitem{polygon, circle:}The graph of a simple closed path, or its edge set. \Spitem{cycle:}In a digraph, a coherently directed polygon, i.e., ``dicycle''. More generally: in an oriented signed, gain, or biased graph, a matroid circuit (usually, of the bias matroid) oriented to have no source or sink. \skipline {\bf Acknowledgement.} 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 (and a special thank-you for creating our very own MSC classification: 05C22). 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. \newpage \centerline {\bf Subject Classification Codes} \skipline A code in {\it lower case} means the topic appears implicitly but not explicitly. A suffix {\bf w} on \S, \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$. A suffix {\bf c} on \SG, \SD, \VS\ denotes signs used as colors (often written as the numbers $+1$ and $-1$), usually permuted by the sign group. In a string of codes a colon precedes subtopics. A code may be refined through being suffixed by a parenthesised code, as \S(\M)\ denoting signed matroids (while \S:~\M\ would indicate matroids of signed objects; thus \S(\M):~\M\ means matroids of signed matroids). \vskip 10pt {\baselineskip = 10pt {\tenrm \spitem{\A} Adjacency matrix, eigenvalues. \spitem{\Alg} Algorithms. \spitem{\Appl} Applications other than (\Chem), (\Phys), (\PsS) (partial coverage). \spitem{\Autom} Automorphisms, symmetries, group actions. \spitem{\B} Balance (mathematical), cobalance. \spitem{\Bic} Bicircular matroids. \spitem{\Chem} Applications to chemistry (partial coverage). \spitem{\Cl} Clusterability. \spitem{\Col} Vertex coloring. \spitem{\Cov} Covering graphs, double coverings. \spitem{\D} Duality (graphs, matroids, or matrices). \spitem{\E} Enumeration of types of signed graphs, etc. \spitem{\EC} Even-cycle matroids. \spitem{\ECol} Edge coloring. \spitem{\Exp} Expository. \spitem{\Exr} Interesting exercises (in an expository work). \spitem{\Fr} Frustration (imbalance); esp\. frustration index (line index of imbalance). \spitem{\G} Connections with geometry, including toric varieties, complex complement, etc. \spitem{\GD} Digraphs with gains (or voltages). \spitem{\Gen} Generalization. \spitem{\GG} Gain graphs, voltage graphs, biased graphs; includes Dowling lattices. \spitem{\GN} Generalized or gain networks. (Multiplicative real gains.) \spitem{\Hyp} Hypergraphs with signs or gains. \spitem{\I} Incidence matrix, Kirchhoff matrix. \spitem{\K} Signed complete graphs. \spitem{\Knot} Connections with knot theory (sparse coverage if signs are purely notational). \spitem{\LG} Line graphs. \spitem{\M} Matroids and geometric lattices, chain-groups, flows. \spitem{\N} Numerical and algebraic invariants of signed graphs, etc. \spitem{\O} Orientations, bidirected graphs. \spitem{\OG} Ordered gains. \spitem{\P} All-negative or antibalanced signed graphs; parity-biased graphs. \spitem{\p} Includes problems on even or odd length of paths or polygons (partial coverage). \spitem{\Phys} Applications in physics (partial coverage). \spitem{\PsS} Psychological, sociological, and anthropological applications (partial coverage). \spitem{\QM} Qualitative (sign) matrices: sign stability, sign solvability, etc\. (sparse coverage). \spitem{\Rand} Random signs or gains, signed or gain graphs. \spitem{\Ref} Many references. \spitem{\S} Signed objects other than graphs and hypergraphs: mathematical properties. \spitem{\SD} Signed digraphs: mathematical properties. \spitem{\SG} Signed graphs: mathematical properties. \spitem{\Sol} Sign solvability, sign nonsingularity (partial coverage). \spitem{\Sta} Sign stability (partial coverage). \spitem{\Str} Structure theory. \spitem{\Sw} Switching of signs or gains. \spitem{\T} Topology applied to graphs; surface embeddings. (Not applications to topology.) \spitem{\TG} Two-graphs, graph (Seidel) switching (partial coverage). \spitem{\VS} Vertex-signed graphs (``marked graphs''); signed vertices and edges. \spitem{\WD} Weighted digraphs. \spitem{\WG} Weighted graphs. \spitem{\X} Extremal problems. \tenrm} } \newpage \pageno = 1 \baselineskip = 10pt \centerline {\smc A Mathematical Bibliography of} \centerline{\smc Signed and Gain Graphs and Allied Areas} \itemspace\itemspace\itemspace\itemspace \author{Robert P\. Abelson} \authorspace \authref See also M.J\. Rosenberg. \authrefspace \bibitem{1967a} Mathematical models in social psychology. In: Leonard Berkowitz, ed., {\it Advances in Experimental Social Psychology}, Vol\. 3, pp\. 1--54. Academic Press, New York, 1967. \annot{} \Sect II: ``Mathematical models of social structure.'' Part B: ``The balance principle.'' Reviews basic notions of balance and clusterability in signed (di)graphs and measures of degree of balance or clustering. Notes that signed $K_n$ is balanced iff $I + A = vv^{\text{\rm T}}$, $v = \pm 1$-vector. Proposes: degree of balance $= \lambda_{1}/n$, where $\lambda_{1} =$ largest eigenvalue of $I + A(\Sigma)$ and $n =$ order of the (di)graph. [Cf. Phillips (1967a).] Part C, 3: ``Clusterability revisited.'' \codes{\SG,~\SD:~\B,~\Cl,~\Fr,~\A} \itemspace \author{Robert P\. Abelson and Milton J\. Rosenberg} \authorspace \bibitem{\dag 1958a} Symbolic psycho-logic: a model of attitudinal cognition. {\it Behavioral Sci\.} 3 (1958), 1--13. \annot{} Basic formalism: the ``structure matrix'', an adjacency matrix $R(\Sigma)$ with entries $o, p, n$ [corresponding to $0, +1, -1$] for nonadjacency and positive and negative adjacency and $a$ for simultaneous positive and negative adjacency. Defines addition and multiplication of these symbols (p\. 8) so as to decide balance of $\Sigma$ via $\per(I + R(\Sigma))$. [See Harary, Norman, and Cartwright (1965a) for more on this matrix.] Analyzes switching, treated as Hadamard product of $R(\Sigma)$ with ``passive $T$-matrices'' [essentially, matrices obtained by switching the square all-$1$'s matrix]. Thm\. 11: Switching preserves balance. \annotctd{} Proposes (p\. 12) ``complexity'' [frustration index] $l(\Sigma)$ as measure of imbalance. [Cf\. Harary (1959b).] Thm\. 12: Switching preserves frustration index. Thm\. 14: $\max\, l(\Sigma)$, over all $\Sigma$ of order $n$, equals $\lfloor (n - 1)^2/4 \rfloor$. (Proof omitted. [Proved by Petersdorf (1966a) and Tomescu (1973a) for signed $K_n$'s and hence for all signed simple graphs of order $n$.]) \codes{\PsS}\codesctd{\SG:~\A,~\B,~\sw,~\Fr} \itemspace \author{B\. Devadas Acharya} \authorspace \authref See also M.K\. Gill. \authrefspace \bibitem{1973a} On the product of $p$-balanced and $l$-balanced graphs. {\it Graph Theory Newsletter} 2, No\. 3 (Jan., 1973), Results Announced No\. 1. \codes{\SG,~\VS:~\B} \itemspace \bibitem{1979a} New directions in the mathematical theory of balance in cognitive organizations. MRI Tech\. Rep\. No\. HCS/DST/409/76/BDA (Dec., 1979). Mehta Research Institute of Math\. and Math\. Physics, Allahabad, India, 1979. \codes{\SG,~\SD:~\B,~\A,~\Ref}\codesctd{\PsS:~\Exp,~\Ref} \itemspace \bibitem{1980a} Spectral criterion for cycle balance in networks. {\it J\. Graph Theory} 4 (1980), 1--11. MR 81e:05097(q.v.). Zbl\. 445.05066. \codes{\SD,~\SG:~\B,~\A} \itemspace \bibitem{1980b} An extension of the concept of clique graphs and the problem of $K$-convergence to signed graphs. {\it Nat\. Acad\. Sci\. Letters (India)} 3 (1980), 239--242. Zbl\. 491.05052. \codes{\SG:~\LG,~{\bf Clique~graph}} \itemspace \bibitem{1981a} On characterizing graphs switching equivalent to acyclic graphs. {\it Indian J\. Pure Appl\. Math}. 12 (1981), 1187-1191. MR 82k:05089. Zbl\. 476.05069. \annot{} Begins an attack on the problem of characterizing by forbidden induced subgraphs the simple graphs that switch to forests. Among them are $K_5$ and $C_n$, $n \geq 7$. \Problem. Find any others that may exist. [Forests that switch to forests are characterized by Hage and Harju (1998a).] \codes{\TG} \itemspace \bibitem{1982a} Connected graphs switching equivalent to their iterated line graphs. {\it Discrete Math\.} 41 (1982), 115--122. MR 84b:05078. Zbl\. 497.05052. \codes{\LG,~\TG} \itemspace \bibitem{1983a} Even edge colorings of a graph. {\it J\. Combin\. Theory Ser\. B} 35 (1983), 78--79. MR 85a:05034. Zbl\. 505.05032, (515.05030). \annot{} Find the fewest colors to color the edges so that in each polygon the number of edges of some color is even. [Possibly, inspired by \Sect 2 of Acharya and Acharya (1983a).] \codes{\b:~\Gen} \itemspace \bibitem{1983b} A characterization of consistent marked graphs. {\it Nat\. Acad\. Sci\. Letters (India)} 6 (1983), 431--440. Zbl\. 552.05052. \annot{} Converts a vertex-signed graph $(\Gamma, \mu)$ into a signed graph $\Sigma$ such that $(\Gamma, \mu)$ is consistent iff every polygon in $\Sigma$ is all-negative or has an even number of all-negative components. [See S.B\. Rao (1984a) and Hoede (1992a) for the definitive results on consistency.] \codes{\VS,~\SG:~\b} \itemspace \bibitem{1984a} Some further properties of consistent marked graphs. {\it Indian J\. Pure Appl\. Math\.} 15 (1984), 837--842. MR 86a:05101. Zbl\. 552.05053. \annot{} Notably: nicely characterizes consistent vertex-signed graphs in which the subgraph induced by negative vertices is connected. [Subsumed by S.B\. Rao (1984a).] \codes{\VS:~\b} \itemspace \bibitem{1984b} Combinatorial aspects of a measure of rank correlation due to Kendall and its relation to social preference theory. In: B.D. Acharya, ed., {\it Proceedings of the National Symposium on Mathematical Modelling} (Allahabad, 1982). M.R.I\. Lecture Notes in Appl\. Math\., 1. Mehta Research Institute of Math\. and Math\. Physics, Allahabad, India, 1984. \annot{} Includes an exposition of Sampathkumar and Nanjundaswamy (1973a). \codes{\SG:~\K:~\Exp} \itemspace \bibitem{1986a} An extension of Katai-Iwai procedure to derive balancing and minimum balancing sets of a social system. {\it Indian J\. Pure Appl\. Math\.} 17 (1986), 875--882. MR 87k:92037. Zbl\. 612.92019. \annot{} Expounds the procedure of Katai and Iwai (1978a). Proposes a generalization to those $\Sigma$ that have a certain kind of polygon basis. Construct a ``dual'' graph whose vertex set is a polygon basis supplemented by the sum of basic polygons. A ``dual'' vertex has sign as in $\Sigma$. Let $T =$ set of negative ``dual'' vertices. A $T$-join in the ``dual'', if one exists, yields a negation set for $\Sigma$. [A minimum $T$-join need not yield a minimum negation set. Indeed the procedure is unlikely to yield a minimum negation set (hence the frustration index $l(\Sigma)$) for all signed graphs, since it can be performed in polynomial time while $l(\Sigma)$ is NP-complete. \Questions. To which signed graphs is the procedure applicable? For which ones does a minimum $T$-join yield a minimum negation set? Do the latter include all those that forbid an interesting subdivision or minor (cf\. Gerards and Schrijver (1986a), Gerards (1988a, 1989a))?] \codes{\SG:~\Fr:~\Alg} \itemspace \author{B\. Devadas Acharya and Mukti Acharya [M.K\. Gill]} \authorspace \bibitem{1983a} A graph theoretical model for the analysis of intergroup stability in a social system. Manuscript, 1983. \annot{} The first half (most of \Sect 1) was improved and published as (1986a). \annotctd{} The second half (\Sects 2--3) appears to be unpublished. Given; a graph $\Gamma$, a vertex signing $\mu$, and a covering $\Cal F$ of $E(\Gamma)$ by cliques of size $\leq 3$. Define a signed graph $S$ by; $V(S) = \Cal F$ and $QQ' \in E(S)$ when at least half the elements of $Q$ or $Q'$ lie in $Q \cap Q'$; sign $QQ'$ negative iff there exist vertices $v \in Q \backslash Q'$, and $w \in Q' \backslash Q$ such that $\mu(v) \neq \mu(w)$. Suppose there is no edge $QQ'$ in which $|Q| = 3$, $|Q'| = 2$, and the two members of $Q \backslash Q'$ have differing sign. [This seems a very restrictive supposition.] Main result (Thm\. 7): $S$ is balanced. The definitions, but not the theorem, are generalized to multiple vertex signs $\mu$, general clique covers, and clique adjacency rules that differ slightly from that of the theorem. \codes{\GG,~\VS,~\SG:~\B} \itemspace \bibitem{1986a} New algebraic models of social systems. {\it Indian J\. Pure Appl\. Math\.} 17 (1986), 150--168. MR 87h:92087. Zbl\. 591.92029. \annot{} Four criteria for balance in an arbitrary gain graph. [See also Harary, Lindstrom, and Zetterstrom (1982a).] \codes{\GG:~\B,~\sw} \itemspace \author{B.D\. Acharya, M.K\. Gill, and G.A\. Patwardhan} \authorspace \bibitem{1984a} Quasicospectral graphs and digraphs. In: {\it Proceedings of the National Symposium on Mathematical Modelling} (Allahabad, 1982), pp\. 133--144. M.R.I\. Lecture Notes Appl\. Math\., 1. Mehta Research Institute of Math\. and Math\. Physics, Allahabad, 1984. MR 86c:05087. Zbl\. 556.05048. \annot{} A signed graph, or digraph, is ``cycle-balanced'' if every polygon, or every cycle, is positive. Graphs, or digraphs, are ``quasicospectral'' if they have cospectral signings, ``strictly quasicospectral'' if they are quasicospectral but not cospectral, ``strongly cospectral'' if they are cospectral and have cospectral cycle-unbalanced signings. There exist arbitrarily large sets of strictly quasicospectral digraphs, which moreover can be assumed strongly connected, weakly but not strongly connected, etc. There exist $2$ unbalanced strictly quasicospectral signed graphs; existence of larger sets is not unsolved. There exist arbitrarily large sets of nonisomorphic, strongly cospectral connected graphs; also, weakly connected digraphs, which moreover can be taken to be strongly connected, unilaterally connected, etc. Proofs, based on ideas of A.J\. Schwenk, are sketched. \codes{\SD,~\SG:~\A} \itemspace \author{Mukti Acharya [Mukhtiar Kaur Gill]} \authorspace \authref See also B.D\. Acharya and M.K\. Gill. \authrefspace \bibitem{1988a} Switching invariant three-path signed graphs. In: M.N\. Gopalan and G.A\. Patwardhan, eds., {\it Optimization, Design of Experiments and Graph Theory} (Bombay, 1986), pp\. 342--345. Indian Institute of Technology, Bombay, 1988. MR 90b:05102. Zbl\. 744.05054. \codes{\SG,~\Sw} \itemspace \author{L\. Adler and S\. Cosares} \authorspace \bibitem{1991a} A strongly polynomial algorithm for a special class of linear programs. {\it Oper\. Res\.} 39 (1991), 955--960. MR 92k:90042. Zbl\. 749.90048. \annot{} The class is that of the transshipment problem with gains. Along the way, a time bound on the uncapacitated, demands-only flows-with-gains problem. \codes{\GN:~\I(D),~\Alg} \itemspace \author{S.N\. Afriat} \authorspace \bibitem{1963a} The system of inequalities $a_{rs} > X_r - X_s$. {\it Proc\. Cambridge Philos\. Soc.} 59 (1963), 125--133. MR 25 \#5071. Zbl\. 118, 149 (e: 118.14901). \annot{} See also Roy (1959a). \codes{\GG:~\OG,~\Sw,~\b} \itemspace \bibitem{1974a} On sum-symmetric matrices. {\it Linear Algebra Appl\.} 8 (1974), 129--140. MR 48 \#11163. Zbl\. 281.15017. \codes{\GG:~\Sw,~\b} \itemspace \author{A.A\. Ageev, A.V\. Kostochka, and Z\. Szigeti} \authorspace \bibitem{1995a} A characterization of Seymour graphs. In: Egon Balas and Jens Clausen, eds., {\it Integer Programming and Combinatorial Optimization} (4th Internat\. IPCO Conf., Copenhagen, 1995, Proc.), pp\. 364--372. Lecture Notes in Computer Sci., Vol\. 920. Springer, Berlin, 1995. MR 96h:05157. \annot{} A Seymour graph satisfies with equality a general inequality between $T$-join size and $T$-cut packing. Thm.: A graph is not a Seymour graph iff it has a conservative $\pm 1$-weighting such that there are two polygons with total weight $0$ whose union is an antibalanced subdivision of $-K_n$ or $-Pr_3$ (the triangular prism). \codes{\SGw:~\Str,~\B,~\P} \itemspace \bibitem{1997a} A characterization of Seymour graphs. {\it J\. Graph Theory} 24 (1997), 357--364. MR 97m:05217. Zbl\. 970.24507. \annot{} Virtually identical to (1995a). \codes{\SGw:~\Str,~\B,~\P} \itemspace \author{J.K\. Aggarwal} \authorspace \authref See M\. Malek-Zavarei. \authrefspace \author{Ron Aharoni, Rachel Manber, and Bronislaw Wajnryb} \authorspace \bibitem{1990a} Special parity of perfect matchings in bipartite graphs. {\it Discrete Math\.} 79 (1990), 221--228. MR 91b:05140. Zbl\. 744.05036. \annot{} When do all perfect matchings in a signed bipartite graph have the same sign product? Solved. \codes{\sg:~\b,~\Alg}\codesctd{\qm:~\Sol} \itemspace \author{R\. Aharoni, R\. Meshulam, and B\. Wajnryb} \authorspace \bibitem{1995a} Group weighted matchings in bipartite graphs. {\it J\. Algebraic Combin\.} 4 (1995), 165--171. MR 96a:05111. Zbl\. 950.25380. \annot{} Given an edge weighting $w: E \to K$ where $K$ is a finite abelian group. Main topic: perfect matchings $M$ such that $\sum_{e \in M} w(e) = 0$ [I'll call them $0$-weight matchings]. (Also, in \Sect 2, $= c$ where $c$ is a constant.) Generalizes and extends Aharoni, Manber, and Wajnryb (1990a). Continued by Kahn and Meshulam (1998a). \codes{\WG} \annotctd{} Prop\. 4.1 concerns vertex-disjoint polygons whose total sign product is $+$ in certain signed digraphs. \codes{\SD} \itemspace \author{Ravindra K\. Ahuja, Thomas L\. Magnanti, and James B\. Orlin} \authorspace \bibitem{1993a} {\it Network Flows: Theory, Algorithms, and Applications}. Prentice Hall, Englewood Cliffs, N.J., 1993. MR 94e:90035. \annot{} \Sect 12.6: ``Nonbipartite cardinality matching problem''. Nicely expounds theory of blossoms and flowers (Edmonds (1965a), etc.). Historical notes and references at end of chapter. \codes{\p:~\o,~\Alg:~\Exp,~\Ref} \annotctd{} \Sect 5.5: ``Detecting negative cycles''; \Sect 12.7, subsection ``Shortest paths in directed networks''. Weighted arcs with negative weights allowed. Techniques for detecting negative cycles and, if none exist, finding a shortest path. \codes{\WD:~\OG,~\Alg:~\Exp} \annotctd{} Ch\. 16: ``Generalized flows''. Sect. 15.5: ``Good augmented forests and linear programming bases'', Thm\. 15.8, makes clear the connection between flows with gains and the bias matroid of the underlying gain graph. Some terminology: ``breakeven cycle'' = balanced polygon; ``good augmented forest'' = basis of the bias matroid, assuming the gain graph is connected and unbalanced. \codes{\GN:~\M(\Bases),~\Alg:~\Exp,~\Ref} \itemspace \author{Martin Aigner} \authorspace \bibitem{1979a} {\it Combinatorial Theory}. Grundl\. math\. Wiss., Vol\. 234. Springer-Verlag, Berlin, 1979. Reprinted: Classics in Mathematics. Springer-Verlag, Berlin, 1997. MR 80h:05002. Zbl\. 415.05001, 858.05001 (reprint). \annot{} In \Sect VII.1, pp\. 333--334 and Exerc\. 13--15 treat the Dowling lattices of $\GF(q)^{\times}$ and higher-weight analogs. \codes{\GG,~\GG(\Gen):~\M:~\N,~\Str} \itemspace \author{M\. A\u\i gner [Martin Aigner]} \authorspace \bibitem{1982a} {\it Kombinatornaya teoriya}. ``Mir'', Moscow, 1982. MR 84b:05002. \annot{} Russian translation of (1979a). Transl\. V.V\. Ermakov and V.N\. Lyamin. Ed\. and preface by G.P\. Gavrilov. \codes{\GG,~\GG(\Gen):~\M:~\N,~\Str} \itemspace \author{J\. Akiyama, D\. Avis, V\. Chv\'atal, and H\. Era} \authorspace \bibitem{\dag\dag 1981a} Balancing signed graphs. {\it Discrete Appl\. Math\.} 3 (1981), 227--233. MR 83k:05059. Zbl\. 468.05066. \annot{} Bounds for $D(\Gamma)$, the largest frustration index $l(\Gamma, \sigma)$ over all signings of a fixed graph $\Gamma$ (not necessarily simple) of order $n$ and size $m = |E|$. Main Thm.: $\frac 12 m - \sqrt{mn} \leq D(\Gamma) \leq \frac 12 m$. Thm\. 4: $D(K_{t,t}) \leq \frac 12 t^2 - c_0 t^{3/2}$, where $c_0$ can be taken $= \pi/480$. Probabilistic methods are used. Thus, Thm\. 2: Given $\Gamma$, Prob$(l(\Gamma, \sigma) > \frac 12 m - \sqrt{mn}) \geq 1 - (\frac 2e)^n$. Moreover, let $n_{\textb}(\Sigma)$ be the largest order of a balanced subgraph of $\Sigma$. Thm\. 5: Prob$(n_{\textb}(K_n, \sigma) \geq k) \leq {n \choose k}/2^{k \choose 2}$. (The problem of evaluating $n - n_{\textb}$ was raised by Harary; see (1959b).) Finally, Thm\. 1: If $\Sigma$ has vertex-disjoint balanced induced subgraphs with $m'$ edges, then $l(\Sigma) \leq \frac 12(m-m')$. [See Poljak and Turz\'{\i}k (1982a), Sol\'e and Zaslavsky (1994a) for more on $D(\Gamma)$; Brown and Spencer (1971a), Gordon and Witsenhausen (1972a) for $D(K_{t,t})$; Harary, Lindstr\"om, and Zetterstr\"om (1982a) for a result similar to Thm\. 1.] \codes{\SG:~\Fr,~\Rand} \itemspace \author{S\. Alexander and P\. Pincus} \authorspace \bibitem{1980a} Phase transitions of some fully frustrated models. {\it J\. Phys\. A: Math\. Gen\.} 13, No\. 1 (1980), 263--273. \codes{\P:~\Phys} \itemspace \author{Kazutoshi Ando and Satoru Fujishige} \authorspace \bibitem{1996a} On structures of bisubmodular polyhedra. {\it Math\. Programming} 74 (1996), 293--317. MR 97g:90102. Zbl\. 855.68107. \codes{\sg:~\O} \itemspace \author{Kazutoshi Ando, Satoru Fujishige, and Takeshi Naitoh} \bibitem{1997a} Balanced bisubmodular systems and bidirected flows. {\it J\. Oper\. Res\. Soc\. Japan} 40 (1997), 437--447. MR 98k:05073. Zbl\. 970.61830. \annot{} A balanced bisubmodular system corresponds to a bidirected graph that is balanced. The ``flows'' are arbitrary capacity-constrained functions, not satisfying conservation at a vertex. \codes{\sg:~\O,~\B} \itemspace \author{Kazutoshi Ando, Satoru Fujishige, and Toshio Nemoto} \authorspace \bibitem{1996a} Decomposition of a bidirected graph into strongly connected components and its signed poset structure. {\it Discrete Appl\. Math\.} 68 (1996), 237--248. MR 97c:05096. Zbl. 960.53208. \codes{\sg:~\O} \itemspace \bibitem{1996b} The minimum-weight ideal problem for signed posets. {\it J\. Oper\. Res\. Soc\. Japan} 39 (1996), 558-565. MR 98j:90084. Zbl\. 874.90188. \codes{\sg:~\O} \itemspace \author{Thomas Andreae} \authorspace \bibitem{1978a} Matroidal families of finite connected nonhomeomorphic graphs exist. {\it J\. Graph Theory} 2 (1978), 149--153. MR 80a:05160. Zbl\. 401.05070. \annot{} Partially anticipates the ``count'' matroids of graphs (see Whiteley (1996a)). \codes{\Bic,~\EC:~\Gen} \itemspace \author{St\. Antohe and E\. Olaru} \authorspace \bibitem{1981a} Singned graphs homomorphism \sic. [Signed graph homomorphisms.] {\it Bul\. Univ\. Galati Fasc\. II Mat\. Fiz\. Mec\. Teoret.} 4 (1981), 35--43. MR 83m:05057. \annot{} A ``congruence'' is an equivalence relation $R$ on $V(\Sigma)$ such that no negative edge is within an equivalence class. The quotient $\Sigma/R$ has the obvious simple underlying graph and signs $\bar{\sigma}(\bar{x}\bar{y}) = \sigma(xy)$ [which is ambiguous]. A signed-graph homomorphism is a function $f: V_1 \to V_2$ that is a sign-preserving homomorphism of underlying graphs. [This is inconsistent, since the sign of edge $f(x)f(y)$ can be ill defined. The defect might perhaps be remedied by allowing multiple edges with different signs or by passing entirely to multigraphs.] The canonical map $\Sigma \to \Sigma/R$ is such a homomorphism. Composition of homomorphisms is well defined and associative; hence one has a category ${\text{\rm Graph}}^{\text{\rm sign}}$. The categorial product is $\prod_{i \in I} \Sigma_i :=$ Cartesian product of the $|\Sigma_i|$ with the component-wise signature $\sigma((\ldots, u_i, \dots)(\ldots, v_i, \dots)) := \sigma_i(u_iv_i)$. Some further elementary properties of signed-graph homomorphisms and congruences are proved. [The paper is hard to interpret due to mathematical ambiguity and grammatical and typographical errors.] \codes{\SG} \itemspace \author{Katsuaki Aoki} \authorspace \authref See M\. Iri. \authrefspace \author{Juli\'an Ar\'aoz, William H\. Cunningham, Jack Edmonds, and Jan Green-Kr\'otki} \authorspace \bibitem{1983a} Reductions to $1$-matching polyhedra. Proc\. Sympos\. on the Matching Problem: Theory, Algorithms, and Applications (Gaithersburg, Md., 1981). {\it Networks} 13 (1983), 455--473. MR 85d:90059. Zbl\. 525.90068. \annot{} The ``minimum-cost capacitated $b$-matching problem in a bidirected graph $B$'' is to minimize $\sum_e c_ex_e$ subject to $0 \leq x \leq u \in \{0, 1, \ldots, \infty\}^E$ and $I(B)x = b \in \Bbb Z^V$. The paper proves, by reduction to the ordinary perfect matching problem, Edmonds and Johnson's (1970a) description of the convex hull of feasible solutions. \codes{\sg:~\O:~\I,~\Alg,~\G} \itemspace \author{Dan Archdeacon} \authorspace \bibitem{1995a} Problems in topological graph theory. Manuscript, 1995. WorldWideWeb URL (2/98) http://www.emba.uvm.edu/\urltwiddle archdeac/papers/papers.html \annot{} A compilation from various sources and contributors, updated every so often. ``The genus sequence of a signed graph'', p\. 10: A conjecture due to \v{S}ir\'a\v{n} (?) on the demigenus range (here called ``spectrum'' [though unrelated to matrices]) for orientation embedding of $\Sigma$, namely, that the answer to Question 1 under \v{S}ir\'a\v{n} (1991b) is affirmative. \codes{\SG:~\T} \itemspace \bibitem{1996a} Topological graph theory: a survey. Surveys in Graph Theory (Proc., San Francisco, 1995). {\it Congressus Numer\.} 115 (1996), 5--54. Updated version: WorldWideWeb URL (2/98) http://www.emba.uvm.edu/\urltwiddle archdeac/papers/papers.html MR 98g:05044. Zbl\. 897.05026. \annot{} \Sect 2.5 describes orientation embedding (called ``signed embedding'' [although there are other kinds of signed embedding]) and switching (called ``sequence of local switches of sense'') of signed graphs with rotation systems. \Sect 5.5, ``Signed embeddings'', briefly mentions \v{S}ir\'a\v{n} (1991b), \v{S}ir\'a\v{n} and \v{S}koviera (1991a), and Zaslavsky (1993a, 1996a). \codes{\SG:~\T:~\Exp} \itemspace \author{Dan Archdeacon and Jozef \v{S}ir\'a\v{n}} \authorspace \bibitem{1998a} Characterizing planarity using theta graphs. {\it J\. Graph Theory} 27 (1998), 17--20. MR 98j:05055. Zbl\. 887.05016. \annot{} A ``claw'' consists of a vertex and three incident half edges. Let $C$ be the set of claws in $\Gamma$ and $T$ the set of theta subgraphs. Fix a rotation of each claw. Call $t \in T$ an ``edge'' with endpoints $c, c'$ if $t$ contains $c$ and $c'$; sign it $+$ or $-$ according as $t$ can or cannot be embedded in the plane so the rotations of its trivalent vertices equal the ones chosen for $c$ and $c'$. This defines, independently (up to switching) of the choice of rotations, the ``signed triple graph'' $T^{\pm}(\Gamma)$. Theorem: $\Gamma$ is planar iff $T^{\pm}(\Gamma)$ is balanced. \codes{\SG,~\Sw} \itemspace \author{Srinivasa R\. Arikati and Uri N\. Peled} \authorspace \bibitem{1993a} A linear algorithm for the group path problem on chordal graphs. {\it Discrete Appl\. Math\.} 44 (1993), 185--190. MR 94h:68084. Zbl\. 779.68067. \annot{} Given a graph with edges weighted from a group. The weight of a path is the product of its edge weights in order (not inverted, as with gains). Problem: to determined whether between two given vertices there is a chordless path of given weight. This is NP-complete in general but for chordal graphs there is a fast algorithm (linear in $(|E|+|V|)\cdot(\text{group order})$). [\Question. What if the edges have gains rather than weights?] \codes{\WG:~\p(\Gen):~\Alg} \itemspace \bibitem{1996a} A polynomial algorithm for the parity path problem on perfectly orientable graphs. {\it Discrete Appl\. Math\.} 65 (1996), 5--20. MR 96m:05120. Zbl\. 854.68069. \annot{} Problem: Does a given graph contain an induced path of specified parity between two prescribed vertices? A polynomial-time algorithm for certain graphs. (Cf. Bienstock (1991a).) [\Problem. Generalize to paths of specified sign in a signed graph.] \codes{\p:~\Alg}\codesctd{\Ref} \itemspace \author{Esther M\. Arkin and Christos H\. Papadimitriou} \authorspace \bibitem{1985a} On negative cycles in mixed graphs. {\it Oper\. Res\. Letters} 4 (1985), 113--116. MR 87h:68061. Zbl\. 585.05017. \codes{\WG:~\OG} \itemspace \author{E.M\. Arkin, C.H\. Papadimitriou, and M\. Yannakakis} \authorspace \bibitem{1991a} Modularity of cycles and paths in graphs. {\it J\. Assoc\. Comput\. Mach.} 38 (1991), 255--274. MR 92h:68068. Zbl\. 799.68146. \annot{} Modular poise gains in digraphs (gain $+1$ on each oriented edge). \codes{\gg:~\B} \itemspace \author{Christos A\. Athanasiadis} \authorspace \bibitem{1996a} Characteristic polynomials of subspace arrangements and finite fields. {\it Adv\. Math\.} 122 (1996), 193--233. \annot{} See Headley (1997a) for definitions of the Shi arrangements. Here the characteristic polynomials of these and other arrangements are evaluated combinatorially. \Sect 3: ``The Shi arrangements''. \Sect 4: ``The Linial arrangement'': this represents $\Latb (K_n, \phi_1)$ (see Stanley (1996a) for notation). \Sect 5: ``Other interesting hyperplane arrangements'', treats: the arrangement representing $\Latb L\cdot K_n$ where $L = \{-k, \ldots, k-1, k\}$, which is the semilattice of $k$-composed partitions (see Zaslavsky (20xxh), also Edelman and Reiner (1996a)) and several generalizations, including to arbitrary sign-symmetric gain sets $L$ and to Weyl analogs; also, an antibalanced analog of the $A_n$ Shi arrangment (Thm\. 5.4); and more. \codes{\sg,~\gg:~\G,~\M,~\N} \itemspace \bibitem{1997a} A class of labeled posets and the Shi arrangement of hyperplanes. {\it J\. Combin\. Theory Ser\. A} 80 (1997), 158--162. MR 98d:05008. Zbl\. 970.66662. \annot{} The Shi arrangement of hyperplanes [of type $A_{n-1}$] represents $\Latb \Phi$ where $\Phi = (K_n, \phi_0) \cup (K_n, \phi_1)$ (see Stanley (1996a) for notation). \codes{\gg:~\G,~\M,~\N} \itemspace \bibitem{1998a} On free deformations of the braid arrangement. {\it European J\. Combin\.} 19 (1998), 7--18. \annot{} The arrangements considered are the subarrangements of the projectivized Shi arrangements of type $A_{n-1}$ that contain $A_{n-1}$. Thms\. 4.1 and 4.2 characterize those that are free or supersolvable. Arrangements representing the extended lift matroid $L_0(\Phi)$ where $\Phi = \bigcup_{i=1-a}^a (K_n, \phi_i)$ and $a \geq 1$ ($a = 1$ giving the Shi arrangement), and a mild generalization, are of use in the proof (see Stanley (1996a) for notation). \codes{\gg:~\G,~\M,~\N} \itemspace \bibitem{20xxa} Deformations of Coxeter hyperplane arrangements and their characteristic polynomials. Submitted. \itemspace \author{David Avis} \authorspace \authref See J\. Akiyama. \authrefspace \author{Constantin P\. Bachas} \authorspace \bibitem{1984a} Computer-intractibility of the frustration model of a spin glass. {\it J\. Physics A} 17 (1984), L709--L712. MR 85j:82043. \annot{} The frustration index decision problem on signed (3-dimensional) cubic lattice graphs is NP-complete. [Proof is incomplete; completed and improved by Green (1987a).] [Cf\. Barahona (1982a).] \codes{\SG:~\Fr:~\Alg} \itemspace \author{G\. David Bailey} \authorspace \bibitem{20xxa} Inductively factored signed-graphic arrangements of hyperplanes. Submitted. \annot{} Continues Edelman and Reiner (1994a). \codes{\SG:~\G,~\M} \itemspace \author{V\. Balachandran} \authorspace \bibitem{1976a} An integer generalized transportation model for optimal job assignment in computer networks. {\it Oper\. Res\.} 24 (1976), 742--759. MR 55 \#12068. Zbl\. 356.90028. \codes{\GN:~\M(\bases)} \itemspace \author{V\. Balachandran and G.L\. Thompson} \authorspace \bibitem{1975a} An operator theory of parametric programming for the generalized transportation problem: I. Basic theory. II. Rim, cost and bound operators. III. Weight operators. IV. Global operators. {\it Naval Res\. Logistics Quart.} 22 (1975), 79--100, 101--125, 297--315, 317--339. MR 52 \#\#2595, 2596, 2597, 2598. Zbl\. 331.90048, 90049, 90050, 90051. \codes{\GN:~\M} \itemspace \author{Egon Balas} \authorspace \bibitem{1966a} The dual method for the generalized transportation problem. {\it Management Sci\.} 12 (1966), No\. 7 (March, 1966), 555--568. MR 32 \#7232. Zbl\. 142, 166 (e: 142.16601). \codes{\GN:~\M(\bases)} \itemspace \bibitem{1981a} Integer and fractional matchings. In: P\. Hansen, ed., {\it Studies on Graphs and Discrete Programming}, pp\. 1--13. North-Holland Math\. Stud., 59. Ann\. Discrete Math\., 11. North-Holland, Amsterdam, 1981. MR 84h:90084. \annot{} Linear (thus ``fractional'', meaning half-integral) vs\. integral programming solutions to maximum matching. The difference of their maxima = $\frac 12$(max number of matching-separable vertex-disjoint odd polygons). Also noted (p\. 12): (max) fractional matchings in $\Gamma$ correspond to (max) matchings in the double covering graph of $-\Gamma$. [\Question. Does this lead to a definition of maximum matchings in signed graphs?] \codes{\p,~\o:~\I,~\G,~\Alg,~\cov} \itemspace \author{E\. Balas and P.L\. Ivanescu [P.L\. Hammer]} \authorspace \bibitem{1965a} On the generalized transportation problem. {\it Management Sci\.} 11 (1965), No\. 1 (Sept., 1964), 188--202. MR 30 \#4599. Zbl\. 133, 425 (e: 133.42505). \codes{\GN:~\M,~\B} \itemspace \author{K\. Balasubramanian} \authorspace \bibitem{1988a} Computer generation of characteristic polynomials of edge-weighted graphs, heterographs, and directed graphs. {\it J\. Computational Chem\.} 9 (1988), 204--211. \annot{} Here a ``signed graph'' means, in effect, an acyclically oriented graph $D$ along with the antisymmetric adjacency matrix $A_{\pm}(D) = A(+D \cup -D^*)$, $D^*$ being the converse digraph. [That is, $A_{\pm}(D) = A(D) - A(D)^{\text t}$. The ``signed graphs'' are just acyclic digraphs with an antisymmetric adjacency matrix and, correspondingly, what we may call the `antisymmetric characteristic polynomial'.] Proposes an algorithm for the polynomial. Observes in some examples a relationship between the characteristic polynomial of $\Gamma$ and the antisymmetric characteristic polynomial of an acyclic orientation. \codes{\SD,~\wg:~\A:~\N:~\Alg,~\Chem} \itemspace \bibitem{1991a} Comments on the characteristic polynomial of a graph. {\it J\. Computational Chem\.} 12 (1991), 248--253. MR 92b:92057. \annot{} Argues (heuristically) that a certain algorithm is superior to another, in particular for the antisymmetric polynomial defined in (1988a). \codes{\SD:~\A:~\N:~\Alg} \itemspace \bibitem{1992a} Characteristic polynomials of fullerene cages. {\it Chemical Physics Letters} 198 (1992), 577--586. \annot{} Computed for graphs of six different cages of three different orders, in both ordinary and ``signed'' (see (1988a)) versions. Observes a property of the ``signed graph'' polynomials [which is due to antisymmetry, as explained by P.W\. Fowler (Comment on ``Characteristic polynomials of fullerene cages''. {\it Chemical Physics Letters} 203 (1993), 611--612)]. \codes{\SD:~\A:~\N:~\Chem} \itemspace \bibitem{1994a} Are there signed cospectral graphs? {\it J\. Chemical Information and Computer Sciences} 34 (1994), 1103--1104. \annot{} The ``signed graphs'' are as in (1988a). Simplified contents: It is shown by example that the antisymmetric characteristic polynomials of two nonisomorphic acyclic orientations of a graph (see (1988a)) may be equal or unequal. [Much smaller examples are provided by P.W\. Fowler (Comment on ``Characteristic polynomials of fullerene cages''. {\it Chemical Physics Letters} 203 (1993), 611--612).] [\Question. Are there examples for which the underlying (di)graphs are nonisomorphic?] [For cospectrality of other kinds of signed graphs, see Acharya, Gill, and Patwardhan (1984a) (signed $K_n$'s).] \codes{\SD:~\A:~\N} \itemspace \author{R\. Balian, J.M\. Drouffe, and C\. Itzykson} \authorspace \bibitem{1975a} Gauge fields on a lattice. II. Gauge-invariant Ising model. {\it Phys\. Rev\. D} 11 (1975), 2098--2103. \codes{\SG:~\Phys,~\Sw,~\B} \itemspace \author{J{\oslash}rgen Bang-Jensen and Gregory Gutin} \authorspace \bibitem{1997a} Alternating cycles and paths in edge-coloured multigraphs: A survey. {\it Discrete Math\.} 165/166 (1997), 39--60. MR 98d:05080. Zbl\. 876.05057. \annot{} A rich source for problems on bidirected graphs. An edge 2-coloration of a graph becomes an all-negative bidirection by taking one color class to consist of introverted edges and the other to consist of extroverted edges. An alternating path becomes a coherent path; an alternating polygon becomes a coherent polygon. [{\it General Problem.} Generalize to bidirected graphs the results on edge 2-colored graphs mentioned in this paper. (See esp\. \Sect 5.) \Question. To what digraph properties do they specialize by taking the underlying signed graph to be all positive?] [See e.g. B\'ankfalvi and B\'ankfalvi (1968a) (q.v.), Bang-Jensen and Gutin (1998a), Das and Rao (1983a), Grossman and H\"aggqvist (1983a), Mahadev and Peled (1995a), Saad (1996a).] \codes{\p:~\o:~\Paths,~\Polygons} \itemspace \bibitem{1998a} Alternating cycles and trails in $2$-edge-colored complete multigraphs. {\it Discrete Math\.} 188 (1998), 61--72. MR 99g:05072. \annot{} The longest coherent trail, having degrees bounded by a specified degree vector, in a bidirected all-negative complete multigraph that satisfies an extra hypothesis. Generalization of Das and Rao (1983a) and Saad (1996a), thus ultimately of Thm\. 1 of B\'ankfalvi and B\'ankfalvi (1968a) (q.v.). Also, a polynomial-time algorithm. \codes{\p:~\o:~\Paths,~\Alg} \itemspace \author{M\. B\'ankfalvi and Zs\. B\'ankfalvi} \authorspace \bibitem{1968a} Alternating Hamiltonian circuit in two-coloured complete graphs. In: P\. Erd\H{o}s and G\. Katona, eds., {\it Theory of Graphs} (Proc\. Colloq., Tihany, 1966), pp\. 11--18. Academic Press, New York, 1968. MR 38 \#2052. Zbl\. 159, 542 (e: 159.54202). \annot{} 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 coherent Hamiltonian polygon iff, for every $k \in \{2, 3, \ldots, n-2\}$, $s_k > k^2$, 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^2$ 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 coherent Hamiltonian polygon 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.] [See Bang-Jensen and Gutin (1997a) for further developments on alternating walks.] \codes{\p:~\o:~\Polygons} \itemspace \author{Zs\. B\'ankfalvi} \authorspace \authref See M\. B\'ankfalvi. \authrefspace \author{C\. Bankwitz} \authorspace \bibitem{1930a} \"Uber die Torsionszahlen der alternierenden Knotes. {\it Math\. Ann\.} 103 (1930), 145--161. \annot{} Introduces the sign-colored graph of a link diagram. [Further work by numerous writers, e.g., S\. Kinoshita {\it et al\.} and esp\. Kauffman (1989a) and successors.] \codes{\Knot:~\SGc} \itemspace \author{Francisco Barahona} \authorspace \bibitem{1981a} Balancing signed toroidal graphs in polynomial-time. Unpublished manuscript, 1981. \annot{} Given a $2$-connected $\Sigma$ whose underlying graph is toroidal, polynomial-time algorithms are given for calculating the frustration index $l(\Sigma)$ and the generating function of switchings $\Sigma^{\mu}$ by $|E_-(\Sigma^{\mu})|$. The technique is to solve a Chinese postman ($T$-join) problem in the toroidal dual graph, $T$ corresponding to the frustrated face boundaries. Generalizes (1982a). [See (1990a), p\. 4, for a partial description.] \codes{\SG:~\Fr,~\Alg} \itemspace \bibitem{1982a} On the computational complexity of Ising spin glass models. {\it J\. Phys\. A: Math\. Gen.} 15 (1982), 3241--3253. MR 84c:82022. \annot{} The frustration-index problem, that is, minimization of $|E_-(\Sigma^{\eta})|$ over all switching functions $\eta : V \to \{\pm 1\}$, for signed planar and toroidal graphs and subgraphs of $3$-dimensional grids. Analyzed structurally, in terms of perfect matchings in a modified dual graph, and algorithmically. The last is NP-hard, even when the grid has only 2 levels; the former are polynomial-time solvable even with weighted edges. Also, the problem of minimizing $|E_-(\Sigma^{\eta})| + \sum_v \eta(v)$ for planar grids (``$2$-dimensional problem with external magnetic field''), which is NP-hard. (This corresponds to adding an extra vertex, positively adjacent to every vertex.) \codes{\SG:~\Phys,~\Fr,~\Fr(\Gen):~\D,~\Alg} \itemspace \bibitem{1982b} Two theorems in planar graphs. Unpublished manuscript, 1982. \codes{\SG:~\Fr} \itemspace \bibitem{1990a} On some applications of the Chinese Postman Problem. In: B\. Korte, L\. Lov\'asz, H.J\. Pr\"omel, and A\. Schrijver, eds., {\it Paths, Flows and VLSI-Layout}, pp\. 1--16. Algorithms and Combinatorics, Vol\. 9. Springer-Verlag, Berlin, 1990. MR 92b:90139. Zbl\. 732.90086. \annot{} Section 2: ``Spin glasses.'' \codes{\SG:~\Phys,~\Fr:~\Exp} \annotctd{} Section 5: ``Max cut in graphs not contractible to $K_5$,'' pp\. 12--13. \codes{\sg:~\fr:~\Exp} \itemspace \bibitem{1990b} Planar multicommodity flows, max cut, and the Chinese Postman problem. In: William Cook and Paul D\. Seymour, eds., {\it Polyhedral Combinatorics} (Proc\. Workshop, 1989), pp\. 189--202. DIMACS Ser\. Discrete Math\. Theoret\. Computer Sci., Vol\. 1. Amer\. Math\. Soc\. and Assoc\. Comput\. Mach., Providence, R.I., 1990. MR 92g:05165. Zbl\. 747.05067. \annot{} Negative cutsets, where signs come from a network with real-valued capacities. Dual in the plane to negative polygons. See \Sect 2. \codes{\SG:~\D:~\B,~\Alg} \itemspace \author{Francisco Barahona and Adolfo Casari} \authorspace \bibitem{1988a} On the magnetisation of the ground states in two-dimensional Ising spin glasses. {\it Comput\. Phys\. Comm.} 49 (1988), 417--421. MR 89d:82004. Zbl\. 814.90132. \codes{\SG:~\Fr:~\Alg} \itemspace \author{Francisco Barahona, Martin Gr\"otschel, and Ali Ridha Mahjoub} \authorspace \bibitem{1985a} Facets of the bipartite subgraph polytope. {\it Math\. Oper\. Res\.} 10 (1985), 340--358. MR 87a:05123a. Zbl\. 578.05056. \annot{} The polytope $P_B(\Gamma)$ is the convex hull in $\Bbb R^E$ of incidence vectors of bipartite edge sets. Various types of and techniques for generating facet-defining inequalities, thus partially extending the description of $P_B(\Gamma)$ from the weakly bipartite case (Gr\"otschel and Pulleyblank (1981a)) in which all facets are due to edge and odd-polygon constraints. [Some can be described best via signed graphs; see Poljak and Turz\'{\i}k (1987a).] [A brief expository treatment of the polytope appears in Poljak and Tuza (1995a).] \codes{\sg:~\p:~\fr:~\G} \itemspace \author{Francisco Barahona and Enzo Maccioni} \authorspace \bibitem{1982a} On the exact ground states of three-dimensional Ising spin glasses. {\it J\. Phys\. A: Math\. Gen.} 15 (1982), L611--L615. MR 83k:82044. \annot{} Discusses a 3-dimensional analog of Barahona, Maynard, Rammal, and Uhry (1982a). (Here there may not always be a combinatorial LP optimum; hence LP may not completely solve the problem.) \codes{\SG:~\Phys,~\Fr,~\Alg} \itemspace \author{Francisco Barahona and Ali Ridha Mahjoub} \authorspace \bibitem{1986a} On the cut polytope. {\it Math\. Programming} 36 (1986), 157--173. MR 88d:05049. Zbl\. 616.90058. \annot{} Call $P_{\text{\rm BS}}(\Sigma)$ the convex hull in $\Bbb R^E$ of incidence vectors of negation sets (or ``balancing [edge] sets'') in $\Sigma$. Finding a minimum-weight negation set in $\Sigma$ corresponds to a maximum cut problem, whence $P_{\text{\rm BS}}(\Sigma)$ is a linear transform of the cut polytope $P_{\text{\rm C}}(|\Sigma|)$, the convex hull of cuts. Conclusions follow about facet-defining inequalities of $P_{\text{\rm BS}}(\Sigma)$. See \Sect 5: ``Signed graphs''. \codes{\SG:~\Fr:~\G} \itemspace \bibitem{1989a} Facets of the balanced (acyclic) induced subgraph polytope. {\it Math\. Programming Ser\. B} 45 (1989), 21--33. MR 91c:05178. Zbl\. 675.90071. \annot{} The ``balanced induced subgraph polytope'' $P_{\text{\rm BIS}}(\Sigma)$ is the convex hull in $\Bbb R^V$ of incidence vectors of vertex sets that induce balanced subgraphs. Conditions are studied under which certain inequalities of form $\sum_{i \in Y} x_i \leq f(Y)$ define facets of this polytope: in particular, $f(Y) =$ max\. size of balance-inducing subets of $Y$, $f(Y) = 1$ or $2$, $f(Y) = |Y| - 1$ when $Y = V(C)$ for a negative polygon $C$, etc. \codes{\SG:~\Fr:~\G,~\Alg} \itemspace \bibitem{1994a} Compositions of graphs and polyhedra. I: Balanced induced subgraphs and acyclic subgraphs. {\it SIAM J\. Discrete Math\.} 7 (1994), 344--358. MR 95i:90056. Zbl\. 802.05067. \annot{} More on $P_{\text{\rm BIS}}(\Sigma)$ (see (1989a)). A balance-inducing vertex set in $\pm\Gamma =$ a stable set in $\Gamma$. [See Zaslavsky (1982b) for a different correspondence.] Thm\. 2.1 is an interesting preparatory result: If $\Sigma = \Sigma_1 \cup \Sigma_2$ where $\Sigma_1 \cap \Sigma_2 \cong \pm K_k$, then $P_{\text{\rm BIS}}(\Sigma) = P_{\text{\rm BIS}}(\Sigma_1) \cap P_{\text{\rm BIS}}(\Sigma_2)$. The main result is Thm\. 2.2: If $\Sigma$ has a $2$-separation into $\Sigma_1$ and $\Sigma_2$, the polytope is the projection of the intersection of polytopes associated with modifications of $\Sigma_1$ and $\Sigma_2$. \Sect 5: ``Compositions of facets'', derives the facets of $P_{\text{\rm BIS}}(\Sigma)$. \codes{\SG:~\G,~\WG,~\Alg} \itemspace \author{F\. Barahona, R\. Maynard, R\. Rammal, and J.P\. Uhry} \authorspace \bibitem{1982a} Morphology of ground states of two-dimensional frustration model. {\it J\. Phys\. A: Math\. Gen.} 15 (1982), 673--699. MR 83c:82045. \annot{} \Sect 2: ``The frustration model as the Chinese postman's problem'', describes how to find the frustration index $l(-\Sigma) = \min_{\eta} |E_-(\Sigma^{\eta})|$ (over all switching functions $\eta$) of a signed planar graph by solving a Chinese postman ($T$-join) problem in the planar dual graph, $T$ corresponding to the frustrated face boundaries. [This was solved independently by Katai and Iwai (1978a).] The postman problem is solved by linear programming, in which there always is a combinatorial optimum: see \Sect 3: ``Solution of the frustration problem by duality: rigidity''. Of particular interest are vertex pairs, esp\. edges, for which $\eta(v)\eta(w)$ is the same for every ``ground state'' (i.e., minimizing $\eta$); these are called ``rigid''. \Sect 5: ``Results'' (of numerical experiments) has interesting discussion. [Barahona (1981a) generalizes to signed toroidal graphs.] \annotctd{} In the preceding one minimizes $f_0(\eta) = \sum_E \sigma(vw)\eta(v)\eta(w)$. More general problems discussed are (1) allowing positive edge weights (due to variable bond strengths); (2) minimizing $f_0(\eta) + c \sum_V \eta(v)$, with $c \neq 0$ because of an external magnetic field. Then one cannot expect the LP to have a combinatorial optimum. \codes{\SG:~\Phys,~\Fr,~\Fr(\Gen),~\Alg} \itemspace \author{F\. Barahona and J.P\. Uhry} \authorspace \bibitem{1981a} An application of combinatorial optimization to physics. {\it Methods Oper\. Res\.} 40 (1981), 221--224. Zbl\. 461.90080. \codes{\SG:~\Phys,~\Fr:~\Exp} \itemspace \author{J\. Wesley Barnes} \authorspace \authref See P.A\. Jensen. \authrefspace \author{Lowell Bassett, John Maybee, and James Quirk} \authorspace \bibitem{1968a} Qualitative economics and the scope of the correspondence principle. {\it Econometrica} 36 (1968), 544--563. MR 38 \#5456. Zbl\. (e: 217.26802). \annot{} Lemma 3: A square matrix with every diagonal entry negative is sign-nonsingular iff every cycle is negative in the associated signed digraph. Thm\. 4: A square matrix with negative diagonal is sign-invertible iff all cycles are negative and the sign of any (open) path is determined by its endpoints. And more. \codes{\QM:~\Sol,~\Sta:~\sd} \itemspace \author{Vladimir Batagelj} \authorspace \bibitem{1990a} [Closure of the graph value matrix.] (In Slovenian. English summary.) {\it Obzornik Mat\. Fiz\.} 37 (1990), 97--104. MR 91f:05058. Zbl\. 704.05035. \codes{\SG:~\A,~\B,~\Cl} \itemspace \bibitem{1994a} Semirings for social networks analysis. {\it J\. Math\. Sociology} 19 (1994), 53--68. Zbl\. 827.92029. \codes{\SG:~\A,~\B,~\Cl} \itemspace \author{M\. Behzad and G\. Chartrand} \authorspace \bibitem{1969a} Line-coloring of signed graphs. {\it Elem\. Math\.} 24 (1969), 49--52. MR 39 \#5415. Zbl\. 175, 503 (e: 175.50302). \codes{\SG:~\LG:~\Cl} \itemspace \author{[L.] W\. Beineke and F\. Harary} \authorspace \bibitem{1966a} Binary matrices with equal determinant and permanent. {\it Studia Sci\. Math\. Hungar.} 1 (1966), 179--183. MR 34 \#7397. Zbl\. (e: 145.01505). \codes{\SD} \itemspace \author{Lowell W\. Beineke and Frank Harary} \authorspace \bibitem{1978a} Consistency in marked digraphs. {\it J\. Math\. Psychology} 18 (1978), 260--269. MR 80d:05026. Zbl\. 398.05040. \annot{} A digraph with signed vertices is ``consistent'' (that is, every cycle has positive sign product) iff its vertices have a bipartition so that every arc with a positive tail lies within a set but no arc with a negative tail does so. (The reason is that a strongly connected digraph with vertex signs can be regarded as edge-signed and the bipartition criterion for balance can be applied.) A corollary: the digraphs that have consistent vertex signs are characterized. \codes{\VS} \itemspace \bibitem{1978b} Consistent graphs with signed points. {\it Riv\. Mat\. Sci\. Econom\. Social\.} 1 (1978), 81--88. MR 81h:05108. Zbl\. 493.05053. \annot{} A graph with signed vertices is ``consistent'' if every polygon has positive sign product. Elementary results, but a characterization of consistent vertex-signed graphs is presented as an open problem. For a good solution see Hoede (1992a); Rao (1984a) had found a more complicated solution. \codes{\VS} \itemspace \author{Jacques B\'elair, Sue Ann Campbell, and P\. van den Driessche} \authorspace \bibitem{1996a} Frustration, stability, and delay-induced oscillations in a neural network model. {\it SIAM J\. Appl\. Math\.} 56 (1996), 245--255. MR 96j:92003. Zbl\. 840.92003. \annot{} The signed digraph of a square matrix is ``frustrated'' if it has a negative cycle. Somewhat simplified: frustration is necessary for there to be oscillation caused by intraneuronal processing delay. \codes{\SD:~\QM,~\Ref} \itemspace \author{A\. Bellacicco and V\. Tulli} \authorspace \bibitem{1996a} Cluster identification in a signed graph by eigenvalue analysis. In: {\it Matrices and Graphs: Theory and Applications to Economics} (full title {\it Proceedings of the Conferences on Matrices and Graphs: Theory and Applications to Economics}) (Brescia, 1993, 1995), pp\. 233--242. World Scientific, Singapore, 1996. MR 99h:00029 (book). Zbl\. 914.65146. \annot{} Signed digraphs (``spin graphs'') are defined. The main concepts---``dis\-sim\-i\-lar\-ity'', ``balance'', and ``cluster''---do not involve signs. Eigenvalues are mentioned. [This may be an announcement. There are no proofs. It is hard to be sure what is being said.] \codes{\SD:~\A} \itemspace \author{Joachim von Below} \authorspace \bibitem{1994a} The index of a periodic graph. {\it Results Math\.} 25 (1994), 198--223. MR 95e:05081. Zbl\. 802.05054. \annot{} Here a periodic graph [of dimension $m$] is defined as a connected graph $\Gamma = \tilde\Psi$ where $\Psi$ is a finite $\Bbb Z^m$-gain graph with gains contained in $\{\bold 0, \bold b_i, \bold b_i - \bold b_j\}$. ($\bold b_1, \ldots, \bold b_m$ are the unit basis vectors of $\Bbb Z^m$.) Let us call such a $\Psi$ a small-gain base graph for $\Gamma$. Any $\tilde\Phi$, where $\Phi$ is a finite $\Bbb Z^m$-gain graph, has a small-gain base graph $\Psi$; thus this definition is equivalent to that of Collatz (1978a). The ``index'' $I(\Gamma)$, analogous to the largest eigenvalue of a finite graph, is the spectral radius of $A(||\Psi||)$ (here written $A(\Gamma, N)$) for any small-gain base graph of $\Gamma$. The paper contains basic theory and the lower bound $L_m = \inf \{I(\Gamma) : \Gamma {\text{\rm\ is $m$-dimensional}}\}$, where $1 = L_1, \sqrt{9/2} = L_2 \leq L_3 \leq \ldots$. \codes{\GG(\Cov):~\A} \itemspace \author{Edward A\. Bender and E\. Rodney Canfield} \authorspace \bibitem{1983a} Enumeration of connected invariant graphs. {\it J\. Combin\. Theory Ser\. B} 34 (1983), 268--278. MR 85b:05099. Zbl\. 532.05036. \annot{} \Sect 3: ``Self-dual signed graphs,'' gives the number of $n$-vertex graphs that are signed, vertex-signed, or both; connected or not; self-isomorphic by reversing edge and/or vertex signs or not, for all $n \leq 12$. Some of this appeared in Harary, Palmer, Robinson, and Schwenk (1977a). \codes{\SG,~\VS:~\E} \itemspace \author{Riccardo Benedetti} \authorspace \bibitem{1998a} A combinatorial approach to combings and framings of $3$-manifolds. In: A\. Balog, G.O.H\. Katona, A\. Recski, and D\. Sa'sz, eds., {\it European Congress of Mathematics} (Budapest, 1996), Vol\. I, pp\. 52--63. Progress in Math\., Vol\. 168. Birkh\"auser, Basel, 1998. MR * Zbl\. 905.57018. \annot{} \Sect 8, ``Spin manifolds'', hints at a use for decorated signed graphs in the structure theory of spin $3$-manifolds. \codes{\sg:~\Appl:~\Exp} \itemspace \author{Curtis Bennett and Bruce E\. Sagan} \authorspace \bibitem{1995a} A generalization of semimodular supersolvable lattices. {\it J\. Combin\. Theory Ser\. A} 72 (1995), 209--231. MR 96i:05180. Zbl\. 831.06003. \annot{} To illustrate the generalization, most of the article calculates the chromatic polynomial of $\pm K_n^{(k)}$ (called $\Cal{DB}_{n,k}$; this has half edges at $k$ vertices), builds an ``atom decision tree'' for $k = 0$, and describes and counts the bases of $G(\pm K_n^{(k)})$ (called $\Cal D_n$) that contain no broken circuits. \codes{\SG:~\M,~\N,~\col} \itemspace \author{M.K\. Bennett, Kenneth P\. Bogart, and Joseph E\. Bonin} \authorspace \bibitem{1994a} The geometry of Dowling lattices. {\it Adv\. Math\.} 103 (1994), 131--161. MR 95b:05050. Zbl\. 814.51003. \codes{\gg:~\M,~\G} \itemspace \author{Moussa Benoumhani} \authorspace \itemspace \bibitem{1996a} On Whitney numbers of Dowling lattices. {\it Discrete Math\.} 159 (1996), 13--33. MR 98a:06005. Zbl\. 861.05004. \codes{\gg:~\M:~\N} \itemspace \bibitem{1997a} On some numbers related to Whitney numbers of Dowling lattices. {\it Adv\. Appl\. Math\.} 19 (1997), 106--116. MR 98f:05004. Zbl\. 876.05001. \annot{} Generating polynomials and infinite generating series for multiples of Whitney numbers of the second kind, analogous to usual treatments of Stirling numbers. \codes{\gg:~\M:~\N} \itemspace \bibitem{1999a} Log-concavity of Whitney numbers of Dowling lattices. {\it Adv\. Appl\. Math\.} 22 (1999), 186--189. \annot{} Logarithmic concavity of Whitney numbers of the second kind is deduced by proving that their generating polynomial has only real zeros. [Cf\. Dur (1986a).] \codes{\gg:~\M:~\N} \itemspace \author{C\. Benzaken} \authorspace \authref See also P.L\. Hammer. \authrefspace \author{C. Benzaken, S.C\. Boyd, P.L\. Hammer, and B\. Simeone} \authorspace \bibitem{1983a} Adjoints of pure bidirected graphs. Proc\. Fourteenth Southeastern Conf\. on Combinatorics, Graph Theory and Computing (Boca Raton, Fla., 1983). {\it Congressus Numer\.} 39 (1983), 123--144. MR 85e:05077. Zbl\. 537.05024. \codes{\sg:~\O:~\LG} \itemspace \author{Cl\. Benzaken, P.L\. Hammer, and B\. Simeone} \authorspace \bibitem{1980a} Some remarks on conflict graphs of quadratic pseudo-boolean functions. In: L\. Collatz, G\. Meinardus, and W\. Wetterling, eds., {\it Konstruktive Methoden der finiten nichtlinearen Optimierung} (Tagung, Oberwolfach, 1980), pp\. 9--30. Internat\. Ser\. of Numerical Math\., 55. Birkh\"auser, Basel, 1980. MR 83e:90096. Zbl\. 455.90063. \codes{\p:~\fr}\codesctd{\sg:~\O:~\LG} \itemspace \author{C\. Benzaken, P.L\. Hammer, and D\. de Werra} \authorspace \bibitem{1985a} Threshold characterization of graphs with Dilworth number two. {\it J\. Graph Theory} 9 (1985), 245--267. MR 87d:05135. Zbl\. 583.05048. \codes{\SG:~\B} \itemspace \author{Claude Berge and A\. Ghouila-Houri} \authorspace \bibitem{1962a} {\it Programmes, jeu et reseaux de transport}. Dunod, Paris, 1962. MR 33 \#1137. Zbl\. (e: 111.17302). \annot{} $2^e$ partie, Ch\. IV, \S2: ``Les reseaux de transport avec multiplicateurs.'' Pp\. 223--229. \codes{\GN:~\imat} \itemspace \bibitem{1965a} {\it Programming, Games and Transportation Networks}. Methuen, London; Wiley, New York, 1965. MR 33 \#7114. \annot{} English edition of (1962a). \annotctd{} Part II, 10.2: ``The transportation network with multipliers.'' Pp\. 221--227. \codes{\GN:~\imat} \itemspace \bibitem{1967a} {\it Programme, Spiele, Transportnetze.} B.G\. Teubner Verlagsgesellschaft, Leipzig, 1967, 1969. MR 36 \#1195. Zbl\. (e: 183.23905, 194.19803). \annot{} German edition(s) of (1962a). \codes{\GN:~\imat} \itemspace \author{Joseph Berger, Bernard P\. Cohen, J\. Laurie Snell, and Morris Zelditch, Jr.} \authorspace \bibitem{1962a} {\it Types of Formalization in Small Group Research}. Houghton Mifflin, Boston, 1962. \annot{} See Ch\. 2: ``Explicational models.'' \codes{\PsS}\codesctd{\SG:~\B}\codesctd{\Ref} \itemspace \author{Abraham Berman and B\. David Saunders} \authorspace \bibitem{1981a} Matrices with zero line sums and maximal rank. {\it Linear Algebra Appl\.} 40 (1981), 229--235. MR 82i:15029. Zbl\. 478.15013. \codes{\QM,~\sd:~\o} \itemspace \author{Gora Bhaumik} \authorspace \authref See P.A\. Jensen. \authrefspace \author{V.N\. Bhave} \authorspace \authref See E\. Sampathkumar. \authrefspace \author{I\. Bieche, R\. Maynard, R\. Rammal, and J.P\. Uhry} \authorspace \bibitem{1980a} On the ground states of the frustration model of a spin glass by a matching method of graph theory. {\it J\. Phys\. A: Math\. Gen.} 13 (1980), 2553--2576. MR 81g:82037. \codes{\SG:~\Phys,~\Fr,~\Alg} \itemspace \author{Dan Bienstock} \authorspace \bibitem{1991a} On the complexity of testing for odd holes and induced odd paths. {\it Discrete Math\.} 90 (1991), 85--92. MR 92m:68040a. Zbl\. 753.05046. Corrigendum. {\it ibid\.} 102 (1992), 109. MR 92m.68040b. Zbl\. 760.05080. \annot{} Given a graph. Problem 1: Is there an odd hole on a particular vertex? Problem 2: Is there an odd induced path joining two specified vertices? Problem 3: Is every pair of vertices joined by an odd-length induced path? All three problems are NP-complete. [Obviously, one can replace the graph by a signed graph and ``odd length'' by ``negative'' and the problems remain NP-complete.] \codes{\P:~\Polygons,~\Paths:~\Alg} \itemspace \author{Norman Biggs} \authorspace \bibitem{1974a} {\it Algebraic Graph Theory}. Cambridge Math\. Tracts, No\. 67. Cambridge Univ\. Press, London, 1974. MR 50 \#151. Zbl\. 284.05101. \annot{} Ch\. 19: ``The covering graph construction.'' Especially see Exercise 19A: ``Double coverings.'' These define what we might call the canonical covering graphs of gain graphs. \codes{\SG,~\GG:~\Cov,~\Autom,~\b} \itemspace \bibitem{1993a} {\it Algebraic Graph Theory}. Second edn\. Cambridge Math\. Library, Cambridge Univ\. Press, Cambridge, Eng., 1993. MR 95h:05105. Zbl\. 797.05032. \annot{} As in (1974a), but Exercise 19A has become Additional Result 19a. \codes{\SG,~\GG:~\Cov,~\Autom,~\b} \itemspace \bibitem{1997a} International finance. In: Lowell W\. Beineke and Robin J\. Wilson, eds\., {\it Graph Connections: Relationships between Graph Theory and other Areas of Mathematics}, Ch\. 17, pp\. 261--279. The Clarendon Press, Oxford, 1997. \annot{} A model of currency exchange rates in which no cyclic arbitrage is possible, hence the rates are given by a potential function. [That is, the exchange-rate gain graph is balanced, with the natural consequences.] Assuming cash exchange without accumulation in any currency, exchange rates are determined. [See also Ellerman (1984a). \codes{\GG,~\gn:~\B:~\Exp} \itemspace \author{Robert E\. Bixby} \authorspace \bibitem{1981a} Hidden structure in linear programs. In: Harvey J\. Greenberg and John S\. Maybee, eds., {\it Computer-Assisted Analysis and Model Simplification} (Proc\. Sympos., Boulder, Col., 1980), pp\. 327--360; discussion, pp\. 397--404. Academic Press, New York, 1981. MR 82g:00016 (book). Zbl. 495.93001 (book). \codes{\GN} \itemspace \author{Anders Bj\"orner and Bruce E\. Sagan} \authorspace \bibitem{1996a} Subspace arrangements of type $B_n$ and $D_n$. {\it J\. Algebraic Combin\.} 5 (1996), 291--314. MR 97g:52028. Zbl\. 864.57031. \annot{} They study lattices $\Pi_{n,k,h}$ (for $0 < h \leq k \leq n$) consisting of all spanning subgraphs of $\pm K_n^{\circ}$ that have at most one nontrivial component $K$, for which $K$ is complete and $|V(K)| \geq k$ if $K$ is balanced, $K$ is induced and $|V(K)| \geq h$ if $K$ is unbalanced (also a generalization). Characteristic polynomial, homotopy and homology of the order complex, cohomology of the real complement. \codes{\SG:~\G,~\M(\Gen):~\N,~\col} \itemspace \author{Anders Bj\"orner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and G\"unter M\. Ziegler} \authorspace \bibitem{1993a} {\it Oriented Matroids.} Encyclop\. Math\. App\., Vol\. 46. Cambridge University Press, Cambridge, Eng\., 1993. MR 95e:52023. Zbl\. 773.52001. \annot{} The adjacency graph of bases of an oriented matroid is signed, using circuit signatures, to make the ``signed basis graph''. See \Sect 3.5, ``Basis orientations and chirotopes'', pp\. 132--3. \codes{\M:~\SG} \itemspace \author{Andreas Blass} \authorspace \bibitem{1995a} Quasi-varieties, congruences, and generalized Dowling lattices. {\it J\. Algebraic Combin\.} 4 (1995), 277--294. MR 96i:06012. Zbl\. 857.08002. Errata. {\it Ibid.} 5 (1996), 167. \annot{} Treats the generalized Dowling lattices of Hanlon (1991a) as congruence lattices of certain quasi-varieties, in order to calculate characteristic polynomials and generalizations. \codes{\M(\gg):~\Gen:~\N} \itemspace \author{Andreas Blass and Frank Harary} \authorspace \bibitem{1982a} Deletion versus alteration in finite structures. {\it J\. Combin\. Inform\. System Sci\.} 7 (1982), 139--142. MR 84d:05087. Zbl\. 506.05038. \annot{} The theorem that deletion index = negation index of a signed graph (Harary (1959b)) is shown to be a special case of a very general phenomenon involving hereditary classes of ``partial choice functions''. Another special case: deletion index = alteration index of a gain graph [an immediate corollary of Harary, Lindst\"om, and Zetterstr\"om (1982a), Thm\. 2]. \codes{\SG,~\GG:~\B,~\Fr} \itemspace \author{Andreas Blass and Bruce Sagan} \authorspace \bibitem{1997a} M\"obius functions of lattices. {\it Adv\. Math\.} 127 (1997), 94--123. MR 98c:06001. Zbl\. 970.32977. \annot{} \Sect 3: ``Non-crossing $B_n$ and $D_n$''. Lattices of noncrossing signed partial partitions. Atoms of the lattices are defined as edge fibers of the signed covering graph of $\pm K_n^{\circ}$, thus corresponding to edges of $\pm K_n^{\circ}$. [The ``half edges'' are perhaps best regarded as negative loops.] The lattices studied, called $NCB_n, NCD_n, NCBD_n(S)$, consist of the noncrossing members of the Dowling and near-Dowling lattices of the sign group, i.e., $\Lat G(\pm K_n^{(T)})$ for $T = [n], \emptyset, [n] \backslash S$, respectively. \codes{\SG:~\G,~\N,~\cov} \itemspace \bibitem{1998a} Characteristic and Ehrhart polynomials. {\it J\. Algebraic Combin\.} 7 (1998), 115--126. MR 99c:05204. Zbl. 899.05003. \annot{} Signed-graph chromatic polynomials are recast geometrically by observing that the number of $k$-colorings equals the number of points of $\{-k, -k + 1, \ldots, k - 1, k\}^n$ that lie in none of the edge hyperplanes of the signed graph. The interesting part is that this generalizes to subspace arrangements of signed graphs and, somewhat {\it ad hoc}, to the hyperplane arrangements of the exceptional root systems. [See also Zaslavsky (20xxi). For applications see articles of Sagan and Zhang.] \codes{\SG,~\Gen:~\M(\Gen),~\G:~\col,~\N} \itemspace \author{T.B\. Boffey} \authorspace \bibitem{1982a} {\it Graph theory in Oper\. Research}. Macmillan, London, 1982. Zbl\. 509.90053. \annot{} Ch\. 10: ``Network flow: extensions.'' 10.1(g): ``Flows with gains,'' pp\. 224--226. 10.3: ``The simplex method applied to network problems,'' subsection ``Generalised networks,'' pp\. 246--250. \codes{\GN:~\m(\bases):~\Exp} \itemspace \author{Kenneth P\. Bogart} \authorspace \authref See M.K\. Bennett, J.E\. Bonin, and J.R\. Weeks. \authrefspace \author{Ethan D\. Bolker} \authorspace \bibitem{1977a} Bracing grids of cubes. {\it Environment and Planning B} 4 (1977), 157--172. \codes{\EC} \itemspace \bibitem{1979a} Bracing rectangular frameworks. II. {\it SIAM J\. Appl\. Math\.} 36 (1979), 491--503. MR 81j:73066b. Zbl\. 416.70010. \codes{\EC,~\SG} \itemspace \author{Bela Bollob\'as} \authorspace \bibitem{1978a} {\it Extremal Graph Theory.} L.M.S\. Monographs, Vol\. 11. Academic Press, London, 1978. MR 80a:05120. Zbl\. 419.05031. \annot{} A rich source of problems: find interesting generalizations to signed graphs of questions involving even or odd polygons, or bipartite graphs or subgraphs. \codes{\p:~\X} \annotctd{} \Sect 3.2, Thm\. 2.2, is Lov\'asz's (1965a) characterization of the graphs having no two vertex-disjoint polygons. \codes{\GG:~\Polygons} \annotctd{} \Sect 6.6, Problem 47, is the theorem on all-negative vertex elimination number from Bollob\'as, Erd\H{o}s, Simonovits, and Szemer\'edi (1978a). \codes{\p:~\Fr} \itemspace \author{B\. Bollob\'as, P\. Erd\"os, M\. Simonovits, and E\. Szemer\'edi} \authorspace \bibitem{1978a} Extremal graphs without large forbidden subgraphs. In: B\. Bollob\'as, ed., {\it Advances in Graph Theory} (Proc\. Cambridge Combin\. Conf., 1977), pp\. 29--41. Ann\. Discrete Math\., Vol\. 3. North-Holland, Amsterdam, 1978. MR 80a:05119. Zbl\. 375.05034. \annot{} Thm\. 9 asymptotically estimates upper bounds on frustration index and vertex elimination number for all-negative signed graphs with fixed negative girth. [Sharpened by Koml\'os (1997a).] \codes{\p:~\Fr} \itemspace \author{J.A\. Bondy and L\. Lov\'asz} \authorspace \bibitem{1981a} Cycles through specified vertices of a graph. {\it Combinatorica} 1 (1981), 117--140. MR 82k:05073. Zbl\. 492.05049. \annot{} If $\Gamma$ is $k$-connected [and not bipartite], then any $k$ $[k-1]$ vertices lie on an even [odd] polygon. [\Problem. Generalize to signed graphs, this being the all-negative case.] \codes{\sg:~\b} \itemspace \author{J.A\. Bondy and M\. Simonovits} \authorspace \bibitem{1974a} Cycles of even length in graphs. {\it J\. Combin\. Theory Ser\. B} 16 (1974), 97--105. MR 49 \#4851. Zbl\. 283.05108. \annot{} If a graph has enough edges, it has even polygons of all moderately small lengths. [\Problem\ 1. Generalize to positive polygons in signed graphs, this being the antibalanced (all-negative) case. For instance, \Problem\ 2. If an unbalanced signed simple graph has positive girth $\geq l$ (i.e., no balanced polygon of length $< l$), what is its maximum size? Are the extremal examples antibalanced? Balanced?] \codes{\p:~\b(~\Polygons),~\X} \itemspace \author{Joseph E\. Bonin} \authorspace \authref See also M.K\. Bennett. \authrefspace \bibitem{1993a} Automorphism groups of higher-weight Dowling geometries. {\it J\. Combin\. Theory Ser\. B} 58 (1993), 161--173. MR 94k:51005. Zbl\. 733.05027, (789.05017). \annot{} A weight-$k$ higher Dowling geometry of rank $n$, $Q_{n,k}(\GF(q)^{\times})$, is the union of all coordinate $k$-flats of $\PG(n-1,q)$: i.e., all flats spanned by $k$ elements of a fixed basis. If $k > 2$, the automorphism groups are those of $\PG(n-1,q)$ for $q > 2$ and are symmetric groups if $q = 2$. \codes{\gg:~\Gen:~\M} \itemspace \bibitem{1993b} Modular elements of higher-weight Dowling lattices. {\it Discrete Math\.} 119 (1993), 3--11. MR 94h:05018. Zbl\. 808.06012. \annot{} See definition in (1993a). For $k > 2$ the only nontrivial modular flats are the projective coordinate $k$-flats and their subflats. This gives some information about the characteristic polynomials [which, however, are still only partially known]. [Kung (1996a), \Sect 6, has further results.] \codes{\gg:~\Gen:~\M,~\N} \itemspace \bibitem{1995a} Automorphisms of Dowling lattices and related geometries. {\it Combin\. Probab\. Comput.} 4 (1995), 1--9. MR 96e:05039. Zbl\. 950.37335. \annot{} The automorphisms of a Dowling geometry of a nontrivial group are the compositions of a coordinate permutation, switching, and a group automorphism. A similar result holds, with two exceptions, if some or all coordinate points are deleted. \codes{\gg:~\M:~Autom} \itemspace \bibitem{1996a} Open problem 6. A problem on Dowling lattices. In: Joseph E\. Bonin, James G\. Oxley, and Brigitte Servatius, eds., {\it Matroid Theory} (Proc., Seattle, 1995), pp\. 417--418. Contemp\. Math., Vol\. 197. Amer\. Math\. Soc., Providence, R.I., 1996. \annot{} \Problem\ 6.1. If a finite matroid embeds in the Dowling geometry of a group, does it embed in the Dowling geometry of some finite group? [The answer may be ``no'' (Squier and Zaslavsky, unwritten and possibly unrecoverable).] \codes{\gg:~\M} \itemspace \author{Joseph E\. Bonin and Kenneth P\. Bogart} \authorspace \bibitem{1991a} A geometric characterization of Dowling lattices. {\it J\. Combin\. Theory Ser\. A} 56 (1991), 195--202. MR 92b:05019. Zbl\. 723.05033. \codes{\gg:~\M} \itemspace \author{Joseph E\. Bonin and Joseph P.S\. Kung} \authorspace \bibitem{1994a} Every group is the automorphism group of a rank-3 matroid. {\it Geom\. Dedicata} 50 (1994), 243--246. MR 95m:20005. Zbl\. 808.05029. \codes{\gg:~\M:~\Autom} \itemspace \author{Joseph E\. Bonin and William P\. Miller} \authorspace \bibitem{20xxa} Characterizing geometries by numerical invariants. Submitted \annot{} Dowling geometries are characterized amongst all simple matroids by numerical properties of large flats of ranks $\leq 7$ (Thm\. 3.4); amongst all matroids by their Tutte polynomials. \codes{\gg:~\M} \itemspace \author{Joseph E\. Bonin and Hongxun Qin} \authorspace \bibitem{20xxa} Size functions of subgeometry-closed classes of representable combinatorial geometries. Submitted \annot{} Extremal matroid theory. The Dowling geometry $Q_3(\GF(3)^{\times})$ appears as an exceptional extremal matroid in Thm\. 2.10. The extremal subset of $\PG(n-1, q)$ not containing the higher-weight Dowling geometry $Q_{m,m-1}(\GF(q)^{\times})$ (see Bonin 1993a) is found in Thm\. 2.14. \codes{\GG,~\Gen:~\M:~\X,~\N} \itemspace \author{C\. Paul Bonnington and Charles H.C\. Little} \authorspace \bibitem{1995a} {\it The Foundations of Topological Graph Theory}. Springer, New York, 1995. MR 97e:05090. Zbl\. 950.48477. \annot{} Signed-graph imbedding: see \Sect 2.3, \Sect 2.6 (esp\. Thm\. 2.4), pp\. 44--48 (for the colorful 3-gem approach to crosscaps), \Sect 3.3, and Ch\. 4 (esp\. Thms. 4.5, 4.6). \codes{\sg:~\T,~\b} \itemspace \author{E\. Boros, Y\. Crama, and P.L\. Hammer} \authorspace \bibitem{1992a} Chv\`atal cuts and odd cycle inequalities in quadratic 0---1 optimization. {\it SIAM J\. Discrete Math\.} 5 (1992), 163--177. MR 93a:90043. Zbl\. 761.90069. \annot{} \Sect 4: ``Odd cycles [i.e., negative polygons] in signed graphs.'' Main problem: Find a minimum-weight deletion set in a signed graph with positively weighted edges. Related problems: A polygon-covering formulation whose constraints correspond to negative polygons. A dual polygon-packing problem. \codes{\SG:~\Fr,~\G,~\Alg} \itemspace \author{Endre Boros and Peter L\. Hammer} \authorspace \bibitem{1991a} The max-cut problem and quadratic 0---1 optimization; polyhedral aspects, relaxations and bounds. {\it Ann. Oper\. Res\.} 33 (1991), 151--180. MR 92j:90049. Zbl\. 741.90077. \annot{} Includes finding a minimum-weight deletion set (as in Boros, Crama, and Hammer (1991a)). \codes{\SG,~\WG:~\Fr:~\G,~\Alg} \itemspace \author{Andr\'e Bouchet} \authorspace \bibitem{1982a} Constructions of covering triangulations with folds. {\it J\. Graph Theory} 6 (1982), 57--74. MR 83b:05057. Zbl\. 488.05032. \codes{\sg:~\O,~\Appl} \itemspace \bibitem{1983a} Nowhere-zero integral flows on a bidirected graph. {\it J\. Combin\. Theory Ser\. B} 34 (1983), 279--292. MR 85d:05109. Zbl\. 518.05058. \annot{} Introduces nowhere-zero flows on signed graphs. A connected, coloop-free signed graph has a nowhere-zero integral flow with maximum weight $\leq 216$. The value $216$ cannot be replaced by $5$, but Bouchet conjectures that it can be replaced by $6$. [See Khelladi (1987a) for some progress on this.] A topological application is outlined. [The bidirection is inessential; it is a device to keep track of the flow.] \codes{\SG:~\M,~\O,~\Flows,~\Appl} \itemspace \author{Jean-Marie Bourjolly} \authorspace \bibitem{1988a} An extension of the K\"onig-Egerv\'ary property to node-weighted bidirected graphs. {\it Math\. Programming} 41 (1988), 375--384. MR 90c:05161. Zbl\. 653.90083. \annot{} [See Sewell (1996a).] \codes{\sg:~\O,~\GG:~\Alg} \itemspace \author{J.-M\. Bourjolly, P.L\. Hammer, and B\. Simeone} \authorspace \bibitem{1984a} Node-weighted graphs having the K\"onig-Egerv\'ary property. Mathematical Programming at Oberwolfach II (Oberwolfach, 1983). {\it Math\. Programming Stud\.} 22 (1984), 44--63. MR 86d:05099. Zbl\. 558.05054. \codes{\p:~\o} \itemspace \author{Jean-Marie Bourjolly and William R\. Pulleyblank} \authorspace \bibitem{1989a} K\"onig-Egerv\'ary graphs, 2-bicritical graphs and fractional matchings. {\it Discrete Appl\. Math\.} 24 (1989), 63--82. MR 90m:05069. Zbl\. 684.05036. \annot{} [It is hard to escape the feeling that we are dealing with all-negative signed graphs and that something here will generalize to other signed graphs. Especially see Theorem 5.1. Consult the references for related work.] \codes{\P;~\Ref} \itemspace \author{John Paul Boyd} \authorspace \bibitem{1969a} The algebra of group kinship. {\it J\. Math\. Psychology} 6 (1967), 139--167. Reprinted in: Samuel Leinhardt, ed., {\it Social Networks: A Developing Paradigm}, pp\. 319--346. Academic Press, New York, 1977. Zbl\. (e: 172.45501). Erratum. {\it J\. Math\. Psychology} 9 (1972), 339. Zbl\. 242.92010. \codes{\SG:~\B} \itemspace \author{S.C\. Boyd} \authorspace \authref See C\. Benzaken. \authrefspace \author{A.J\. Bray, M.A\. Moore, and P\. Reed} \authorspace \bibitem{1978a} Vanishing of the Edwards-Anderson order parameter in two- and three-dimensional Ising spin glasses. {\it J\. Phys\. C: Solid State Phys.} 11 (1978), 1187--1202. \codes{\Phys:~\SG:~\Fr} \itemspace \author{Floor Brouwer and Peter Nijkamp} \authorspace \bibitem{1983a} Qualitative structure analysis of complex systems. In: P\. Nijkamp, H\. Leitner, and N\. Wrigley, eds., {\it Measuring the Unmeasurable}, pp\. 509--530. Martinus Nijhoff, The Hague, 1983. \codes{\QM,~\SD:~\Sol,~\Sta:~\Exp} \itemspace \author{Edward M\. Brown and Robert Messer} \bibitem{1979a} The classification of two-dimensional manifolds. Trans\. Amer\. Math\. Soc\. 255 (1979), 377--402. MR 80j:57007. Zbl\. 391.57010, (414.57003). \annot{} Their ``signed graph'' we might call a type of Eulerian partially bidirected graph. That is, some edge ends are oriented (hence ``partially bidirected''), and every vertex has even degree and at each vertex equally many edge ends point in and out (``Eulerian''). More specially, at each vertex all or none of the edge ends are oriented. \codes{\sg:~\o:~\gen:~\Appl} \itemspace \author{Gerald G\. Brown and Richard D\. McBride} \authorspace \bibitem{1984a} Solving generalized networks. {\it Management Sci\.} 30 (1984), 1497--1523. Zbl\. 554.\-90032. \codes{\GN:~\M(\bases)} \itemspace \author{Kenneth S\. Brown and Persi Diaconis} \authorspace \bibitem{1998a} Random walks and hyperplane arrangements. {\it Ann\. Probab\.} 26 (1998), 1813--1854. \annot{} The real hyperplane arrangement representing $-K_n$ is studied in \Sect 3D. It leads to a random walk on threshold graphs. \codes{\p:~\G} \itemspace \author{Thomas A\. Brown} \authorspace \authref See also F.S\. Roberts. \authrefspace \author{T.A\. Brown, F.S\. Roberts, and J\. Spencer} \authorspace \bibitem{1972a} Pulse processes on signed digraphs: a tool for analyzing energy demand. Rep\. R-926-NSF, Rand Corp., Santa Monica, Cal., March, 1972. \codes{\SDw} \itemspace \author{Thomas A\. Brown and Joel H\. Spencer} \authorspace \bibitem{1971a} Minimization of $\pm 1$ matrices under line shifts. {\it Colloq\. Math\.} 23 (1971), 165--171. MR 46 \#7059. Zbl\. 222.05016. \annot{} Asymptotic estimates of $l(K_{r,s})$, the maximum frustration index of signatures of $K_{r,s}$. Improved by Gordon and Witsenhausen (1972a). Also, exact values stated for $r \leq 4$ [extended by Sol\'e and Zaslavsky (1994a)]. \codes{\sg:~\Fr} \itemspace \author{William G\. Brown, ed.} \authorspace \bibitem{1980a} {\it Reviews in Graph Theory}. 4 vols. American Math\. Soc., Providence, R.I., 1980. Zbl\. 538.05001. \annot{} See esp.: \Sect 208: ``Signed graphs ($+$ or $-$ on each edge), balance'' (undirected and directed), Vol\. 1, pp\. 569--571. \codes{\SG,~\SD} \itemspace \author{Richard A\. Brualdi and Herbert J\. Ryser} \authorspace \bibitem{1991a} {\it Combinatorial Matrix Theory}. Encycl\. Math\. Appl., Vol\. 39. Cambridge University Press, Cambridge, Eng., 1991. MR 93a:05087. Zbl\. 746.05002. \annot{} See \Sect 7.5. \codes{\QM:~\Sol,~\SD,~\b}\codesctd{\Exp,~\Ref} \itemspace \author{Richard A\. Brualdi and Bryan L\. Shader} \authorspace \bibitem{1995a} {\it Matrices of Sign-Solvable Linear Systems}. Cambridge Tracts in Math\., Vol\. 116. Cambridge University Press, Cambridge, Eng., 1995. MR 97k:15001. Zbl\. 833.\-15002. \annot{} Innumerable results and references on signed digraphs are contained herein. \codes{\QM,~\SD:~\Sol,~\Sta}\codesctd{\Exp,~\Ref,~\Alg} \itemspace \author{Michael Brundage} \authorspace \bibitem{1996a} From the even-cycle mystery to the $L$-matrix problem and beyond. M.S\. thesis, Dept\. of Mathematics, Univ\. of Washington, Seattle, 1996. WorldWideWeb URL (10/97) http://www.math.washington.edu/\urltwiddle brundage/evcy/ \annot{} A concise expository survey. Ch\. 1: ``Even cycles in directed graphs''. Ch\. 2: ``$L$-matrices and sign-solvability'', esp\. sect\. ``Signed digraphs''. Ch\. 3: ``Beyond'', esp. sect\. ``Balanced labellings'' (vertices labelled from $\{0, +1, -1\}$ so that from each vertex labelled $\epsilon \neq 0$ there is an arc to a vertex labelled $-\epsilon$) and sect\. ``Pfaffian orientations''. \codes{\SD,~\P:~\Polygons,~\Sol,~\Alg,~\VS:~\Exp,~\Ref} \itemspace \author{Fred Buckley, Lynne L\. Doty, and Frank Harary} \authorspace \bibitem{1988a} On graphs with signed inverses. {\it Networks} 18 (1988), 151--157. MR 89i:05222. Zbl\. 646.05061. \annot{} ``Signed invertible graph'' [i.e., sign-invertible graph] = graph $\Gamma$ such that $A(\Gamma)^{-1} = A(\Sigma)$ for some signed graph $\Sigma$. Finds two classes of such graphs. Characterizes sign-invertible trees. [Cf\. Godsil (1985a) and, for a different notion, Greenberg, Lundgren, and Maybee (1984b).] \codes{\SG:~\A} \itemspace \author{James R\. Burns and Wayland H\. Winstead} \authorspace \bibitem{1982a} Input and output redundancy. {\it IEEE Trans\. Systems Man Cybernetics} SMC-12, No\. 6 (1982), 785--793. \annot{} \Sect IV: ``The computation of contradictory redundancy.'' Summarized in modified notation: In a signed graph, define $w^\epsilon_{ij}(r) =$ number of walks of length $r$ and sign $\epsilon$ from $v_i$ to $v_j$. Define an adjacency matrix $A$ by $a_{ij} = w^+_{ij}(1) + w^-_{ij}(1)\theta$, where $\theta$ is an indeterminate whose square is 1. Then $w^+_{ij}(r) + w^-_{ij}(r)\theta = (A^r)_{ij}$ for all $r\geq 1$. [We should regard this computation as taking place in the group ring of the sign group. The generalization to arbitrary gain graphs and digraphs is obvious.] Other sections also discuss signed digraphs [but have little mathematical content]. \codes{\SD,~\gd:~\A,~\Paths} \itemspace \author{F.C\. Bussemaker, P.J\. Cameron, J.J\. Seidel, and S.V\. Tsaranov} \authorspace \bibitem{1991a} Tables of signed graphs. EUT Report 91-WSK-01. Dept\. of Math\. and Computing Sci., Eindhoven Univ\. of Technology, Eindhoven, 1991. MR 92g:05001. \codes{\SG:~\Sw} \itemspace \author{F.C\. Bussemaker, D.M\. Cvetkovi\'c, and J.J\. Seidel} \authorspace \bibitem{1976a} Graphs related to exceptional root systems. T.H.-Report 76-WSK-05, 91 pp. Dept\. of Math\., Technological Univ\. Eindhoven, Eindhoven, The Netherlands, 1976. Zbl\. 338.05116. \annot{} The 187 simple graphs with eigenvalues $\geq -2$ that are not (negatives of) reduced line graphs of signed graphs are found, with computer aid. By Cameron, Goethals, Seidel, and Shult (1976a), all are represented by root systems $E_d$, $d = 6,7,8$. Most interesting is Thm\. 2: each such graph is Seidel-switching equivalent to a line graph of a graph. [\Problem. Explain this within signed graph theory.] \codes{\LG:~\p:~\A} \itemspace \bibitem{1978a} Graphs related to exceptional root systems. In: A\. Hajnal and Vera T\. S\'os, eds., {\it Combinatorics} (Proc\. Fifth Hungar\. Colloq., Keszthely, 1976), Vol\. 1, pp\. 185--191. Colloq\. Math\. Soc\. J\'anos Bolyai, 18. North-Holland, Amsterdam, 1978. MR 80g:05049. Zbl\. 392.05055. \annot{} Announces the results of (1976a). \codes{\LG:~\p:~\A} \itemspace \author{F.C\. Bussemaker, R.A\. Mathon, and J.J\. Seidel} \authorspace \bibitem{1979a} Tables of two-graphs. TH-Report 79-WSK-05. Dept\. of Math\., Technological Univ\. Eindhoven, Eindhoven, The Netherlands, 1979. Zbl\. 439.05032. \codes{\TG} \itemspace \bibitem{1981a} Tables of two-graphs. In: S.B\. Rao, ed., {\it Combinatorics and Graph Theory} (Proc\. Sympos., Calcutta, 1980), pp\. 70--112. Lecture Notes in Math\., 885. Springer-Verlag, Berlin, 1981. MR 84b:05055. Zbl\. 482.05024. \annot{} ``The most important tables from'' (1979a). \codes{\TG} \itemspace \author{Leishen Cai and Baruch Schieber} \authorspace \bibitem{1997a} A linear-time algorithm for computing the intersection of all odd cycles in a graph, {\it Discrete Appl\. Math\.} 73 (1997), 27--34. MR 97g:05149. Zbl\. 867.05066. \annot{} By the negative-subdivision trick (subdividing each positive edge into two negative ones), the algorithm will find the intersection of all negative polygons of a signed graph. \codes{\P,~\sg:~\Fr:~\Alg} \itemspace \author{Peter J\. Cameron} \authorspace \authref See also F.C\. Bussemaker. \authrefspace \bibitem{1977a} Automorphisms and cohomology of switching classes. {\it J\. Combin\. Theory Ser\. B} 22 (1977), 297--298. MR 58 \#16382. Zbl\. 331.05113, (344.05128). \annot{} The first step towards (1977b), Thm\. 3.1. \codes{\TG:~\Autom} \itemspace \bibitem{\dag 1977b} Cohomological aspects of two-graphs. {\it Math\. Z\.} 157 (1977), 101--119. MR 58 \#21779. Zbl\. 353.20004, (359.20004). \annot{}Introducing the cohomological theory of two-graphs. A two-graph $\tau$ is a $2$-coboundary in the complex of $\GF(2)$-cochains on $E(K_n)$. [The $1$-cochains are the signed complete graphs, equivalently the graphs that are their negative subgraphs. Cf\. D.E\. Taylor (1977a).] Write $Z_i$, $Z^i$, $B^i$ for the $i$-cycle, $i$-cocycle, and $i$-coboundary spaces. Switching a signed complete graph means adding a $1$-cocycle to it; a switching class of signed complete graphs is viewed as a coset of $Z^1$ and is equivalent to a two-graph. \annotctd{} Take a group $\frak G$ of automorphisms of $\tau$. Special cohomology elements $\gamma \in H^1(\frak G, B^1)$ and $\beta \in H^2(\frak G, \tilde B^0)$ (where $\tilde B^0 = \{0, V(K_n)\}$, the reduced $0$-coboundary group) are defined. Thm\. 3.1: $\gamma = 0$ iff $\frak G$ fixes a graph in $\tau$. Thm\. 5.1: $\beta = 0$ iff $\frak G$ can be realized as an automorphism group of the canonical double covering graph of $\tau$ (viewing $\tau$ as a switching class of signed complete graphs). Conditions are explored for the vanishing of $\gamma$ (related to Harries and Liebeck (1978a)) and $\beta$. \annotctd{} $Z^1$ is the annihilator of $Z_1 =$ the space of even-degree simple graphs; the theorems of Mallows and Sloane (1975a) follow immediately. More generally: Lemma 8.2: $Z^i$ is the annihilator of $Z_i$. Thm\. 8.3. The numbers of isomorphism types of $i$-cycles and $i$-cocycles are equal, for $i = 1, \ldots, n-2$. \annotctd{} \Sect 8 concludes with discussion of possible generalizations, e.g., to oriented two-graphs (replacing $\GF(2)$ by $\GF(3)^*$) and double coverings of complete digraphs (Thms\. 8.6, 8.7). [A full ternary analog is developed in Cheng and Wells (1986a).] \codes{\TG:~\Sw,~\Autom,~\E.~\G} \itemspace \bibitem{1979a} Cohomological aspects of $2$-graphs. II. In: C.T.C\. Wall, ed., {\it Homological Group Theory} (Proc\. Sympos\., Durham, 1977), Ch\. 11, pp\. 241--244. London Math\. Soc\. Lecture Note Ser\. 36. Cambridge Univ\. Press, Cambridge, 1979. MR 81a:05061. Zbl\. 461.20001. \annot{} Exposition of parts of (1977b) with a simplified proof of the connection between $\beta$ and $\gamma$. \codes{\TG:~\Autom,~\E,~\G,~\Exp} \itemspace \bibitem{1980a} A note on generalized line graphs. {\it J\. Graph Theory} 4 (1980), 243--245. MR 81j:05089. Zbl\. 403.05048, (427.05039). \annot{} [For generalized line graphs see Zaslavsky (1984c).] If two generalized line graphs are isomorphic, their underlying graphs and cocktail-party attachments are isomorphic, with small exceptions related to exceptional isomorphisms and automorphisms of root systems. The proof, along the lines of Cameron, Goethals, Seidel, and Shult (1976a), employs the canonical vector representation of the underlying signed graph. \codes{\sg:~\LG:~\Autom,~\G} \itemspace \bibitem{1994a} Two-graphs and trees. Graph Theory and Applications (Proc., Hakone, 1990). {\it Discrete Math\.} 127 (1994), 63--74. MR 95f:05027. Zbl\. 802.05042. \annot{} Let $T$ be a tree. Construction 1 (simplifying Seidel and Tsaranov (1990a)): Take all triples of edges such that none separates the other two. This defines a two-graph on $E(T)$ [whose underlying signed complete graph is described by Tsaranov (1992a)]. Construction 2: Choose $X \subseteq V(T)$. Take all triples of end vertices of $T$ whose minimal connecting subtree has its trivalent vertex in $X$. The two-graphs $(V, \Cal T)$ that arise from these constructions are characterized by forbidden substructures, namely, the two-graphs of (1) $C_5$ and $C_6$; (2) $C_5$. Also, trees that yield identical two-graphs are characterized. \codes{\TG} \itemspace \bibitem{1995a} Counting two-graphs related to trees. {\it Electronic J\. Combin\.} 2 (1995), Research Paper 4. MR 95j:05112. Zbl\. 810.05031. \annot{} Counting two-graphs of the types constructed in (1994a). \codes{\TG:~\E} \itemspace \author{P.J\. Cameron, J.M\. Goethals, J.J\. Seidel, and E.E\. Shult} \authorspace \bibitem{\dag\dag 1976a} Line graphs, root systems, and elliptic geometry. {\it J\. Algebra} 43 (1976), 305--327. MR 56 \#182. Zbl\. 337.05142. Reprinted in Seidel (1991a), pp\. 208--230. \annot{} The essential idea is that graphs with least eigenvalue $\geq -2$ are represented by the angles of root systems. It follows that line graphs are so represented. [Similarly, signed graphs with largest eigenvalue $\leq 2$ are represented by the inner products of root systems, as in Vijayakumar {\it et al}. These include the line graphs of signed graphs as in Zaslavsky (1984c), since simply signed graphs are represented by $B_n$ or $C_n$ with a few exceptions . The representation of ordinary graphs by all-negative signed graphs is motivated in Zaslavsky (1984c).] \codes{\LG:~\sg:~\A,~\G,~\Sw} \itemspace \author{P.J\. Cameron, J.J\. Seidel, and S.V\. Tsaranov} \authorspace \bibitem{1994a} Signed graphs, root lattices, and Coxeter groups. {\it J\. Algebra} 164 (1994), 173--209. MR 95f:20063. Zbl\. 802.05043. \annot{} A generalized Coxeter group $\Cox(\Sigma)$ and a Tsaranov group $\Ts(\Sigma)$ are defined via Coxeter relations and an extra relation for each negative polygon in $\Sigma$. They generalize Coxeter groups of tree Coxeter graphs and the Tsaranov groups of a two-graph ($|\Sigma| = K_n$; see Seidel and Tsaranov (1990a)). A new operation of ``local switching'' is introduced, which changes the edge set of $\Sigma$ but preserves the associated groups. \annotctd{} \Sect 2, ``Signed graphs'', proves some well-known properties of switching and reviews interesting data from Bussemaker, Cameron, Seidel, and Tsaranov (1991a). \Sect 3, ``Root lattices and Weyl groups'': The ``intersection matrix'' $2I + A(\Sigma)$ is a hyperbolic Gram matrix of a basis of $\Bbb R^n$ whose vectors form only angles $\pi/2, \pi/3, 2\pi/3$. To these vectors are associated the lattice $L(\Sigma)$ of their integral linear combinations and the Weyl group $W(\Sigma)$ generated by reflecting along the vectors. $W$ is finite iff $2I + A(\Sigma)$ is positive definite (Thm\. 3.1). \Problem\ 3.6. Determine which $\Sigma$ have this property. \Sect 4 introduces local switching to partially solve \Problem\ 4.1: Which signed graphs generate the same lattice? Results and some experimental data are reported. All-negative signed graphs play a special role. \Sect 6, ``Coxeter groups'': The relationship between the Coxeter and Weyl groups of $\Sigma$. Cox($\Sigma$) is Cox($|\Sigma|$) with additional relations for antinegative (i.e., negative in $-\Sigma$) induced polygons. \Sect 7: ``Signed complete graphs''. \Sect 8: ``Tsaranov groups'' of signed $K_n$'s \Sect 9: ``Two-graphs arising from trees'' (as in Seidel and Tsaranov (1990a)). \annotctd{} Dictionary: ``$(\Gamma, f)$'' = $\Sigma = (\Gamma, \sigma)$. ``Fundamental signing'' = all-negative signing, giving the antibalanced switching class. ``The balance'' of a cycle (i.e., polygon) = its sign $\sigma(C)$; ``the parity'' = $\sigma(-C)$ where $-C = C$ with all signs negated. ``Even'' = positive and ``odd'' = negative (referring to ``parity''). ``The balance'' of $\Sigma$ = the partition of all polygons into positive and negative classes $\Cal C^+$ and $\Cal C^-$; this is the bias on $|\Sigma|$ due to the signing and should not be confused with the customary meaning of ``balance'', i.e., all polygons are positive. \annotctd{} [A more natural definition of the intersection matrix would be $2I - A$. Then signs would be negative to those in the paper. The need for ``parity'' would be obviated, ordinary graphs would correspond to all-positive signings (and those would be ``fundamental''), and the extra Coxeter relations would pertain to negative induced polygons.] \codes{\SG:~\A,~\G,~\Sw(\Gen),~\lg} \itemspace \author{P.J\. Cameron and Albert L\. Wells, Jr.} \authorspace \bibitem{1986a} Signatures and signed switching classes. {\it J\. Combin\. Theory Ser\. B} 40 (1986), 344--361. MR 87m:05115. Zbl\. 591.05061. \codes{\SG:~\TG:~\Gen} \itemspace \author{Sue Ann Campbell} \authorspace \authref See J\. B\'elair. \authrefspace \author{E\. Rodney Canfield} \authorspace \authref See E.A\. Bender. \authrefspace \author{D.-S\. Cao} \authorspace \authref See R\. Simion. \authrefspace \author{Dorwin Cartwright} \authorspace \authref See also T.C\. Gleason; Harary, Norman, and Cartwright (1965a, etc.) \authrefspace \author{Dorwin Cartwright and Terry C\. Gleason} \authorspace \bibitem{1966a} The number of paths and cycles in a digraph. {\it Psychometrika} 31 (1966), 179--199. MR 33 \#5377. Zbl\. (e: 143.43702). \codes{\SD:~\A,~\Paths} \itemspace \author{Dorwin Cartwright and Frank Harary} \authorspace \itemspace \bibitem{1956a} Structural balance: a generalization of Heider's theory. {\it Psychological Rev\.} 63 (1956), 277--293. Reprinted in: Dorwin Cartwright and Alvin Zander, eds., {\it Group Dynamics: Research and Theory}, Second Edition, pp\. 705--726. Harper and Row, New York, 1960. Also reprinted in: Samuel Leinhardt, ed., {\it Social Networks: A Developing Paradigm}, pp\. 9--25. Academic Press, New York, 1977. \annot{} Expounds Harary (1953a, 1955a) with sociological discussion. Proposes to measure imbalance by the proportion of balanced polygons (the ``degree of balance'') or polygons of length $\leq k$ ((``degree of $k$-balance''). \codes{\PsS,~\SG:~\B,~\Fr} \itemspace \bibitem{1968a} On the coloring of signed graphs. {\it Elem\. Math\.} 23 (1968), 85--89. MR 38 \#2053. Zbl\. 155, 317 (e: 155.31703). \codes{\SG:~\Cl} \itemspace \bibitem{1970a} Ambivalence and indifference in generalizations of structural balance. {\it Behavioral Sci\.} 15 (1970), 497--513. \codes{\SD,~\B} \itemspace \bibitem{1977a} A graph theoretic approach to the investigation of system-environment relationships. {\it J\. Math\. Sociology} 5 (1977), 87--111. MR 56 \#2477. Zbl\. 336.92026. \annot{} \codes{\SD:~\Cl} \itemspace \bibitem{1979a} Balance and clusterability: an overview. In: Paul W\. Holland and Samuel Leinhardt, eds., {\it Perspectives on Social Network Research} (Proc\. Sympos., Dartmouth Coll., Hanover, N.H., 1975), Ch\. 3, pp\. 25--50. Academic Press, New York, 1979. \codes{\SG,~\SD,~\VS:~\B,~\Fr,~\Cl,~\A:~\Exp} \itemspace \author{Adolfo Casari} \authorspace \authref See F\. Barahona. \authrefspace \author{Paul A\. Catlin} \authorspace \bibitem{1979a} Haj\'os' graph-coloring conjecture: variations and counterexamples. {\it J\. Combin\. Theory Ser\. B} 26 (1979), 268--274. MR 81g:05057. Zbl\. 385.05033, 395.05033. \annot{} Thm\. 2: If $\Gamma$ is $4$-chromatic, $[-\Gamma]$ contains a subdivision of $[-K_4]$ (an ``odd-$K_4$''). [\Question. Can this possibly be a signed-graph theorem? For instance, should it be interpreted as concerning the $0$-free (signed) chromatic number of $-\Gamma$?] \codes{\p:~\col} \itemspace \author{Seth Chaiken} \authorspace \bibitem{1982a} A combinatorial proof of the all minors matrix tree theorem. {\it SIAM J\. Algebraic Discrete Methods} 3 (1982), 319--329. MR 83h:05062. \codes{\SD,~\SG,~\GG:~\A,~\I} \itemspace \bibitem{1996a} Oriented matroid pairs, theory and an electrical application. In: Joseph E\. Bonin, James G\. Oxley, and Brigitte Servatius, eds., {\it Matroid Theory} (Proc., Seattle, 1995), pp\. 313--331. Contemp\. Math\., Vol\. 197. Amer\. Math\. Soc., Providence, R.I., 1996. MR 97e:05058. \annot{} Connects a problem on common covectors of two subspaces of $\Bbb R^m$, and more generally of a pair of oriented matroids, to the problem of sign-solvability of a matrix and the even-cycle problem for signed digraphs. \codes{\Sol,~\sd:~\P,~\Alg} \itemspace \bibitem{1996b} Open problem 5. A problem about common covectors and bases in oriented matroid pairs. In: Joseph E\. Bonin, James G\. Oxley, and Brigitte Servatius, eds., {\it Matroid Theory} (Proc., Seattle, 1995), pp\. 415--417. Contemp\. Math\., Vol\. 197. Amer\. Math\. Soc., Providence, R.I., 1996. \annot{} Possible generalizations to oriented matroids of sign-nonsingularity of a matrix. \codes{\Sol,~\SD:~\P} \itemspace \author{Vijaya Chandru, Collette R\. Coullard, and Donald K\. Wagner} \authorspace \bibitem{1985a} On the complexity of recognizing a class of generalized networks. {\it Oper\. Res\. Letters} 4 (1985), 75--78. MR 87a:90144. Zbl\. 565.90078. \annot{} Determining whether a gain graph with real multiplicative gains has a balanced polygon, i.e., is not contrabalanced, is NP-hard. So is determining whether a real matrix is projectively equivalent to the incidence matrix of a contrabalanced real gain graph. \codes{\GN,~\Bic:~\I,~\Alg} \itemspace \author{Chung-Chien Chang and Cheng-Ching Yu} \authorspace \bibitem{1990a} On-line fault diagnosis using the signed directed graph. {\it Industrial and Engineering Chem\. Res\.} 29 (1990), 1290--1299. \annot{} Modifies the method of Iri, Aoki, O'Shima, and Matsuyama (1979a) of constructing the diagnostic signed digraph, e.g\. by considering transient and steady-state situations. \codes{\SD:~\Appl,~\Ref} \itemspace \author{Gerard J\. Chang} \authorspace \authref See J.-H\. Yan. \authrefspace \author{A\. Charnes, M\. Kirby, and W\. Raike} \authorspace \bibitem{1966a} Chance-constrained generalized networks. {\it Oper\. Res}. 14 (1966), 1113--1120. Zbl\. (e: 152.18302). \codes{\GN} \itemspace \author{A\. Charnes and W.M\. Raike} \authorspace \bibitem{1966a} One-pass algorithms for some generalized network problems. {\it Oper\. Res\.} 14 (1966), 914--924. Zbl\. (e: 149.38106). \codes{\GN:~\I} \itemspace \author{Gary Chartrand} \authorspace \authref See also M\. Behzad. \authrefspace \bibitem{1977a} {\it Graphs as Mathematical Models}. Prindle, Weber and Schmidt, Boston, 1977. MR 58 \#9947. Zbl\. 384.05029. \codes{\SG:~\B,~\Cl} \itemspace \author{Gary Chartrand, Heather Gavlas, Frank Harary, and Michelle Schultz} \authorspace \bibitem{1994a} On signed degrees in signed graphs. {\it Czechoslovak Math\. J\.} 44 (1994), 677--690. MR 95g:05084. Zbl\. 837.05110. \annot{} Net degree sequences (i.e., $d^+ - d^-$; called ``signed degree sequences'') of signed simple graphs. A Havel--Hakimi-type reduction formula, but with an indeterminate length parameter [improved in Yan, Lih, Kuo, and Chang (1997a)]; a determinate specialization to complete graphs. A necessary condition for a sequence to be a net degree sequence. Examples: paths, stars, double stars. [Continued in Yan, Lih, Kuo, and Chang (1997a).] \annotctd{}[This is a special case of weighted degree sequences of $K_n$ with integer edge weights chosen from a fixed interval of integers. In this case the interval is $[-1, +1]$. There is a theory of such sequences; however, it seems not to yield the exact results obtained here.] \codes{\SGw:~\N} \annotctd{}[One can interpret net degrees as the net indegrees ($d^{\text{\rm in}} - d^{\text{\rm out}}$) of certain bidirected graphs. Change the positive (negative) edges to extroverted (resp\., introverted). Then we have the net indegree sequence of an oriented $-\Gamma$. \Problem\ 1. Generalize this paper and Yan, Lih, Kuo, and Chang (1997a) to all bidirected (simple, or simply signed) graphs, especially $K_n$'s. \Problem\ 2. Find an Erd\H{o}s--Gallai-type characterization of net degree sequences of signed simple graphs. \Problem\ 3. Characterize the separated signed degree sequences of signed simple graphs, where the separated signed degree is $(d^+(v), d^-(v))$. \Problem\ 4. Generalize Problem 3 to edge $k$-colorings of $K_n$.] \codes{\SG:~\O:~\N} \itemspace \author{Gary Chartrand, Frank Harary, Hector Hevia, and Kathleen A\. McKeon} \authorspace \bibitem{1992a} On signed graphs with prescribed positive and negative graphs. {\it Vishwa Internat\. J\. Graph Theory} 1 (1992), 9--18. MR 93m:05095. \annot{} What is the smallest order of an edge-disjoint union of two (isomorphism types of) simple graphs, $\Gamma$ and $\Gamma'$? Bounds, constructions, and special cases. (The union is called a signed graph with $\Gamma$ and $\Gamma'$ as its positive and negative subgraphs.) Thm\. 13: If $\Gamma'$ is bipartite (i.e., the union is balanced) with color classes $V'_1$ and $V'_2$, the minimum order $= \min(|V'_1|, |V'_2|) + \max(|V|, |V'_1|, |V'_2|)$. \codes{\wg}\codesctd{\SG:~\B} \itemspace \author{Guy Chaty} \authorspace \bibitem{1988a} On signed digraphs with all cycles negative. {\it Discrete Appl\. Math\.} 20 (1988), 83--85. MR 89d:05148. Zbl\. 647.05028. \annot{} Clarifies the structure of ``free cyclic'' digraphs and shows they include strong ``upper'' digraphs (see Harary, Lundgren, and Maybee (1985a)). \codes{\SD:~\Str} \itemspace \author{P.D\. Chawathe and G.R\. Vijayakumar} \authorspace \bibitem{1990a} A characterization of signed graphs represented by root system $D_\infty$. {\it European J\. Combin\.} 11 (1990), 523--533. MR 91k:05071. Zbl\. 764.05090. \codes{\SG:~\G} \itemspace \author{Jianer Chen, Jonathan L\. Gross, and Robert G\. Rieper} \authorspace \bibitem{1994a} Overlap matrices and total imbedding distributions. {\it Discrete Math\.} 128 (1994), 73--94. MR 95f:05031. Zbl\. 798.05017. \codes{\SG:~\T,~\Sw} \itemspace \author{Ying Cheng} \authorspace \bibitem{1986a} Switching classes of directed graphs and $H$-equivalent matrices. {\it Discrete Math\.} 61 (1986), 27--40. MR 88a:05075. Zbl\. 609.05039. \annot{} This article studies what are described as $\Bbb Z_4$-gain graphs $\Phi$ with underlying simple graph $\Gamma$. [However, see below.] They are regarded as digraphs $D$, the gains being determined by $D$ as follows: $\phi(u,v) = 1$ or $2$ if $(u,v)$ is an arc, $2$ or $3$ if $(v,u)$ is an arc. [N.B. $\Gamma$ is not uniquely determined by $D$.] Cheng's ``switching'' is gain-graph switching but only by switching functions $\eta : V \to \{0,2\}$; I will call this ``semiswitching''. His ``isomorphisms'' are vertex permutations that are automorphisms of $\Gamma$; I will call them ``$\Gamma$-isomorphisms''. The objects of study are equivalence classes under semiswitching (semiswitching classes) or semiswitching and $\Gamma$-isomorphism (semiswitching $\Gamma$-isomorphism classes). Prop\. 3.1 concerns adjacency of vertex orbits of a $\Gamma$-isomorphism that preserves a semiswitching class (call it a $\Gamma$-automorphism of the class). Thm\. 4.3 gives the number of semiswitching $\Gamma$-isomorphism classes. Thm\. 5.2 characterizes those $\Gamma$-automorphisms of a semiswitching class that fix an element of the class; Thm\. 5.3 characterizes the $\Gamma$-isomorphisms $g$ that fix an element of every $g$-invariant semiswitching class. \annotctd{} [Likely the right viewpoint, as is hinted in \Sect 6, is that the edge labels are not $\Bbb Z_4$-gains but weights from the set $\{\pm1, \pm2, \ldots, \pm k\}$ with $k = 2$. Then semiswitching is ordinary signed switching, and so forth. However, I forbear to reinterpret everything here.] \annotctd{} In \Sect 6, $\Bbb Z_4$ is replaced by $\Bbb Z_{2k}$ [but this should be $\{\pm1, \pm2, \ldots, \pm k\}$]; semiswitching functions take values $0, k$ only. Generalizations of Sects\. 3, 4 are sketched and are applied to find the number of $H$-equivalent matrices of given size with entries $\pm1, \pm1, \ldots, \pm k$. ($H$- [or Hadamard] equivalence means permuting rows and columns and scaling by $-1$.) \codes{~\sg,~\wg,~\GG:~\Sw,~\Autom,~\E} \itemspace \author{Ying Cheng and Albert L\. Wells, Jr.} \authorspace \bibitem{1984a} Automorphisms of two-digraphs. (Summary). Proc\. Fifteenth Southeastern Conf\. on Combin\., Graph Theory and Computing (Baton Rouge, 1984). {\it Congressus Numer\.} 45 (1984), 335--336. MR 86c:05004c (volume). \annot{} A two-digraph is a switching class of $\Bbb Z_3$-gain graphs based on $K_n$. \codes{\gg,~\SD:~\Sw,~\Autom} \itemspace \bibitem{\dag 1986a} Switching classes of directed graphs. {\it J\. Combin\. Theory Ser\. B} 40 (1986), 169--186. MR 87g:05104. Zbl\. 565.05034, (579.05027). \annot{} This exceptionally interesting paper treats a digraph as a ternary gain graph $\Phi$ (i.e., with gains in $\GF(3)^+$) based on $K_n$. A theory of switching classes and triple covering graphs, analogous to that of signed complete graphs (and of two-graphs) is developed. The approach, analogous to that in Cameron (1977b), employs cohomology. The basic results are those of general gain-graph theory specialized to the ternary gain group and graph $K_n$. \annotctd{} The main results concern a switching class $[\Phi]$ of digraphs and an automorphism group $\frak A$ of $[\Phi]$. \Sect 3, ``The first invariant'': Thm\. 3.2 characterizes, by a cohomological obstruction $\gamma$, the pairs $([\Phi], \frak A)$ such that some digraph in $[\Phi]$ is fixed. Thm\. 3.5 is an [interestingly] more detailed result for cyclic $\frak A$. \Sect 4: ``Triple covers and the second invariant''. Digraph triple covers of the complete digraph are considered. Those that correspond to gain covering graphs of ternary gain graphs $\Phi$ are characterized (``cyclic triple covers'', pp\. 178--180). Automorphisms of $\Phi$ and its triple covering $\tilde\Phi$ are compared. Given $([\Phi], \frak A)$, Thm\. 4.4 finds the cohomological obstruction $\beta$ to lifting $\frak A$ to $\tilde\Phi$. Thm\. 4.7 establishes an equivalence between $\gamma$ and $\beta$ in the case of cyclic $\frak A$. \annotctd{} \Sect 5: ``Enumeration''. Thm\. 5.1 gives the number of isomorphism types of switching classes on $n$ vertices, based on the method of Wells (1984a) for signed graphs. \Sect 6: ``The fixed signing property''. Thm\. 6.1 characterizes the permutations of $V(K_n)$ that fix a gain graph in every invariant switching class, based on the method of Wells (1984a). \annotctd{} Dictionary: ``Alternating function'' on $X \times X$ = $\GF(3)^+$-valued gain function on $K_X$. \codes{\gg,~\SD:~\Sw,~\Autom,~\E,~\Cov} \itemspace \author{Hyeong-ah Choi, Kazuo Nakajima, and Chong S\. Rim} \authorspace \bibitem{1989a} Graph bipartization and via minimization. {\it SIAM J\. Discrete Math\.} 2 (1989), 38--47. MR 89m:90132. Zbl\. 677.68036. \annot{} Vertex biparticity (the fewest vertices to delete to get a bipartite graph) is compared to edge biparticity (for cubic graphs) and studied algorithmically. \codes{\p:~\Fr} \itemspace \author{Debashish Chowdhury} \authorspace \bibitem{1986a} {\it Spin Glasses and Other Frustrated Systems}. Princeton Univ\. Press, Princeton, and World Scientific, Singapore, 1986. \annot{} Includes brief survey of how physicists look upon frustration. See esp\. \Sect 1.3, ``An elementary introduction to frustration'', where the signed square lattice graph illustrates balance vs\. imbalance; Ch\. 20, ``Frustration, gauge invariance, defects and SG [spin glasses]'', discussing planar duality (see e.g\. Barahona (1982a), ``gauge theories'', where gains are in the orthogonal or unitary group (and switching is called ``gauge transformation'' by physicists), and functions of interest to physicists; Addendum to Ch\. 10, pp\. 378--379, mentioning results on when the proportion of negative bonds is fixed and on gauge theories. \codes{\Phys:~\SG,~\GG,~\VS,~\Fr:~\Exp,~\Ref} \itemspace \author{San Yan Chu} \authorspace \authref See S.-L\. Lee. \authrefspace \author{V\. Chv\'atal} \authorspace \authref See J\. Akiyama. \authrefspace \author{F.W\. Clarke, A.D\. Thomas, and D.A\. Waller} \authorspace \bibitem{1980a} Embeddings of covering projections of graphs. {\it J\. Combin\. Theory Ser\. B} 28 (1980), 10--17. MR 81f:05066. Zbl\. 351.05126, (416.05069). \codes{\gg:~\T} \itemspace \author{Bernard P\. Cohen} \authorspace \authref See J\. Berger. \authrefspace \author{Edith Cohen and Nimrod Megiddo} \authorspace \bibitem{1989a} Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs. In: {\it Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing} (Seattle, 1989), pp\. 523--534. \annot{} Partial version of (1993a). \codes{GD:~\B:~\Alg} \itemspace \bibitem{1991a} Recognizing properties of periodic graphs. In: Peter Gritzmann and Bernd Sturmfels, eds., {\it Applied geometry and Discrete Mathematics: The Victor Klee Festschrift}, pp\. 135--146. DIMACS Ser\. Discrete Math\. Theoret\. Computer Sci., Vol\. 4. Amer\. Math\. Soc., Providence, R.I., and Assoc\. Computing Mach., 1991. MR 92g:05166. Zbl\. 753.05047. \annot{} Given: a gain graph $\Phi$ with gains in $\Bbb Z^d$ (a ``static graph''). Found: algorithms for (1) connected components and (2) bipartiteness of the covering graph $\tilde\Phi$ (the ``periodic graph'') and, (3) given costs on the edges of $\Phi$, for a minimum-average-cost spanning tree in the covering graph. Many references to related work. \codes{\GG(~\Cov):~\Alg,~\Ref} \itemspace \bibitem{1992a} New algorithms for generalized network flows. In: D\. Dolev, Z\. Galil, and M\. Rodeh, eds., {\it Theory of Computing and Systems} (Proc\., Haifa, 1992), pp\. 103--114. Lect\. Notes in Computer Sci., Vol\. 601. Springer-Verlag, Berlin, 1992. MR 94b:68023 (book). \annot{} Preliminary version of (1994a), differing only slightly. \codes{\GN:~\Alg}\codesctd{\sg:~\O:~\Alg} \itemspace \bibitem{1993a} Strongly polynomial-time and NC algorithms for detecting cycles in periodic \linebreak graphs. {\it J\. Assoc\. Comput\. Mach.} 40 (1993), 791--830. MR 96h:05182. Zbl\. 782.68053. \annot{} Looking for a closed walk (``cycle'') with gain $0$ in a gain digraph with (additive) gains in $\Bbb Q^d$. [Cf\. Kodialam and Orlin (1991a).] \codes{\GD:~\B:~\Alg} \itemspace \bibitem{1994a} New algorithms for generalized network flows. {\it Math\. Programming} 64 (1994), 325--336. MR 95k:90111. Zbl\. 816.90057. \annot{} Maximize the fraction of demand satisfied by a flow on a network with gains. Positive real gains in \Sect 3. Bidirected networks with positive gains in \Sect 4; these are more general than networks with arbitrary non-zero real gains. \codes{\GN:~\Alg}\codesctd{\sg:~\O:~\Alg} \itemspace \bibitem{1994b} Improved algorithms for linear inequalities with two variables per inequality. {\it SIAM J\. Comput.} 23 (1994), 1313--1347. MR 95i:90040. Zbl\. 833.90094. \codes{\GN(\I):~\D:~\Alg} \itemspace \author{Charles J\. Colbourn and Derek G\. Corneil} \authorspace \bibitem{1980a} On deciding switching equivalence of graphs. {\it Discrete Appl\. Math\.} 2 (1980), 181--184. MR 81k:05090. Zbl\. 438.05054. \annot{} Deciding switching equivalence of graphs is polynomial-time equivalent to graph isomorphism. \codes{\TG:~\Alg} \itemspace \author{L\. Collatz} \authorspace \bibitem{1978a} Spektren periodischer Graphen. {\it Resultate Math\.} 1 (1978), 42--53. MR 80b:05042. Zbl\. 402.05054. \annot{} Introducing periodic graphs: these are connected canonical covering graphs $\Gamma = \tilde\Phi$ of finite $\Bbb Z^d$-gain graphs $\Phi$. The ``spectrum'' of $\Gamma$ is the set of all eigenvalues of $A(||\Phi||)$ for all possible $\Phi$. The spectrum, while infinite, is contained in the interval $[-r, r]$ where $r$ is the largest eigenvalue of each $A(||\Phi||)$ [the ``index'' of von Below (1994a)]. The inspiration is tilings. \codes{\GG(\Cov):~\A} \itemspace \author{Barry E\. Collins and Bertram H\. Raven} \authorspace \bibitem{1968a} Group structure: attraction, coalitions, communication, and power. In: Gardner Lindzey and Elliot Aronson, eds., {\it The Handbook of Social Psychology}, Second Edition, Vol\. 4, Ch\. 30, pp\. 102--204. Addison-Wesley, Reading, Mass., 1968. \annot{} ``Graph theory and structural balance,'' pp\. 106--109. \codes{\PsS:~\SG:~\Exp,~\Ref} \itemspace \author{Ph\. Combe and H\. Nencka} \authorspace \bibitem{1995a} Non-frustrated signed graphs. In: J\. Bertrand {\it et al\.}, eds., {\it Modern Group Theoretical Methods in Physics} (Proc\. Conf\. in Honour of Guy Rideau, Paris, 1995), pp\. 105--113. Math\. Phys\. Stud., Vol\. 18. Kluwer, Dordrecht, 1995. MR 96j:05105. \annot{} $\Sigma$ is balanced iff a fundamental system of polygons is balanced [as is well known; see {\it i.a.} Popescu (1979a), Zaslavsky (1981b)]. An algorithm [incredibly complicated, compared to the obvious method of tracing a spanning tree] to determine all vertex signings of $\Sigma$ that switch it to all positive. Has several physics references. \codes{\SG:~\B,~\