TOPICS
Search

Signed Graph


A signed graph is a finite simple graph G together with a function sigma:E(G)->{-1,1} assigning a sign to each graph edge (Zaslavsky 1982). The sign of a cycle graph is the product of its edge signs. Switching at a graph vertex reverses the signs of all incident edges and preserves every cycle sign. Reversing every edge sign is a different operation.

The signed circular chromatic number measures the circumference needed for a circular coloring that respects the signs. It depends on the convention for positive and negative edges.

The frustration index is the minimum number of edges whose deletion makes every cycle graph positive. Equivalently, it is the minimum number of negative edges attainable by switching (Zaslavsky 1998).


See also

Signed Circular Chromatic Number

Explore with Wolfram|Alpha

References

Zaslavsky, T. "Glossary of Signed and Gain Graphs and Allied Areas, 2nd ed." Sep. 16, 1998. https://ftp.gwdg.de/pub/EMIS/journals/EJC/Surveys/ds9.html.Zaslavsky, T. "Signed Graphs." Discrete Appl. Math. 4, 47-74, 1982. https://doi.org/10.1016/0166-218X(82)90033-6.

Cite this as:

Weisstein, Eric W. "Signed Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SignedGraph.html

Subject classifications