![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
We examine the conditions under which a signed graph contains an edge or a vertex that is contained in a unique negative circle or a unique positive circle. For an edge in a unique signed circle, the positive and negative case require the same structure on the underlying graph, but the requirements on the signature are different. We characterize the structure of the underlying graph necessary to support such an edge in terms of bridges of a circle. We then use the results from the edge version of the problem to help solve the vertex version.
0 Introduction
A signed graph is a graph in which each edge is assigned either a positive or negative sign. The sign of a circle (a connected, -regular subgraph) in a signed graph is defined to be the product of the signs of its edges. In many cases, the most important feature of a signed graph is the sign of each of its circles. A signed graph that contains no negative circle is said to be balanced, while a signed graph that contains at least one negative circle is unbalanced. The purpose of this paper is to determine when a signed graph contains an edge or a vertex that is contained in a unique negative circle or a unique positive circle.
Signed graphs were invented by Harary in 1953 in order to help study a question in social psychology [Citation1]. In 1956, Harary observed that an edge of a signed graph lies in some negative circle if and only if the block (maximal -connected subgraph) containing it is unbalanced [Citation2]. Similarly, an edge lies in some positive circle if and only if it is not a balancing edge in its block (see Lemma 3.3). Our problem is related to these facts, but the added uniqueness condition creates many additional restrictions on both the structure of the underlying graph and the signature.
1 Definitions
1.1 Graphs
A graph
consists of a finite vertex set
and finite edge set
. Each edge has a pair of vertices as its endpoints, and we write
for an edge with endpoints
and
. A link is an edge with two distinct endpoints, and a loop has two equal endpoints. We write
for the complete graph on
vertices.
Let be a subgraph of
. Then for
, the degree of
in
, denoted as
, is the number of edges in
that are incident with
(a loop counts twice).
A circle
is a connected
-regular subgraph. An edge
connecting two different vertices of
is a chord.
A path
is a sequence of adjacent vertices and connecting edges that never repeats an edge or a vertex. We call
and
the endpoints of
, while the other vertices are interior vertices.
We subdivide an edge by replacing it with a path that has at least one edge. A subdivision of is a graph obtained by subdividing some of the edges of
.
Given a circle of
, a bridge of
is either a connected component
of
along with all edges joining
to
, or a chord of
. The vertices of attachment of a bridge
are the vertices in
. A path contained in
that has different vertices of attachment for its endpoints is a path through
.
A cutpoint of is a vertex
with the property that there exist subgraphs
and
each with at least one edge, such that
and
. An isthmus is an edge whose removal increases the number of connected components. A block of
is a maximal subgraph that contains no cutpoint. Each edge is contained in exactly one block.
1.2 Signed graphs
A signed graph
is a pair
, where
is a graph (called the underlying graph), and
is the signature.
The sign of a circle in
is defined to be the product of the signs of its edges. Thus, a signed circle can be either positive or negative. A signed graph is balanced if all of its circles are positive, and unbalanced if it contains at least one negative circle.
A theta graph consists of three paths with the same endpoints and no other vertices in common. The most useful thing about theta graphs in our context is the theta property : every signed theta graph has either or
positive circles. If two circles
and
intersect in a path with at least one edge, then
is a theta graph with third circle
(we use
for symmetric difference). By the theta property, if
and
have the same sign then
is positive, and otherwise
is negative.
A switching function on is a function
. We can use
to modify
, obtaining a new signature given by
, where
are the endpoints of
. The switched signed graph is written
. If
is obtained from
via switching, we say
and
are switching equivalent, written
. Switching is useful for us because of the following fact.
Lemma 1.1
Zaslavsky [Citation3], Sozański [Citation4]
Let
and
be signed graphs on the same underlying graph. Then,
if and only if
and
have the same collection of positive circles. In particular,
is balanced if and only if it switches to an all-positive signature.
If can be switched so that it has a single negative edge
, we call
a balancing edge. The deletion of a balancing edge yields a balanced signed graph. Moreover, if
is a balancing edge, the negative circles of
are precisely those that contain
.
Assume an edge is contained in at least one circle. Then
is contained in only positive circles if and only if the block containing it is balanced, and
is contained in only negative circles if and only if it is a balancing edge in its block (Lemma 3.3). In other words,
is contained in some negative circle if and only if the block containing
is unbalanced (as discovered by Harary [Citation2]), and
is contained in some positive circle if and only if
is not balancing in the block containing it.
2 Batteries
Let us give a name to the main object of study in this paper. A battery is an edge of that is contained in a unique negative or positive circle
. An edge
may be a negative battery or a positive battery, depending on the sign of
. We write
for a negative battery
that is contained in the unique negative circle
, and similarly
for a positive battery. The advantage of this notation is that it enables us to keep track of both
and its sign.
We wish to determine when a given edge is a battery. This problem is uninteresting when
is an isthmus of
(
is not contained in a circle), so throughout we assume
is contained in at least one circle. Since the block
containing
is the union of all circles containing
, we will focus only on
. If
consists of a single circle, it is trivially true that all edges of
are batteries. Thus, for the rest of this section we assume that the underlying graph of
is a block
containing
such that
is neither an isthmus, nor a circle.
2.1 Layering
In this section we introduce the structure of the underlying block that is necessary for
to be a battery.
First, we need some terminology to help describe the chords of a circle . We say that chords
and
of
cross if
is a subdivision of
. Chords that do not cross are noncrossing. Let
be the set of all vertices of
that are endpoints of some chord of
. The vertices of
partition
into paths, called segments. A segment of
whose endpoints have a chord between them is called a handle. We say that
is
-handled if any two of its chords are noncrossing and it contains exactly two handles. Thus, the property of being
-handled is a stronger version of having noncrossing chords (noncrossing chords may create many handles). If
is
-handled, edges
and
contained in separate handles are said to be separated.
We will now define the appropriate structure on , and then explain how to reduce this structure to a
-handled circle. Let
be a circle of
, and suppose every bridge of
has exactly two vertices of attachment. The graph obtained by replacing each of these bridges with a single chord between its vertices of attachment is denoted as
. If
is
-handled, we say that
is
-layered. See for an example of a
-layered graph.
![](/cms/asset/9c1fdc6c-3381-499c-a9bf-352a86dc61c3/uakc_a_12092631_f0001_ob.jpg)
Assuming that each bridge of has two vertices of attachment, it is extremely convenient to use
to deduce things about
. For example, suppose
has a theta graph containing chords
,
, and
, and suppose
,
, and
correspond to the bridges
,
, and
. Then, we can deduce that
contains at least one theta graph whose three constituent paths go through
, and
(this occurs in —pick any three chords). The following lemma makes this example concrete.
Lemma 2.1
Let
be a subgraph of
. Then,
contains a subdivision of
.
Proof
To obtain the subdivision of in
, first take
. Then, for each chord in
, take a path through the corresponding bridge.
We will frequently make use of Lemma 2.1 by finding configurations of circles in and then pulling them up to
.
2.2 Negative and positive batteries
We are now ready to describe when a certain fixed edge is a battery. As a reminder, we assume that is a signed graph such that
is a block that is neither an isthmus, nor circle. Also,
is an edge of
, and
is a circle containing
. Our main theorem concerning edge batteries is as follows.
Theorem 2.2
The edge
is a battery if and only if
is
-layered,
is contained in a handle of
, and one of the following occurs:
1. | The other handle of
|
2. | Every path through a bridge of
|
The author thanks Thomas Zaslavsky for suggesting the following lemma, which helps simplify our proof method.
Lemma 2.3
Every edge in a signed subdivision of
lies in an even number of negative circles and an even number of positive circles.
Proof
Let be a signed subdivision of
, and let
be an edge of
. Then,
is contained in exactly four circles, denoted as
, and
. The labeling is chosen so that
. If
is a positive circle, then
and
must have the same sign, as well as
and
(here we are using the theta property). If
is a negative circle, then
and
have different signs, as do
and
. In either case, there is an even number of both positive and negative circles containing
.
Proof of Theorem 2.2
The reverse direction of the proof is easy. If is
-layered and
is contained in a handle, then clearly either of the two signature properties listed imply that
is a negative or positive battery respectively.
It remains to show the forward direction. Suppose is a battery contained in the unique signed circle
. If there exists some bridge
of
that has three or more vertices of attachment, then
contains a subdivision of
(containing all of
). By Lemma 2.3,
is contained in at least two circles that have the same sign as
in this subdivision—impossible by assumption that
is a battery in
. Thus, each bridge of
must have precisely
vertices of attachment (they cannot have
, since
is a block).
Replace each bridge of with a single chord between its vertices of attachment to form
. We will find configurations of circles in
and repeatedly use Lemma 2.1 without mention to pull them up to
. If
has two chords
and
that are crossing, then
is a subdivision of
containing
, once again impossible by Lemma 2.3. So we assume that
is a circle with noncrossing chords. Now we want to prove that
has exactly two handles and that
must be in one of them.
First, suppose that is contained in a segment of
that is not a handle. Thus, the segment of
containing
meets two different chords at its endpoints,
and
. Consider
. This graph has six circles, denoted as
, and
. We choose the labeling so that
and
and
, and
. This situation is illustrated in . If
is negative, then
,
, and
must be positive (they contain
). Since
and
, both
and
are positive. This implies that
is positive, a contradiction. Similarly, if
is positive, then
,
and
are negative. This implies that
and
are positive, but then
implies that
is negative, a contradiction. Thus, this case is impossible—
must be contained in a handle.
Now, we have with non-crossing chords and we know
is in a handle of
. All that remains is to show that there are exactly two handles. Suppose there are (at least) three handles, and let their corresponding chords be
,
, and
. Each handle along with its chord forms a circle, and we denote these
,
, and
, respectively. We choose labeling so that
, and we write
. This situation is illustrated in . If
is negative, then
and
and
are positive, which means
(and similarly
) are positive. However,
which implies that
is positive, a contradiction. Similarly, if
is positive then
is negative and
and
must again be positive. Therefore, the equality
contradicts the fact that
is positive. Consequently, there must be no more than two handles present. Note that under the assumption that
is not a single circle, less than two handles are also impossible.
Now that we have confirmed the structure of , we will examine the signature of
. We break this into two cases. First, suppose
is negative (so that
is a negative battery). Delete the handle of
not containing
(denoted as
), destroying the only negative circle containing
. The resulting
is still a block (clearly deleting a handle from a
-layered graph with at least one bridge does not create a cutpoint), and hence balanced (it contains
). Thus, we can switch
so that the only negative edge is contained in
(Lemma 1.1). This is the balancing edge described in the theorem.
If is positive, we observe that every path through a bridge of
between its vertices of attachment makes a negative circle with either half of
. To see this, it is convenient to switch
so that
is all-positive. Then, any path through a bridge of
between vertices of attachment must have a negative sign, otherwise this path along with
forms an all-positive theta graph containing
(and hence two positive circles containing
).
Consider a negative battery separated from a balancing edge
, and let
be the handle containing
. Clearly, every edge in
is a balancing edge. Moreover, no edge outside of
is a balancing edge. This is because
is a block, and thus
is contained in a circle besides
with any given edge in
. Thus we call
the balancing handle, since it contains all balancing edges of
. The presence of a single negative battery fixes
, and as a consequence, we are able to describe the location of all other negative batteries at the same time.
Theorem 2.4
Suppose
has a negative battery
separated from a balancing handle
. Let
be an edge contained in
and let
be the bridge of
containing
. Then
is a negative battery if and only if there is exactly one path through
that contains
.
Proof
If
is a negative battery there must only be one path through
containing it, since each path through
can be extended to a circle containing
. Conversely, if there is exactly one path through
that contains
, this path extends uniquely to a circle containing
.
Theorem 2.4 is illustrated in . As seen in the figure, the presence of a negative battery allows for the presence of many other negative batteries. Interestingly, the presence of a positive battery severely restricts the possible locations of other positive batteries.
![](/cms/asset/9f8eba8e-0b0d-4dc2-a120-b3f627550e9d/uakc_a_12092631_f0004_ob.jpg)
As an easy application of Theorem 2.2 we notice that if is a positive battery, every edge contained in either handle of
is a positive battery, and no other edge of
is a positive battery. We will now study edges that are contained in
.
Lemma 2.5
If
is a positive battery and
is a bridge of
, then
is balanced.
Proof
Suppose is a negative circle contained in
. Let
be a path through
that intersects
in a path
with at least one edge. Then, define
so that
. Since
is negative,
and
have opposite sign. Define
to be the path obtained by replacing
with
in
. Then,
and
have opposite sign—impossible by Theorem 2.2.
Theorem 2.6
Suppose
is a positive battery. If
has 3 or more bridges, no edge outside of
is a positive battery.
Proof
Let be an edge of
not contained in
. Since
is a positive battery,
is
-layered and hence all bridges of
have two vertices of attachment and are pairwise non-crossing. Let
, and
be three bridges of
with labeling chosen so that
. For convenience, we switch
so that
is all-positive. By Theorem 2.2, performing this switch makes all paths through
, and
negative. Let
be such a path through
that contains
, and let
and
be paths through
and
respectively. Then,
and
, together with two (possibly trivial) paths through
between the vertices of attachment of
and
, form a positive circle containing
. Similarly,
and
are contained in a positive circle containing
. Thus, we have found two positive circles containing
—it is not a positive battery.
If has less than
bridges it is possible to have positive batteries outside of
, though specific types of bridges are required.
Theorem 2.7
Suppose
is a positive battery and
has exactly
bridges. If both bridges are paths, every edge contained in either bridge is a positive battery. Otherwise, no edge in either bridge is a positive battery.
Proof
Let and
be the bridges of
. Once again we switch so that
is all-positive. If
and
are paths, then they are negative paths by Theorem 2.2. In this case,
and
along with the (possibly trivial) paths in
between their vertices of attachment form a positive circle. The fact that this is the only positive circle containing
and
is a matter of inspection.
Now, suppose that one of the bridges, say , is not a path. Since we are working within a block,
must contain a circle
. By Lemma 2.5,
is a positive circle. As in the proof of Lemma 2.5, let
be a path through
that intersects
in a path
that contains at least one edge. Define
so that
. Let
be the path obtained by replacing
with
in
. Let
be a path through
. Then,
, and
along with the appropriate paths through
form a theta graph with three positive circles, forcing every edge in
and
to be in at least
positive circles. Clearly for any edge
outside of
, a choice of
, and
can be found containing
.
Finally, we investigate the case where has only one bridge.
Theorem 2.8
Suppose
is a positive battery and
has exactly
bridge
. An edge
of
is a positive battery if and only if it is contained in a single circle in
.
Proof
Since is balanced (Lemma 2.5), any positive battery contained in
is contained in a single circle in
. In the other direction, suppose
is contained in a single (positive) circle in
. Then, any other circle containing
must consist of a path through
and a path through
. This will form a negative circle by Theorem 2.2.
3 Vertex batteries
Now let us examine a similar question to the one discussed in the previous section—when does a vertex of lie in a unique signed circle
? We will call such a vertex a vertex battery, written
or
for the negative and positive varieties, respectively. We cannot assume that
is a block, since a vertex, unlike an edge, may be contained in many blocks at once (if the vertex is a cutpoint). However, an acyclic block is of no interest to us. Thus, for the rest of this section we assume that every block containing
contains a circle.
First, we will study the problem of determining if is a negative vertex battery. It is clear that if
is a negative vertex battery, it is contained in one and only one unbalanced block
. Moreover, there is a restriction on
, the degree of
in
.
Lemma 3.1
Let
be an unbalanced block of
. If
, then
is not a negative vertex battery.
Proof
Certainly is contained in some negative circle
in
. Thus, consider the two edges incident to
, say
and
, that are contained in
. There is a third edge
incident with
, and therefore there must be some theta graph
such that
and also
. Therefore,
is contained in all three circles of
. Since
is negative,
contains an additional negative circle which contains
.
Assuming is a negative vertex battery, let
be the single unbalanced block containing
, and let
be the negative circle of
containing
. By Lemma 3.1,
, so let
and
be the two neighbors of
in
. We can suppress
—that is, replace the edges
and
with the single edge
, setting
. We write the result of the suppression as
. Thus, there is a bijective correspondence between the signed circles of
and the signed circles of
. Therefore, we have the following theorem, which reduces the vertex problem to the edge problem.
Theorem 3.2
Let
be a signed graph, and let
be a vertex of
. Then
is a negative vertex battery if and only if
1. | The block
|
2. |
|
We will now turn our attention to the problem of determining if a given vertex is a positive vertex battery. Our characterization of positive vertex batteries is analogous to our characterization of negative vertex batteries, though slightly more complicated. Just as a negative vertex battery may be contained in many blocks in which it is contained in only positive circles (balanced), but only one block in which it is contained in a negative circle, a positive vertex battery may be contained in many blocks in which it is contained in only negative circles, but only one block in which it is contained in a positive circle.
We will first describe when an edge is contained in only negative circles and then convert this to a description of vertices.
Lemma 3.3
An edge of
is contained in only negative circles if and only if it is a balancing edge in the block containing it.
Proof
Let be an edge of
and let
be the block containing it. First, if
is a balancing edge in
, then
is clearly contained in only negative circles (switch so that
is the only negative edge).
In the other direction, suppose that is contained only in negative circles. Consider
. Suppose there is a negative circle
contained in
. Then, since
is a block, there is a theta graph containing both
and
, forcing
to be in a positive circle—impossible. Thus,
is balanced and can hence be switched to all-positive by a switching function
. However, applying
to
instead will leave
as a negative edge, since
is contained in only negative circles. Thus,
is a balancing edge in
.
We can now characterize the type of block in which is contained only in negative circles.
Lemma 3.4
A vertex
is contained only in negative circles in
if and only if
is degree
in
, and
is a balancing edge in
.
Proof
If is degree
in
and
is a balancing edge, then clearly
is contained in only negative circles by Lemma 3.3.
Conversely, if is contained in only negative circles, then
is not balanced. If
, then
is contained in a negative circle
and furthermore
is a degree
vertex in a theta graph containing
. Hence,
is contained in a positive circle—impossible. Thus,
, and we can suppress
to obtain the result.
Now we will describe the blocks in which is contained in exactly one positive circle. This along with Lemma 3.4 will complete the description of positive vertex batteries.
Lemma 3.5
A vertex
is contained in a unique positive circle
in a block
if and only if one of the following occurs:
1. |
|
2. |
|
3. |
|
Proof
If and
satisfy either of the first two conditions above, then clearly
is contained in a unique positive circle in
. If
and
satisfy the third condition, observe that any circle besides
that contains
must consist of a path through the single bridge and a handle of
—a negative circle.
In the other direction, suppose is contained in a unique positive circle in
. If
is balanced, it consists of only a single positive circle or else
is contained in multiple positive circles.
So, suppose that is unbalanced and consider the case where
. Let
be four edges incident with
, so that
and
are contained in
. Since
is a block, we can find a theta graph
that contains
, and
(up to choice of labels). Furthermore, there is a path
containing
starting at
and ending at a vertex of
(besides
). It is easy to see that
contains at least two positive circles that contain
.
Now we consider the case where is unbalanced and
. Find a theta graph
that contains
such that
. Observe that
is
-layered, with a single bridge
consisting of a path. There can be no path connecting an internal vertex of
to an internal vertex of a handle of
, or else we create a subdivision of
, forcing
to be in more than one positive circle. There can be no path besides
connecting two vertices of
, or else there is a second positive circle containing
. Thus, any path besides
connecting two vertices of
must have both its endpoints in
and be otherwise disjoint from
. Since
, no such path will contain
. The union of all such paths forms a single bridge of
, of which
is a vertex of attachment.
Finally, we combine the results of this section to give a complete description of whether or not is a positive vertex battery. As a reminder, we assume that each block containing
contains at least one circle.
Theorem 3.6
Let
be a signed graph, and let
be a vertex of
. Then
is a positive vertex battery if and only if:
1. | The block containing
|
2. | In any other block
|
Proof
A positive vertex battery must be contained in exactly one block in which it is contained in a unique positive circle. It must be contained in no positive circles in all other blocks containing it. Thus, the proof is a combination of Lemmas 3.5 and 3.4.
Notes
Peer review under responsibility of Kalasalingam University.
References
- Harary F. On the notion of balance of a signed graph Michigan Math. J. 2 2 1953 143 146
- Harary F. On local balance and N-balance in signed graphs Michigan Math. J. 3 1955 37 41
- Zaslavsky T. Signed graphs Discrete Appl. Math. 4 1982 47 74
- Sozański T. Enumeration of weak isomorphism classes of signed graphs J. Graph Theory 4 1980 127 144