Reza Naserasr

Éric Sopena

Thomas Zaslavsky

Homomorphisms of signed graphs: An update

Keywords: Signed graph; edge-colored graph, graph homomorphism, packing

A signed graph is a graph together with an assignment of signs to the edges. A closed walk in a signed graph is said to be positive (negative) if it has an even (odd) number of negative edges, counting repetition. Recognizing the signs of closed walks as one of the key structural properties of a signed graph, we define a homomorphism of a signed graph (G, σ) to a signed graph (H, π) to be a mapping of vertices and edges of G to (respectively) vertices and edges of H which preserves incidence, adjacency and the signs of closed walks.

In this work we first give a characterization of the sets of closed walks in a graph G that correspond to the set of negative closed walks in some signed graph on G. We also give an easy algorithm for the corresponding decision problem.

After verifying the equivalence between this definition and earlier ones, we discuss the relation between homomorphisms of signed graphs and those of 2-edge-colored graphs. Next we provide some basic no-homomorphism lemmas. These lemmas lead to a general method of defining chromatic number which is discussed at length. Finally, we list a few problems that are the driving force behind the study of homomorphisms of signed graphs.

Introduction

The notion of homomorphisms of signed graphs was first defined by B. Guenin in an unpublished manuscript. The development of the subject started from [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]. It also appeared under a different context at [START_REF] Brewster | Edge-switching homomorphisms of edge-coloured graphs[END_REF]. The theory extends the classical notion of graph homomorphism and is strongly related to the theory of homomorphisms of 2-edge-colored graphs, but has the main advantage of correlating with the theory of graph minors.

Being unsatisfied with the definition and terminology employed in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF], here we present a more natural definition which leads to a number of simple no-homomorphism lemmas, special subclasses and some characterization theorems. The new definition is based on closed walks and their signs, thus we study them at length. The notion of chromatic number of a signed graph, introduced long ago by Zaslavsky [START_REF] Zaslavsky | How colorful the signed graph? Discrete Math[END_REF], has recently drawn considerable attention with a variety of definitions offered. We will show how one such definition can be regarded as an optimization question with certain restrictions. At the end, we list only a few of the most motivating questions of this theory.

Toward a comprehensive study, we will begin with terminology and notation. This is of particular importance due to the diversity of terminology being used in the study of signed graphs. The following section is on the signs of cycles and closed walks, which we consider as basic elements of signed graphs. Section 4 is on the main subject of this work, homomorphisms of signed graphs, and the last section is about motivating problems, noting that the number of open problems is too large to be listed.

Terminology and Notation for Graphs and Signed Graphs

Graphs

We allow a graph G = (V (G), E(G)) to have loops and multiple edges. Thus the vertex and edge sets are disjoint, and each edge is provided with a multiset of two vertices, called its endpoints. If the endpoints are equal, the edge is a loop; if not, it is a link. Different edges may have the same multiset of endpoints; then they are called parallel edges. By having a set of edges instead of a multiset, we can have functions that differ on parallel edges.

An edge cut [X, Y ] of G is the set of all edges with one endpoint in X and another in Y , where X and Y form a partition of V (G).

A walk of G is a sequence W = v 0 e 1 v 1 e 2 • • • , e k v k where for each e i its endpoints are v i-1 and v i (thus if e i is a loop we must have v i = v i-1 ). Its length is k and its parity is the parity of k. It is a closed walk if we have v k = v 0 . An trivial walk is a walk of length 0, i.e., with one vertex and no edge; this is considered a closed walk. The inverse of W is the walk

W -1 = v k e k • • • e 2 v 1 e 1 v 0 . The walk W is a path if there is no repeated element. It is a cycle if k ≥ 1, v 0 = v k ,
and that is the only repetition of elements in the walk. Thus loops are cycles of length 1 and parallel edges form cycles of length 2. Given two walks W 1 = v 0 e 1 v 1 e 2 • • • e k v k and W 2 = v k e k+1 v k+1 e k+2 • • • e k+l v k+l (W 2 starts at the end of W 1 ) the walk v 0 e 1 v 1 e 2 • • • e k v k e k+1 v k+1 e k+2 • • • e k+l v k+l is denoted by W 1 W 2 . We often omit the vertices from the sequence defining a walk, since they are usually obvious; thus W may be written as e 1 e 2 • • • e k . A closed walk W = v 0 e 1 v 1 e 2 • • • e k v k may be rotated to begin at a different vertex, giving a walk v i-1 e i v i • • • e k v k e 1 v 1 • • • e i-1 v i , which we call a rotation of W .

A theta graph is a graph that consists of three paths joining the same two vertices, but which are otherwise pairwise disjoint. Theta subgraphs of a graph are important in signed graph theory.

2-edge-colored graphs

A 2-edge-colored graph, Γ = (V (Γ), E 1 (Γ), E 2 (Γ)), is a graph where the set of edges is decomposed into two disjoint subsets. That is, we have two colors and we associate one of them to each edge of Γ. Thus, we have a mapping E(Γ) → C, where C is the set of two colors.

Signed graphs

A signed graph is a graph G together with an assignment σ : E → {+, -} of a sign (+ or -) to each edge of G. We call G the underlying graph, and σ is called the signature. We may denote this signed graph by (G, σ) or sometimes by G. A signed graph where all edge are positive is denoted by (G, +) and called all positive, and similarly if all edges are negative it will be denoted by (G, -) and called all negative.

We call a signed graph (G, σ) connected, bipartite, etc. when G is connected, bipartite, etc.

The signed graph (G, σ) may be thought of as a 2-edge-colored graph (G, E + , E -), where E + and E -denote the sets of positive and negative edges, respectively; but that does not express the fact that signs + and -are essentially different. The difference between a signed graph and a 2-edge-colored graph is on the notion of sign of a closed walk in (G, σ). For any walk W = e 1 e 2 • • • e l , of a signed graph (G, σ), the sign of W is σ(W ) := σ(e 1 )σ(e 2 ) • • • σ(e l ). Then W is said to be positive or negative depending on the value of σ(W ). Since a cycle of a graph is also a closed walk we naturally have the definition of positive cycles and negative cycles. It is clear that the signs of cycles determine the signs of all closed walks.

Signs of cycles determine many fundamental properties of a signed graph. The most important is balance. A signed graph (G, σ) is said to be balanced if every cycle is positive. It is said to be antibalanced if (G, -σ) is balanced. These two subclasses of signed graphs together with the subclass of signed bipartite graphs form three subclasses of signed graphs which will be shown to be of special interest in Section 4.6.

A closely related notion is the notion of switching1 : to switch a vertex v of a signed graph (G, σ) is to negate all signs in the edge cut [{v}, V (G) \ v]. To switch a set X of vertices is to switch all the vertices of X in any sequence; it has the effect that it negates the edges in the cut [X, Y ], which is the same as switching the complementary set Y . A fundamental though obvious fact is that switching does not change the signs of closed walks. An equivalent property to balance is that, after a suitable switching, every edge is positive; equivalent to antibalance is that, after suitable switching, every edge is negative.

Historically, a notion similar to that of edge signs in the form of a distinguished edge set appeared in the first book on graph theory, published by D. König in 1936 [14, Chapter X, Section 3]. This work contains many basic results about signed graphs (in its own terminology), as detailed in its entry in [START_REF] Zaslavsky | A mathematical bibliography of signed and gain graphs and allied areas[END_REF]. The essential concepts of edge and cycle signs were first introduced by Harary [START_REF] Harary | On the notion of balance of a signed graph[END_REF]. Switching in the form of set summation with a vertex cut is employed by König, but further use of switching of signed graphs begins only much later in [START_REF] Zaslavsky | Characterizations of signed graphs[END_REF][START_REF] Zaslavsky | Signed graphs[END_REF].

Two signatures σ 1 and σ 2 on the same graph G are said to be switching equivalent if one is obtained from the other by switching. The set of negative closed walks or negative cycles determines the class to which a signature belongs.

Lemma 1 (Zaslavsky [START_REF] Zaslavsky | Signed graphs[END_REF]Theorem 3.2]). Given two signatures σ 1 and σ 2 of a graph G, σ 1 is a switching of σ 2 if and only if the sets of positive (or, equivalently, negative) cycles of (G, σ 1 ) and (G, σ 2 ) are the same.

The proof given in [START_REF] Zaslavsky | Signed graphs[END_REF] is based on two key observations which we would like to state separately:

Lemma 2. For a tree T , any two signatures σ 1 and σ 2 are switching equivalent.

Lemma 3. Given a connected graph G, a signature σ of G, a spanning tree T and signature τ of T there is a unique signature σ which is identical to τ on the edges of T and is switching equivalent to σ.

The proof of this lemma is based on the following key notions: given a spanning tree T of G and an edge e of G which is not in T , the subgraph induced by e and edges of T forms a unique cycle in G, denoted by C e . The cycles C e are called the fundamental cycles of G with respect to T . The set of fundamental cycles with respect to a spanning tree is called a fundamental system of cycles for G. The lemma is then proved by observing the relation between the sign of e and the sign of C e .

The remark following [START_REF] Zaslavsky | Characterizations of signed graphs[END_REF]Theorem 2] states a stronger result: that there is a oneto-one correspondence between the classes of switching equivalent signatures on G and subsets of a fundamental system of cycles of G, regarded as the positive fundamental cycles. It follows that the number of signatures on G which are pairwise not switching equivalent is 2 e-n+c where e is the number of edges, n is the number of vertices and c is the number of connected components.

These lemmas together also imply a fast algorithm to decide whether two signatures σ 1 and σ 2 on a graph G are switching equivalent: Choose a spanning tree T . Switch both σ 1 and σ 2 to σ 1 and σ 2 so that they agree on T . Check if σ 1 = σ 2 . This simple method, presented in [START_REF] Zaslavsky | Signed graphs[END_REF]Lemma 3.1], is essentially the same as the test for balance found independently by Hansen [START_REF] Hansen | Labelling algorithms for balance in signed graphs[END_REF] and Harary and Kabell [START_REF] Harary | A simple algorithm to detect balance in signed graphs[END_REF], which switches σ to be all positive on T and deduces balance of (G, σ) if and only if there is no negative edge in (G, σ). Proposition 4. It can be decided in time quadratic in the order of a graph G whether two given signatures on G are switching equivalent.

Proof. Here is a 6-step algorithm, assuming G is connected. After Step 1, it is the algorithm of Hansen [START_REF] Hansen | Labelling algorithms for balance in signed graphs[END_REF] and Harary-Kabell [START_REF] Harary | A simple algorithm to detect balance in signed graphs[END_REF].

Step 1. Multiply the two signatures: σ(e) = σ 1 (e)σ 2 (e). Time: O(n 2 ). It is easy to see that σ 1 and σ 2 are equivalent if and only if σ is balanced.

Step 2. Find a rooted spanning tree, (T, r). Time: O(n 2 ).

Step 3. Label each vertex u by the sign in (G, σ) of the path from r to v in T . Time: O(n 2 ) at worst. This step can be integrated into Step 2.

Step 4. Find the set X of negative vertices. Time: O(n).

Step 5. Negate the signs of edges in the cut [X, V (G) \ X]. Time: O(n 2 ). Note that now all edges in T are positive.

Step 6. Search for a negative edge. Time: O(n 2 ).

If there is no negative edge, σ is balanced and the original signatures are switching equivalent. If there is a negative edge, σ is unbalanced and the original signatures are not equivalent.

Positive and Negative Elements of the Cycle Space

Given a signed graph G, the set of cycles and the set of closed walks of the underlying graph G are each divided into the two sets of positive and negative elements. We think of the signature as determining sets of negative cycles and closed walks.

These subsets are among the fundamental properties of a signed graph, along with incidence and adjacency; thus we have two basic questions: Given a subset W of the closed walks in a graph G, does W correspond to a set of negative (equivalently, positive) closed walks in (G, σ) for some signature σ of G? If yes, can we find one such σ by an efficient algorithm?

One might emphasize the set of positive cycles or positive closed walks, especially because the former forms a subspace of the cycle space of G. However, in the study of signed graphs and specially in the study of homomorphism which is the central part of this work, negative cycles and closed walks are of higher importance. In fact, negative cycles extend the role which odd cycles play in many parts of graph theory. For this reason, some authors have used the term "odd cycle" in a signed graph to refer to negative cycles, even when they have even length! Observe that the set of all cycles of G could be of exponential order (in the order of G) and that as long as G contains an edge, the set of closed walks in G is an infinite set. However, as we mentioned in the previous subsection and will discuss later in this section, the subset of negative closed walks can be finitely presented, e.g., by a subset of a fundamental system of cycles of G.

Considering cycles rather than all closed walks, an analogue of the first question has already been addressed in [START_REF] Zaslavsky | Characterizations of signed graphs[END_REF] using the following definition: Definition 5 (Theta Co-Additivity). A set C of cycles of a graph G is theta co-additive if, for every theta subgraph Θ of G, the number of cycles in Θ that belong to C is even.

It is then proved that: Lemma 6 ( [START_REF] Zaslavsky | Characterizations of signed graphs[END_REF]). A set C of cycles in a graph G is the set of negative cycles of (G, σ) for some choice of signature σ if and only if C satisfies theta co-additivity.

Systems of closed walks

As we will see later, in the study of homomorphisms of signed graphs we may have to consider closed walks that are not cycles; for example see Lemma 17 and Figure 1. Thus we introduce the following notion which, working with the set of closed walks rather than just cycles, extends the notion of theta co-additivity. Then we provide a similar tool to test whether a given set W of closed walks in G is the exact set of negative closed walks of (G, σ) for some choice of a signature σ. This test can, in particular, be used for a NO-certificate. We then present an algorithm by which we can answer the algorithmic part of the question and produce one such signature if the output is YES. Our algorithm is efficient with the condition that C is presented efficiently and that testing membership in C can be done efficiently. Our first test is based on the following definitions.

Definition 7 (Rotation property). A set W of closed walks is said to have the rotation property if, for each closed walk P Q (the concatenation of walks P and Q), either P Q and QP are both in W or neither of them is in W.

Definition 8 (Exclusive 3-walk property). A set W of closed walks in a graph G satisfies the exclusive 3-walk property if it has the rotation property and, for every two vertices x and y (not necessarily distinct) of G and every three xy-walks W 1 , W 2 and W 3 of G,

W 1 W -1 2 ∈ W ⇒ (W 1 W -1 3 ∈ W) (W 2 W -1 3 ∈ W),
where denotes the "exclusive or" operator. That is to say, given any two vertices x and y, among the three closed walks induced by any three xy-walks, an even number is in the set W, i.e., either none of them or exactly two of them.

(We thank Andrzej Szepietowski [START_REF] Szepietowski | Negative closed walks in signed graphs: A note[END_REF] and an anonymous referee for pointing out the need to assume the rotation property.)

We give algebraic formulations. The characteristic sign function of closed walks with respect to W is

σ W (W ) = + if W / ∈ W, and -if W ∈ W.
In terms of this function, Definition 7 becomes the formula

σ W (P Q) = σ W (QP ) (1)
if P is an xy-walk and Q is a yx-walk, and the implication of Definition 8 becomes the formula

σ W (W 1 W -1 2 )σ W (W 1 W -1 3 )σ W (W 2 W -1 3 ) = +. ( 2
)
Using this definition, we can characterize the sets W of closed walks in a graph G that can be the set of negative closed walks in (G, σ) for some choice of signature σ, by the fact that they satisfy the exclusive 3-walk property (see Theorem 10). As it is easy to prove that the set of negative closed walks of a signed graph satisfies the property, our main goal is to show that if a set W of closed walks in G satisfies the exclusive 3-walk property then W is the set of negative closed walks in (G, σ) for a signature σ of G. Being such a set would imply certain properties, for example that a trivial walk cannot be a member of W as it is positive by definition. We collect such properties in the following proposition and provide a proof solely based on the exclusive 3-walk property. Proposition 9. Let G be a graph and let W be a set of closed walks which satisfies the exclusive 3-walk property. Then W satisfies the following properties:

[i] No trivial walk is in W. (I.e., σ W (W 0 ) = + for every trivial walk W 0 .)

[ii] For any walk W , the closed walk W W -1 is not in W. (I.e., σ W (W W -1 ) = +.)

[iii] For any closed walk W , we have W -1 ∈ W if and only if W ∈ W. (I.e., σ W (W -1 ) = σ W (W ).)

[iv] For any pair of closed walks W and W with the same end point v, W W is in W if and only if exactly one of W and W is in W. (I.e., σ W (W W ) = σ W (W )σ W (W ).)

[v] Given a closed walk W starting at y and an xy-walk P , P W P -1 is in W if and only if W is in W. (I.e., σ W (P W P -1 ) = σ W (W )).

Proof. By taking W as a trivial walk we observe that the first claim is a special case of the second. Thus we jump to proving the second claim. For this, we take

W 1 = W 2 = W 3 = W .
Then the three closed walks in the exclusive 3-walk property are all W W -1 but a condition for W is that all three cannot be in W.

For [iii], let v be the start of W and for x = y = v take W 1 = W and W 2 = W -1 and let W 3 be the trivial walk at v. Then the three xy-walks to be considered are W , W -1 and W W -1 . By part [ii], the last one is never in W, thus we have our claim.

For [iv] take x = y = v and consider W 1 = W , W 2 = v (the trivial walk at v) and W 3 = (W ) -1 . Then the three walks considered in the exclusive 3-walk property are W , W and W W . By Equation 2,

σ W (W )σ W (W )σ W (W W ) = +.
For [v] rotate P W P -1 to W P -1 P ; then apply [iv] and [ii].

Theorem 10. A set W of closed walks in a graph G is the set of negative closed walks in (G, σ) for some choice of signature σ if and only if W satisfies the exclusive 3-walk property.

Proof. We will prove the theorem for connected graphs. For graphs with more than one connected component we may apply the proof to each connected component of the graph. First we consider a signed graph (G, σ) and we show that the set W -of the negative closed walks in (G, σ) satisfies the exclusive 3-walk property. Consider two vertices x and y (not necessarily distinct) and let W 1 , W 2 and W 3 be three xy-walks in (G, σ). Then

σ(W 1 W -1 2 )σ(W 1 W -1 3 )σ(W 2 W -1 3 ) = σ(W 1 ) 2 σ(W 2 ) 2 σ(W 3 ) 2 = +,
thus verifying the exclusive 3-walk property in the form of Equation (2).

To prove the converse, let W be a set of closed walks in G satisfying the exclusive 3-walk property. We need to show that there exists a signature σ of G such that the set of negative closed walks in (G, σ) is exactly W. A cycle C of G can be viewed as a closed walk starting at a vertex of the cycle. By Proposition 9 [vi], whether this closed walk is in W or not is independent of the choice of the starting vertex. Thus we may simply talk about a cycle being in W. We then use a fundamental system of cycles of G to define a signature σ. Let T be a spanning tree of G and for each edge e / ∈ T let C e be the fundamental cycle, with respect to T , that contains e. Define a signature σ by

σ(e) = + if e ∈ T, σ W (C e ) if e / ∈ T.
It remains to show that σ(W ) = σ W (W ) for every closed walk W . We prove this by induction on the number of edges that are not in T . By Proposition 9 a trivial walk W 0 is not in W so σ W (W 0 ) = + = σ(W 0 ). Let W be a closed walk which uses only edges of T . As T has no cycle, the induced subgraph by the edges of W must have a vertex y of degree 1. Let x be the neighbour of this vertex in T . Let P be the walk xey where e = xy. Then W can be written as W P P -1 , where W has two fewer edges than W . By Proposition 9 σ W (W ) = σ W (W ). By repeating this process we conclude that

σ W (W ) = σ W (W 0 ) = + = σ(W ).
To complete the induction we consider a closed walk W which uses k edges not in T (counting repetitions), k ≥ 1. Let e = xy be one such edge. We build a new walk W which uses k -1 edges not in T and such that σ W (W ) = σ W (W )σ(e). By Proposition 9 we may rotate and, if necessary, invert W so that it starts with Q = xey and continues with W , so W = QW . Let P be the xy-path obtained from C e after removing the edge e. Observe that all edges of P are in T . Let W = P W . Note that W has one less edge not in T than W does.

Consider the following three xy-walks:

W 1 = Q, W 2 = P and W 3 = (W ) -1 . Then W 1 W -1 2 = C e , W 1 W -1 3 = W and W 2 W -1 3 = W . By Equation (2), σ W (W 1 W -1 2 )σ W (W 1 W -1 3 )σ W (W 2 W -1 3 ) = +; more simply, σ W (C e )σ W (W )σ W (W ) = +. So, σ W (W ) = σ W (Ce)σ W (W ) = σ(e)σ W (W )
by the definition of σ, = σ(e)σ(W ) by induction, = σ(e)σ(P )σ(W ) = σ(e)σ(W ) because all edges of P are in T , = σ(W ).

Algorithmics of closed walk systems

Given a closed walk W of graph G, let C W be the subgraph of G which is induced by edges which appear on W an odd number of times. Then C W has no repeated edges, so it is an edge-disjoint union of cycles. Equivalently, every vertex has even degree in C W ; such a subgraph is called an even subgraph. Given a signature σ on G, the product of the signs of cycles in C W determines whether W is a negative closed walk or a positive one. Observe that while the set of closed walks in a graph with at least one edge is an infinite set, the set of even subgraphs is a finite set because each even subgraph uses each edge at most once. Thus in practice we may use a chosen set of even subgraphs (a finite set) to define a choice of negative (or positive) closed walks (an infinite set). The question is then, what conditions on a set of even subgraphs make it the set of negative (or positive) even subgraphs C W of some signature on G.

Consider a subset W of closed walks in G that may, or may not, be the set of all negative closed walks in some signed graph on G. Then the choice of W corresponds to a choice of C W 's. Thus a first necessary condition for W to be the set of negative closed walks in (G, σ) for some choice of σ is that the two sets {C W | W ∈ W} and {C W | W / ∈ W} have no common element. Observe that the set of all even subgraphs corresponds to the (binary) cycle space of the graph G, which is the set of binary vectors in Z E 2 , of length |E(G)|, which are in the null space of the vertex-edge incidence matrix of G regarded as a binary matrix. The (binary) characteristic vector of a closed walk W equals that of the corresponding even subgraph C W . If we identify a subset of edges with its characteristic vector, then binary addition corresponds to set summation (that is, symmetric difference). Assume G is connected and let W 1 and W 2 be two closed walks in G. By adding a P P -1 walk and rotating the walks, as needed, we may assume W 1 and W 2 are starting from the same vertex, observing that the C W i will remain the same. Then the set sum C W 1 + C W 2 , which corresponds to the binary sum of the characteristic vectors of W 1 and W 2 , equals C W 1 W 2 (noting that W 1 W 2 is only defined if they have a common starting point).

For a signed graph (G, σ) the even subgraphs whose elements correspond to positive closed walks in (G, σ) form a subspace of the cycle space of codimension at most 1, and every such subspace is the set of even subgraphs that are positive in some signature of G [START_REF] Zaslavsky | Characterizations of signed graphs[END_REF]. We may then use the notion of basis in linear algebra to present a choice of negative even subgraphs using only a linear number of edges, by using the notion of a fundamental system of cycles with respect to a spanning tree. Let T be a spanning tree of G. For an edge e / ∈ E(T ), the fundamental cycle of e with respect to T is the unique cycle contained in T ∪ e. An elementary consequence of Lemma 1 is that, given a signature σ on G with negative edge set E -, defining σ T (e) := σ(C e ) if e / ∈ E(T ) and σ T (e) := + if e ∈ E(T ), then σ T is switching equivalent to σ.

Using this terminology, we state in the next theorem how a subset of all the closed walks (an infinite set) satisfying the exclusive 3-path property can be presented by a choice of a negative edge set.

Theorem 11. Let G be a connected graph with a spanning tree T . Let W be a subset of the closed walks in G that satisfies the exclusive 3-path property. Let E -be the set of edges e / ∈ E(T ), such that C e is in W. Then a closed walk W is in W if and only if C W can be written as the sum of C e 's where an odd number of e's in is E -. Proof. By Theorem 10, the assumption on W is equivalent to assuming that it is the class of negative closed walks of a signature σ on G.

If that is true, by Lemma 3 we may switch σ so that every edge of T is positive. Then

σ(W ) = σ(C W ) = e∈E(C W )\E(T ) σ(e).

Homomorphisms

Graphs

The main goal of this work is the study of homomorphisms of signed graphs with special focus on improving terminology. To this end we first offer an alternative definition of a graph homomorphism as follows (recall that we are allowing loops and multiple edges): Definition 12. A homomorphism of a graph G to a graph H is a mapping f which maps vertices of G to vertices H and edges of G to the edges of H and preserves the incidence relation between vertices and edges. We indicate the existence of a homomorphism by writing G → H.

This contrasts with the usual definition, in which graphs are assumed to be simple, the vertex mapping is assumed to preserve adjacency (but not non-adjacency) and then the edge mapping is determined by the vertex mapping. Since signed graphs have multiple edges that may have different signs, that kind of definition is inadequate.

Signed graphs

We may now define the central concept of this work: Definition 13. A homomorphism of a signed graph (G, σ) to a signed graph (H, π), written (G, σ) → (H, π), is a graph homomorphism that preserves the signs of closed walks. More precisely, this is a switching homomorphism of signed graphs. We indicate the existence of a homomorphism by the notation (G, σ) → (H, π).

Intuitively speaking, since we consider the signs of cycles of a signed graph as one of its determining characteristics, we define a homomorphism of signed graphs to be a mapping that preserves the main structures: incidences and cycle signs.

One can redefine homomorphisms of signed graphs in terms of edge signs. A edgesign-preserving homomorphism of a signed graph (G, σ) to a signed graph (H, π) is a homomorphism of underlying graphs, G → H, that preserves the signs of edges. Theorem 14. A homomorphism (G, σ) → (H, π) of signed graphs consists of a switching of (G, σ) followed by an edge-sign-preserving homomorphism to (H, π), and conversely.

Proof. We first show the easy part. Suppose (G, σ) switches to (G, σ ) such that there is a graph homomorphism φ : G → H that preserves edge signs. Since φ preserves edge signs, it preserves the signs of all walks. The signs of closed walks are the same in (G, σ) and in (G, σ ), so φ, considered as a mapping of signed graphs (G, σ) → (H, π), preserves the signs of closed walks.

For the contrary, suppose φ is a signed graph homomorphism (G, σ) → (H, π); thus, φ is a graph homomorphism G → H and preserves the signs of closed walks. Let σ be a new signature which assigns to each edge e of G the sign of φ(e) in (H, π). Then φ, as a mapping from (G, σ ) → (H, π), preserves the signs of closed walks and in particular the signs of cycles. Each cycle C in G has the same sign with respect to σ and σ , as both signs equal the sign of φ(C) in (H, π). It then follows from Lemma 1 that σ is a switching of σ.

The definition of a homomorphism of one signed graph to another, contained in this theorem, is the one originally given in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF], and in practice is easier to use. To be more precise, in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] a homomorphism of (G, σ) to (H, π) is a mapping f = (f 1 , f 2 , f 3 ) where f 1 : V (G) → {+, -} specifies for each vertex x whether x is switched or not, f 2 : V (G) → V (H) specifies to which vertex of V (H) the vertex x is mapped to and, similarly, f 3 : E(G) → E(H) is the edge mapping. When working on graphs with no parallel edges, one may simply write (f 1 , f 2 ) as f 3 would be uniquely determined by f 2 .

Bipartite universality

What is rather surprising, and not so obvious, is that the restriction to signed bipartite graphs also captures the classic notion of homomorphism of graphs. With any graph G, we associate a signed bipartite graph S(G) defined as follows: for each edge uv of G, we first add a parallel edge, and then subdivide both edges in order to form a 4-cycle (if G has n vertices and m edges, S(G) has thus n + 2m vertices and 4m edges). Finally, for each such 4-cycle, we assign one negative and three positive signs to its edges. That is, we replace each edge uv of G by a 4-cycle with one negative edge in which u and v are not adjacent. The following is proved in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF].

Theorem 15. Given graphs G and H, there is a homomorphism of G to H if and only if there is a homomorphism of S(G) to S(H).

It is thus of special interest to study the homomorphism relation on the subclass of signed bipartite graphs. Indeed, as is discussed in Section 6, the study of homomorphisms of signed graphs was originated in order to address a possible extension of the Four-Color Theorem that is partly on the family of signed bipartite graphs and partly on that of antibalanced signed graphs.

Core

A common notion in the theory of homomorphisms is the notion of core, which is defined analogously for each of the structural objects. A core is a graph (or a signed graph; or a 2-edge-colored graph-see Section 5) which does not admit any homomorphism to one of its proper subgraphs. The core of a graph G is then the smallest subgraph of G (with respect to subgraph inclusion) to which G admits a homomorphism. It is clear, in each case, that the core of a graph is a core, and it is not difficult to show that the core of a graph is unique up to isomorphism.

Isomorphism and transitivity

Any adaptation of a notion of homomorphism leads to a corresponding notion of isomorphism. An isomorphism, more precisely a switching isomorphism, from (G, σ) to (H, π) is a homomorphism φ that has an inverse, i.e., a homomorphism θ : (H, π) → (G, σ) such that the compositions φ • θ and θ • φ are the identity self-mappings: φ • θ = id (H,π) and θ • φ = id (G,σ) . Equivalently, φ is a graph isomorphism that preserve the signs of closed walks; it follows easily that θ is also such a graph isomorphism. We write φ -1 for θ and call it the inverse isomorphism to φ.

We say that (G, σ) is isomorphic to (H, π) if there is an isomorphism of (G, σ) to (H, π)

An automorphism of a signed graph (G, σ) is an isomorphism of (G, σ) to itself. The set of all automorphisms of (G, σ) forms the automorphism group of (G, σ).

We say, as with unsigned graphs, that a signed graph (G, σ) is vertex transitive if for any two vertices x and y of G, there exists a automorphism of (G, σ) which maps x to y. That is, the automorphism group is transitive on V . We define edge transitivity similarly.

Girth and no-homomorphism lemmas

That the parity of a closed walk must be preserved by a homomorphism is the key fact that makes most graph homomorphism problems NP-hard. However, it also leads to a no-homomorphism lemma based on the easily computable parameter of odd girth (the least length of an odd cycle): the image of every odd cycle must contain an odd cycle which, therefore, is of smaller or equal length. Thus if G → H, then the shortest odd cycle of G is at least as big as the shortest odd cycle of H.

With homomorphisms of signed graphs asking to preserve signs of closed walks, we have four types of essentially different closed walk to consider: positive even closed walks, positive odd closed walks, negative even closed walks and negative odd closed walks. Given a homomorphism of (G, σ) to (H, π), images of closed walks of a given type in (G, σ) must be of the same type in (H, π).

We will say that a positive even walk is of type 00, a negative even walk is of type 10, a positive odd walk is of type 01 and a negative odd walk is of type 11. This notation is convenient in the following sense: given closed walks W 1 of type ij and W 2 of type i j , both starting at a same vertex, the type of closed walk W 1 W 2 is the binary sum of the two types, that is ij + i j where addition is done in Z 2 2 . We may now introduce four separate notions of girth based on walks, one for each of the four types of closed walk: Definition 16 (Walk-girths of signed graphs). Given a signed graph (G, σ), for each walk type ij we define the length of a shortest nontrivial closed walk of that type in (G, σ) to be the ij-walk-girth of (G, σ) and denote it by g ij (G, σ). When there is no such walk, we write

g ij (G, σ) = ∞.
For simplicity, we use the term girth of type ij to denote the walk-girth of type ij.

As the examples of Figure 1 show, a walk-girth of type ij is not always obtained by a cycle; thus we use term walk-girth. Observe that g 00 (G, σ) is either ∞ (when G has no edge) or it is 2. While g 00 is thus not of much interest, the other three values are of high interest in the study of homomorphisms of signed graphs. Indeed we have the following no-homomorphism lemma from the definition. Lemma 17. If a signed graph (G, σ) admits a homomorphism to a signed graph (H, π),

then g ij (G, σ) ≥ g ij (H, π) for each ij ∈ Z 2 2 .
To emphasize the importance of Lemma 17, we show that given a signed graph (G, σ) one can compute g ij (G, σ) for all four choices of ij in polynomial time.

Proposition 18. Given a signed graph (G, σ) of order n we can compute g ij (G, σ) in time O(n 4 ).

Proof. Our method is that, for each vertex v of G, we compute in time O(n 3 ) the length of a shortest closed walk of type ij which starts at v. Taking the minimum of all such values then gives g ij (G, σ). (The length of the input is O(n 2 ) because we assume no parallel edges in (G, σ) have the same sign.)

We use the following notation: N i (v) is the set of vertices that are at distance i from v in G. Moreover, for = +, -, we define N i (v) to be the set of vertices at distance i from v that can be reached from v by a path P of length i and sign . Observe that these sets can be built inductively: given N + i (v) and N - i (v) for i = k -1, vertices not already reached which are adjacent to some vertex in N + i (v) with an edge of sign or to some vertex in N - i (v) with an edge of sign -form N k (v). The time to construct the sets

N k (v) for each vertex v is O(n 3 ). Each set satisfies |N k (v)| = O(n). Each vertex in N k-1 (v) scans O(n) vertices for possible inclusion in N k (v)
. This procedure is repeated O(n) times for increasing values of k. The time needed for this is O(n 3 ) for each vertex v; thus, O(n 4 ) in total.

The shortest length of a closed walk of type ij starting at v, denoted by g ij (G, v, σ), is now computed as follows. ij = 00: g 00 (G, v, σ) = 2 if N 1 (v) = ∅ and g 00 (G, v, σ) = ∞ otherwise. ij = 01: Consider the first k where one of the following happens: N + k (v) or N - k (v) induces a positive edge, or a negative edge connects a vertex from

N + k (v) to a vertex from N - k (v). Then g 01 (G, v, σ) = 2k + 1. ij = 10: Consider the first k where N + k (v) ∩ N - k (v) = ∅. Then g 10 (G, v, σ) = 2k. ij = 11:
Consider the first k where one of the following happens:

N + k (v) or N - k (v) induces a negative edge, or a positive edge connects a vertex from N + k (v) to a vertex from N - k (v). Then g 11 (G, v, σ) = 2k + 1.
This computation takes time O(n 3 ) because there are O(n) possible values of k and the set intersections and edge examinations take time O(n 2 ). Now the n vertices are examined to find

g ij (G, σ) = min v g ij (G, v, σ). This takes time O(n).
The longest step is the first, so the whole procedure takes time O(n 4 ).

The bound of O(n 4 ) is for simplicity of the proof; one can certainly do better. We conjecture that this can be done in time O(n 3 ).

Observe that if g 00 (G, σ) = ∞ then G has no edge and, therefore, g ij (G, σ) = ∞ for all other choices of ij. In the next lemma we show something similar but weaker for other choices of ij: that if G is connected and g ij (G, σ) = ∞, then at least for one other choice i j we have g i j (G, σ) = ∞. This will lead to the study of three special subclasses of signed graph, each of which is of special importance in the study of homomorphisms. These classes will be discussed in the next subsection.

Lemma 19. Let (G, σ) be a connected signed graph. If (G, σ) contains two closed walks W 1 and W 2 of types i 1 j 1 = 00 and i 2 j 2 = 00, respectively, with i 1 j 1 = i 2 j 2 , then it contains a closed walk W 3 of the third nonzero type.

Proof. Since G is connected, there is a (shortest) path P connecting a vertex u of W 1 to a vertex v of W 2 . Let W 3 = W 1 P W 2 P -1 , as a closed walk starting at u. Since P is traversed twice, it affects neither parity nor sign of W 3 . Therefore, W 3 is of type (i 1 + j 1 )(i 2 + j 2 ) (where addition is modulo 2). Since i 1 j 1 and i 2 j 2 are nonzero elements of Z 2 2 , their sum is the third nonzero element of this group.

We say that g ij (G, σ) is realized by a walk W if W has the type ij and has minimum length with that type. It appears that g ij (G, σ), if finite, may be realized by cycles and non-cyclic closed walks, or only by cycles, or only by closed walks that are not cycles. Appearances are misleading, as we see in the following result, where for simplicity we write g ij := g ij (G, σ) and m := max(g 01 , g 10 , g 11 ). We do not exclude the possibility that m = ∞. Proposition 20. Let G be a graph that is not bipartite, let σ be a signature on G. Suppose that, for some ij = 00, g ij < m or g ij = g i * j * = m < ∞ for some other i * j * = 00, ij. Then g ij is realized only by cycles.

In particular, if all three types of girth aside from g 00 are finite, then at least two of the three values g 10 , g 01 and g 11 are realized only by cycles of G.

Proof. A subwalk of a walk W is any nonempty consecutive sequence of edges in W . A closed walk that realizes some g ij cannot contain a closed subwalk of type 00, or it would not have minimal length. Now consider ij as assumed in the statement. Since g ij < ∞, there is a closed walk W that realizes g ij . If this walk is not a cycle, by minimality it contains a subwalk C that is a cycle of type i C j C = 00, ij. If we cut C out of W we are left with a closed walk W , shorter than W and of type ij + i C j C = i j = 00, ij, i C j C . Both C and W are shorter than W so g ij = m < ∞ and both g i C j C and g i j are less than m. We have shown that either all closed walks that realize g ij are cycles, or ∞ > g ij = m > g i C j C , g i j . This proves that any g ij < m can only be realized by cycles.

Suppose now that g ij = m < ∞. If g ij is realized by a closed walk W that is not a cycle, the preceding argument shows that m > g i C j C , g i j so both g i C j C and g i j are realized only by cycles. Therefore, if any two of g 01 , g 10 , g 11 equal m, then all three are realized only by cycles.

The last part of the proposition is now obvious.

As examples in Figure 1 show, for each choice of the ij, ij = 00, there exist a signed graph (G, σ) where the values g ij (G, σ), can only be realized only non-cyclic closed walks.

Special classes

Lemma 19 leads to the definition of three classes of signed graph which have proven to be of special importance in the homomorphism study of signed graphs. We refer to Section 6 for examples of important problems in these classes.

1. If g 11 (G, σ) = g 10 (G, σ) = ∞, then (G, σ) has no negative cycle, thus it is balanced.

By Lemma 1, after a suitable switching, all edges are positive, i.e., (G, σ) is switching equivalent to (G, +). This class of signed graphs will be denoted by G 01 .

2. If g 10 (G, σ) = g 01 (G, σ) = ∞, then (G, σ) is antibalanced. By Lemma 1, after a suitable switching, all edges are negative, i.e., (G, σ) is switching equivalent to (G, -). This class of signed graphs will be denoted by G 11 .

3. If g 11 (G, σ) = g 01 (G, σ) = ∞, then G has no cycle of odd length and, thus, (G, σ) is a signed bipartite graph. This class of signed graphs will be denoted by G 10 .

Thus G ij , ij ∈ { 01, 10, 11 }, is the class of signed graphs consisting of signed graphs in which every closed walk is either of type 00 or ij.

Given two signed graphs (G, σ) and (H, π) both in G 01 , to decide whether there is a homomorphism of (G, σ) to (H, π), first we switch each of the graphs so that all edges are positive; then, by Theorem 14, (G, σ) maps to (H, π) if and only if G maps to H. The same conclusion applies when both graphs are in the class G 11 . While therefore the homomorphism problem in each of these two classes is about homomorphisms of underlying graphs, as signed graphs the two classes behave differently in connection with graph minors.

A minor (more precisely, a link minor ) of a signed graph is a signed graph obtained by the following sequence of operations: 1. Delete vertices and edges. 2. Switch a set of vertices. 3. Contract a set of positive edges. (A link is a non-loop edge. This definition of contraction, which can be found in [START_REF] Zaslavsky | Is there a matroid theory of signed graph embedding?[END_REF], is a restriction of the definition of minors from [START_REF] Zaslavsky | Signed graphs[END_REF], which also allows contracting loops. For a positive loop, contraction is the same as deletion.)

In the class G 01 , the signed graphs without a (K 3 , +)-minor are the signed graphs with no cycle in the underlying graph (a forest in the usual sense), and thus all admit homomorphisms to (K 2 , +). Similarly those not containing (K 4 , +) are K 4 -minor-free graphs together with a signature where all cycles are positive. Thus all such signed graphs map to (K 3 , +).

On the other hand, in the class G 11 signed graphs without a (K 3 , -)-minor are the signed graphs with no odd cycle in the underlying graph. That is because (K 3 , -) can only be obtained as a minor from a negative cycle, which in the class G 11 is the same as an odd cycle. Thus in this case we have the class of bipartite graphs with signature such that all cycles are positive, and therefore, each admits a homomorphism to (K 2 , -). A restatement of a result of Catlin from [START_REF] Catlin | Ha jos graph-coloring conjecture: Variations and counterexamples[END_REF] (the proof of equivalence is left to the reader) is that a signed graph (G, σ) in G 11 which does not have a (K 4 , -)-minor maps to (K 3 , -).

Recalling that the homomorphism question in each of the classes G 01 and G 11 is (only) about the homomorphisms of the underlying graphs, we may restate previous claims as follows. Given a graph G, if (G, +) has no (K 3 , +)-minor (respectively, no (K 4 , +)minor), then G maps to K 2 (respectively, K 3 ). Similarly, if for a given graph G the signed graph (G, -) has no (K 3 , -)-minor (respectively, no (K 4 , -)-minor), then G maps to K 3 (respectively, K 4 ). While the conclusions of the two cases are the same, the class of graphs for which the first statement applies is strictly included in the class of graphs for which the latter one applies. More importantly, the class of graphs for which the first statement works is a sparse family of graphs whereas the class of graphs in the latter statement in particular contains all bipartite graphs, thus includes a dense family of graphs.

This observation has been one of the main motivations behind the development of this theory of homomorphisms of signed graphs. Some possible generalizations will be mentioned in Section 6.

Definitions of a chromatic number for signed graphs

One of the most classic notions of graph theory is the notion of proper coloring together with the associated parameter: chromatic number. Recall that proper coloring of a simple graph is a coloring of vertices where adjacent vertices receive different colors and the chromatic number is the minimum number of colors required in such a coloring. A natural extension of proper coloring of graphs to signed graphs, using signed colors, was first given in [START_REF] Zaslavsky | Signed graph coloring[END_REF] (see also [START_REF] Zaslavsky | Chromatic invariants of signed graphs[END_REF] and [START_REF] Zaslavsky | How colorful the signed graph? Discrete Math[END_REF]). Motivated by this notion of proper coloring, various other definitions of chromatic number of signed graphs have been recently introduced, whose difference depends on the choice of the set of signed colors; see e.g. [START_REF] Kang | Circular coloring of signed graphs[END_REF] for circular coloring and [START_REF] Fleiner | Coloring signed graphs using DFS[END_REF] for list coloring.

Here we present chromatic number as a natural optimization problem. To better express the idea, we begin with a reformulation of chromatic number of graphs which is better suited to the homomorphism viewpoint: the chromatic number of a simple graph G is the smallest order of a homomorphic image of G which is also simple (i.e., without loops). It is easy to verify that this definition gives the classic chromatic number. Observing the importance of the odd cycles in the value of the chromatic number, and that loops, which are odd cycles of length 1, are the crucial objects to be avoided in the target graph, we may refine the definition of chromatic number as follows. Given a triangle-free graph (or more generally one with odd girth 2k + 1) what is the smallest order of a triangle-free graph (or, respectively, a graph of odd girth 2k + 1) to which G admits a homomorphism? For example, as an extension of the Four-Color Theorem, and using that theorem itself, it has been shown that every triangle-free planar graph admits a triangle free image of order at most 16 and that 16 is the best possible (see [START_REF] Naserasr | Mapping planar graphs into projective cubes[END_REF] and references therein, also Section 6). This upper bound of 16 is reduced to 5 if we consider the subclass of planar graphs of odd girth at least 13 (see [START_REF] Zhu | Circular chromatic number of planar graphs of large odd girth[END_REF]). Considering our no-homomorphism lemma, Lemma 17, we generalize this idea to signed graphs as follows.

Definition 21. Given a triple L = (l 01 , l 10 , l 11 ) where l ij is either a positive integer or infinity, and given a signed graph (G, σ) satisfying g ij (G, σ) ≥ l ij , we define the Lchromatic number of (G, σ), denoted by χ L (G, σ), to be the minimum number of vertices of a signed graph (H, π) which satisfies g ij (H, π) ≥ l ij and (G, σ) → (H, π).

Furthermore, given a triple K = (k 01 , k 10 , k 11 ) satisfying k ij ≥ l ij , we define the (K, L)chromatic number of a class S of signed graphs to be the maximum of the L-chromatic numbers of signed graphs (G, σ) in S satisfying g ij (G, σ) ≥ k ij , and ∞ when there is no such maximum.

With this terminology, if we take L = (∞, ∞, l), then any signed graph (G, σ) satisfying g ij (G, σ) ≥ l ij is a signed graph in G 11 , i.e., an antibalanced signed graph, and thus it can be switched to (G, -) (all edges negative). As mentioned in the previous section, in this class of signed graphs the question of whether (G, σ) maps to (H, π) is reduced to the question of whether the graph G maps to H. Similarly for L = (l, ∞, ∞) a signed graph satisfying g ij (G, σ) ≥ l ij is a signed graph in G 01 , i.e., a balanced signed graph, which switches to (G, +), so homomorphism questions on these signed graphs are identical to homomorphism questions on graphs.

Let P be the class of signed planar graphs. With our terminology, it is a restatement of the Four-Color Theorem to say that for K = L = (∞, ∞, 3) and for K = L = (3, ∞, ∞) the (K, L)-chromatic number of P is 4. For K = (∞, ∞, 5) and L = (∞, ∞, 3) it is a restatement of the Grötzsch theorem to say that the (K, L)-chromatic number of P is 3. The result of [START_REF] Naserasr | Mapping planar graphs into projective cubes[END_REF] can be also restated as: for K = L = (∞, ∞, 5) the (K, L)-chromatic number of P is 16. In general, determining the (K, L)-chromatic number of planar graphs is a question of high interest. Special cases will be mentioned in Section 6.

The notion of proper coloring of signed graphs as defined in [START_REF] Zaslavsky | Signed graph coloring[END_REF] corresponds to the (K, L)-chromatic number for K = L = (3, 2, 1). That is to say, given a signed graph where digons and negative loops are allowed but positive loops are not, we want to find a smallest homomorphic image without a positive loop. For more detail we refer to Section 2.4 of [START_REF] Brewster | The complexity of signed graph and edge-coloured graph homomorphisms[END_REF].

Connections to 2-Edge-Colored Graphs

A homomorphism of a 2-edge-colored graph G = (V (G), E 1 (G), E 2 (G)) to a 2-edge- colored graph H = (V (H), E 1 (H), E 2 (H)
) is a homomorphism of the underlying graph G to the underlying graph H which preserves colors of the edges.

Homomorphisms of signed graphs can be viewed as a special case of homomorphisms of 2-edge-colored graphs in a few ways; we discuss three such possibilities here.

Signs as colors

The easiest connection is by way of Theorem 14. A signed graph (G, σ) is a 2-edgecolored graph with the colors + and -. Then an edge-sign-preserving homomorphism of signed graphs is identical to a homomorphism of 2-edge-colored graphs. Thus by Theorem 14, there is a (switching) homomorphism of (G, σ) to (H, π) if and only if there are a switching σ of σ and a 2-edge-colored graph homomorphism (G, σ ) → (H, π).

Double switching graph

The second connection is based on a construction first presented by R. C. Brewster and T. Graves in [START_REF] Brewster | Edge-switching homomorphisms of edge-coloured graphs[END_REF]. In fact, in that paper Brewster and Graves introduced and studied (independently of other writers) the notion of homomorphisms of signed graphs as "edgeswitching [i.e., switching] homomorphisms of edge-colored graphs". Definition 22. Let (G, σ) be a signed graph. We define the double switching graph DSG(G, σ) to be a signed graph with two vertex sets, V + and V -, each a copy of V (G), with edges u α v β (α, β = ±) for each edge uv, and signs σ(u α v β ) = αβσ(uv). We normally treat DSG(G, σ) as a 2-edge-colored graph.

Observe that (G, σ) is an induced subgraph of DSG(G, σ). It is induced by V + and also by V -. To switch a vertex x of signed graph (G, σ), when viewed as a subgraph induced by V + , is to replace x + by x -. Thus DSG(G, σ) can be partitioned into two copies of (G, σ ) for any switching σ of σ. For this reason one may refer to DSG(G, σ) as the double switching graph of (G, σ).

Brewster and Graves used this construction to connect homomorphisms of signed graphs to homomorphisms of 2-edge-colored graphs. We restate here two main connections:

Theorem 23. Given signed graphs (G, σ) and (H, π), there exists a switching homomorphism of (G, σ) to (H, π) if and only if there exists a color-preserving homomorphism of the 2-edge-colored graph (G, σ) (equivalently, of DSG(G, σ)) to the 2-edge-colored graph DSG(H, π).

Theorem 24. A signed graph (G, σ) is a core if and only if DSG(G, σ) is a core as a 2-edge-colored graph.

It is noteworthy that if (G, σ) is in G ij for i, j ∈ {0, 1}, then so is DSG(G, σ) when viewed as a signed graph.

Extended double cover

We now introduce a new construction which provides a different setting to capture homomorphisms of signed graphs as a special case of homomorphisms of 2-edge-colored graphs.

Definition 25. Let (G, σ) be a signed graph. We define EDC(G, σ) to be a signed graph on vertex set V + ∪ V -, where V + := {v + : v ∈ V (G)} and V -:= {v -: v ∈ V (G)}. Vertices x + and x -are connected by a negative edge; all other edges, to be described next, are positive. If vertices u and v are adjacent in (G, σ) by a positive edge, then v + u + and v -u -are two positive edges of EDC(G, σ), if vertices u and v are adjacent in (G, σ) by a negative edge, then v + u -and v -u + are two positive edges of EDC(G, σ).

Since EDC(G, σ) consists of the double covering graph of (G, σ), as defined in [START_REF] Zaslavsky | Signed graphs[END_REF], with positive edge signs and added negative edges x + x -, we call it the extended double cover of (G, σ). Let (G, σ) • denote (G, σ) with a negative loop attached to each vertex. There is a natural projection p G : EDC(G, σ) → (G, σ) • induced by mapping x + , x -→ x for each x ∈ V (G). The negative edges map to the negative loops. A positive edge u α v β maps to the edge uv with sign αβ. A fiber of p is any set p -1 G (u) = {u + , u -} (for a vertex) or p -1 G (uv) = {u + v σ(uv) , u -v -σ(uv) } (for an edge), which for a negative loop means p -1 G (uu) = {u + u -}.

To be of interest for homomorphisms we first show that EDC(G, σ) is independent of switching. We define a fibered automorphism of EDC(G, σ) to be an automorphism that preserves fibers; that is, it carries an element of a fiber to itself or to the other element of the same fiber. More generally, we define a fibered homomorphism ψ : EDC(G, σ) → EDC(H, π) to be a graph homomorphism that respects fibers; that is, if x ∈ V (G), then {ψ(x + ), ψ(x -)} = {y + , y -} for some y ∈ V (H). This definition implies that ψ(x + x -) = y + y -and that ψ carries an edge fiber p -1 G (uv) to p H (yz) for some edge yz ∈ E(H). Lemma 26. Let (G, σ) and (H, π) be signed graphs. Suppose ψ is a graph homomorphism EDC(G, σ) → EDC(H, π). Then ψ is a 2-edge-colored homomorphism (i.e., it preserves edge signs) if and only if it is a fibered homomorphism.

Proof. The proof follows from the fact that the only negative edges are of the form x + x - and such an edge exists for every vertex x in both graphs. Proposition 27. Let (G, σ) be a signed graph and let σ be a switching of σ. Then EDC(G, σ) is isomorphic to EDC(G, σ ) as a 2-edge-colored graph. The isomorphism is a fibered isomorphism.

Proof. Let X be a set of vertices that are switched in order to get σ from σ. An isomorphism of EDC(G, σ) to EDC(G, σ ) then consists of interchanging the roles of v + and v - for every vertex v ∈ X. This is a fibered isomorphism.

Theorem 28. There is a homomorphism of a signed graph (G, σ) to a signed graph (H, π) if and only if there is a color-preserving homomorphism of EDC(G, σ) to EDC(H, π).

Proof. Suppose (G, σ) maps to (H, π) as a signed graph. The by Theorem 14 there are a switching σ of σ and a mapping φ of (G, σ ) to (H, π) which preserves the signs as well. By Proposition 27 switching σ will give an isomorphic copy of EDC(G, σ) (as a 2-edge-colored graph), thus, without loss of generality, σ = σ.

We need to present a homomorphism from EDC(G, σ) to EDC(H, π) which preserves edge signs (i.e., colors). We show that the most natural extension of φ works. More precisely, let ψ(x ) = φ(x) for each vertex x of G and for = +, -(this gives the mapping of vertices); for the edges we define ψ(x y δ ) = φ(x) φ(y) δ for every edge x y δ of EDC(G, σ), where , δ = +, -(this gives the mapping of edges). This is a homomorphism because φ never maps two adjacent vertices of G to a single vertex of H. Also, ψ is clearly sign-preserving.

For the other direction, suppose ψ is a homomorphism from EDC(G, σ) to EDC(H, π) preserving signs. Thus each pair x + x -must map to a pair of the form z + z -as these are the only negative edges (i.e., ψ is a fibered homomorphism). To complete the proof we should introduce a switching σ of σ under which we may find a homomorphism preserving edge signs. To this end it is enough to decide for each vertex x whether we switch x. As x + x -is mapped to a pair z + z -, either we have ψ(x + ) = z + and ψ(x -) = z -or we have ψ(x + ) = z -and ψ(x -) = z + . In the former case we do not switch x, in the latter case we do switch x. Let σ be the signature obtained after such switching. Observe that by the definition of σ , after composing the mapping ψ with the isomorphism which changes EDC(G, σ ) to EDC(G, σ) (by Proposition 27) we have a homomorphism ψ of EDC(G, σ ) to EDC(H, π) which preserves vertex signs, i.e., φ (x ) = z for some z ∈ V (H).

We now define φ as a sign preserving homomorphism from (G, σ ) to (H, π) as follows: for the vertex mapping, if ψ(x + x -) = z + z -then define φ(x) = z; for the edge mapping, let p G ψ(xy) = {x + y , x -y } in EDC(G, σ ). Thus σ (xy) = and since ψ preserves vertex signs it is straightforward to show that π(φ(xy)) = = σ (xy), as we wished.

It worth noting the effect of the extended double cover construction on the three special classes of signed graphs. If (G, σ) is balanced (that is to say (G, σ) is in the class G 01 ), then one may switch σ to σ so that all edges are positive. Thus EDC(G, σ ) consists of two vertex-disjoint copies of G with a negative edge between each pair of corresponding vertices; we observe that EDC(G, σ ) itself is a balanced signed graph and so is EDC(G, σ) (by Proposition 27). If (G, σ) is antibalanced, then EDC(G, σ) is a signed bipartite graph, and vice versa, if (G, σ) is a signed bipartite graph, then EDC(G, σ) is antibalanced. We prove this and more in the next proposition.

Theorem 29. Let (G, σ) be a signed graph.

(1) (G, σ) is antibalanced if and only if EDC(G, σ) is a signed bipartite graph.

(2) (G, σ) is a signed bipartite graph if and only if EDC(G, σ) is antibalanced.

Proof. (1) If (G, σ) ∈ G 11 , then it can be switched to (G, -) such that all edges are negative. It is then immediate that EDC(G, -) is a signed bipartite graph, and it is isomorphic to EDC(G, σ).

Conversely, suppose EDC(G, σ) is a signed bipartite graph. Each two vertices x + , x - must be in opposite sets of the bipartition, so by switching to, say, (G, σ ) we can ensure that the two sets are V + and V -. Then every edge in EDC(G, σ) has the form x y -, so every edge of (G, σ ) is negative. It follows that (G, σ) is antibalanced.

(2) We now consider a signed bipartite graph (G, σ). Let A, B be the partition of vertices of G into two independent sets. By switching A + ∪ A -we make all edges of EDC(G, σ) negative. Thus, EDC(G, σ) is antibalanced.

For the converse, suppose EDC(G, σ) is antibalanced. That means we can make it all negative by switching a set X ⊆ V + ∪ V -. Since x + x -is already negative, x + and x -are either both in X or both not in X. For two adjacent vertices x, y ∈ V (G), exactly one of x + and y + is in X. Let A := p G (X) and B := V (G) \ A; this gives a bipartition of V (G) such that no edge of G has both endpoints in A or both in B. Thus, G is bipartite.

The extended double cover can be used to give a nice inductive definition of signed projective cubes. These graphs and problems about homomorphism to them are what motivated the definition of a homomorphism of signed graphs in the first place (see [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF]). We write more in Section 6 on the importance of these graphs and a connection to the Four-Color Theorem. Definition 30. A signed projective cube of dimension 1, denoted by SPC [START_REF] Brewster | The complexity of signed graph and edge-coloured graph homomorphisms[END_REF], is a signed graph on two vertices connected by one negative edge and one positive edge. A signed projective cube of dimension k, k ≥ 2, denoted by SPC(k), is defined to be EDC(SPC(k -1)).

Proposition 31. For k ≥ 1, SPC(k) is isomorphic as a 2-edge-colored graph to the signed graph whose vertices are the elements of Z k 2 and in which two vertices x and y are adjacent by a positive edge if they differ in exactly one coordinate and are adjacent by a negative edge if they differ in all coordinates.

That is, SPC(k) is isomorphic as a 2-edge-colored graph to the signed graph that consists of a k-dimensional cube graph Q k on vertex set {0, 1} k with all edges positive and with additional negative diagonals xx, where x := (1, 1, . . . , 1) -x.

Proof. The proposition is obviously true for k = 1. We assume it for k and show how the construction of SPC(k + 1) in Definition 30 produces the graph in the proposition.

By definition, the vertex set of EDC(SPC(k + 1)) is {(x, 0), (x, 1) : x ∈ {0, 1} k } and the edges are the positive edges (x, 0)(y, 0) and (x, 1)(y, 1) whenever xy ∈ E + (SPC(k)), (x, 0)(ȳ, 1) and (x, 1)(ȳ, 0) whenever xy ∈ E -(SPC(k)) (which means that y = x), and the negative edges (x, 0)(x, 1) for all x ∈ {0, 1} k . Now relabel every vertex (x, 1) by the new name (x, 1). With the new labeling, the signed edge set is identical to that of the definition of SPC(k + 1) in the proposition. This leads to the following packing problem: Problem 35. Given a signed graph (G, σ) what is the maximum number of signatures σ 1 , σ 2 , . . . , σ l such that i. each σ i is switching equivalent to σ, and ii. the sets E -(σ i ) are pairwise disjoint?

A starting point for this question then is to ask whether, given a signed graph (G, σ), there is a switching (G, σ ) that has no negative edge in common with (G, σ). Using our results from Section 3 we may provide an easy test for this case of the question. We consider that the empty graph, with no vertices or edges, is bipartite.

Theorem 36. Given a signed graph (G, σ), there exists a switching (G, σ ) such that the two signed graphs have no negative edge in common if and only if the set of negative edges of (G, σ) induces a bipartite graph.

Proof. Let G -be the subgraph induced by the set of negative edges of (G, σ). Note that G -is bipartite if and only if its edge set is a subset of a cut [X, Y ] with Y := V (G) \ X.

For sufficiency assume that G -is bipartite. Switching X, the negative edge set becomes [X, Y ] \ E -, which is disjoint from E -and induces a bipartite subgraph.

Conversely, if (G, σ) and (G, σ ) are switching equivalent with no common negative edge, then the cut [X, Y ] which we switch to get one from the other contains all negative edges of both; thus, both sets of negative edges together induce a bipartite graph.

(This short proof was contributed by Nicholas Lacasse.)

We note that the bipartition {X, Y } may not be unique, so the switched signed graph may not be unique, but each such resulting signed graph has negative edge set that is disjoint from E -. Indeed, every (G, σ ) whose negative edge set is disjoint from E -is obtained in this way.

Alternate Proofs.

Here is a different approach to necessity. If G -is not bipartite, then it contains an odd cycle C. Since all edges of C are negative and it has odd length, it is a negative cycle; thus any signature which is switching equivalent to σ must have an odd number of edges of C; in particular at least one negative edge must belong to C, thus to G -.

Here is an entirely different proof of sufficiency using a contraction technique that has other applications. As in the short proof above, we assume G -is bipartite. Thus each negative cycle, and, therefore, each negative closed walk, has at least one positive edge. Let W be the set of negative closed walks of G. By Theorem 10, W satisfies the exclusive 3-walk property. Let Ḡ be the minor of G obtained by contracting all negative edges of (G, σ) (without deletion of parallel edges or loops), and let W be the set of closed walks in Ḡ obtained from walks in W. As each walk in W has at least one positive edge, none of the closed walks in W is a trivial walk. It is then straightforward to check that W has inherited the exclusive 3-walk property, and therefore, by Theorem 10, W is the set of negative closed walks ( Ḡ, η) for some signature η of Ḡ. As each edge of Ḡ corresponds to an edge of G, we may lift η to a signature σ of G which assigns negative sign to exactly those edges to which η has assigned a negative sign. As such, the set of negative closed walks of (G, σ ) is the same as that of (G, σ). But since all negative edges of σ were contracted to get Ḡ, the two signed graphs on G have no negative edge in common.

We would like to point out the importance of this theorem in approaching Conjecture 33. To this end we first restate the conjecture in the following uniform form: Conjecture 37. A planar signed graph (G, σ) maps to SPC(k) if and only if the four girth conditions of Lemma 17, the no-homomorphism lemma, are satisfied.

The two conjectures are equivalent because if for (G, σ) we have g ij (G, σ) ≥ g ij (SPC(2k)), then since g 01 (SPC(2k)) = g 10 (SPC(2k)) = ∞, (G, σ) must be an antibalanced graph; and similarly (G, σ) must be a signed bipartite graph in order to satisfy g ij (G, σ) ≥ g ij (SPC(2k -1)).

While the case k = 1 of the conjecture is rather trivial, the case k = 2 of the conjecture is equivalent to the four-color theorem. It is verified for k ≤ 7 through an equivalent reformulation and by means of induction on k (we refer to [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF] for details). In attempt to apply induction (based on k) directly on this statement, what one would need is to find a signature σ equivalent to σ, such that the signed graph ( G, η) obtained by switching as in the alternate proof of Theorem 36 satisfies the four conditions of the no-homomorphism lemma for mapping to SPC(k -1).

One may also consider a more general form of the question.

Problem 38. Given signed graphs (G, σ) and (G, η), are there switchings (G, σ ) and (G, η ) such that the two signatures have no negative edge in common?

Problem 35 is the planar dual of the packing problem for T -joins. Consider a signed plane graph (G, σ) and the consequent signs of dual vertices (i.e., faces of G). The dual edges have the same signs as in the original signed graph. Let T be the set of negative dual vertices. The negative edges of the dual graph G * have the property that they have even degree at every positive vertex of G * and odd degree at every negative vertex. This is the definition of a T -join. Switching (G, σ) to (G, σ ) does not change T , but it does change the negative edge set. Thus, E -(G, σ) and E -(G, σ ) are disjoint if and only if the corresponding T -joins are disjoint. Thus, packing the most negative edge sets as in Problem 35 is the planar dual of packing the most T -joins in a graph with a fixed set T of evenly many vertices.

Finally, we would like to mention a possible extension of Conjecture 37 in relation to minors theory.

Conjecture 39. A signed graph (G, σ) without a (K 5 , -)-minor maps to SPC(k) if and only if the four girth conditions of Lemma 17, the no-homomorphism lemma, are satisfied.

Future work

One may observe that the four no-homomorphism conditions of Lemma 17 are on the four possible types of cycle based on the parity of the length and the sign. Parity itself is the sign of the cycle when all edges are negative. This leads to the idea of assigning an array of signatures to a given graph. A homomorphism among such structures then is a mapping of basic elements that preserves the signs of closed walks in all signatures. We hope to address this generalization and its properties in future work.

The algorithm of Proposition 18 is designed only to show that g ij (G, σ) can be computed in polynomial time. It would of interest to design more efficient algorithms. We believe the computation should be possible in time O(n 3 ).

As an extension of the four-color problem, Hadwiger proposed that every simple graph with no K n -minor admits a proper (n -1)-coloring. That is, any balanced signed graph without a loop and with no (K n , +)-minor admits a homomorphism to the balanced complete graph on n-1 vertices. This is widely believed to be one of the most challenging problems in graph theory. B. Gerards and P. Seymour independently then introduced a strengthening of the conjecture which can be well stated using the terminology of signed graphs:

Conjecture 40 (Odd-Hadwiger). If (G, -) is an antibalanced signed graph with no loop that has no (K n , -)-minor, then (G, -) → (K n-1 , -).

This important conjecture remains wide open. B. Guenin in 2005 claimed a proof for n = 4 (assuming the four-color theorem), but to now there has been no publication.

Acknowledgement

Figure 1 :

 1 Figure 1: Signed graphs where g 10 , g 11 , g 01 are realized by a closed walk but not a cycle.

Switching is called resigning in some works on signed graphs.

Acknowledgement. This work is supported by the French ANR project HOSIGRA (ANR-17-CE40-0022). The work is descendant of an earlier work with Clément Charpentier and has benefited from discussions with him.

Corollary 32. The signed projective cube SPC(k) is antibalanced if and only if k is even and is a signed bipartite graph if and only if k is odd.

Proof. This follows by induction from Theorem 29 applied to the definition of SPC(k).

Further Discussion and Future Work

We expect to extend many properties of homomorphisms and coloring of graphs to signed graphs. The special interest here will be a stronger connection with graph minors. However, many interesting ideas seem to arise independently. Here we mention only some of the most challenging problems of the subject.

Signed projective cubes and packing of negative edge sets

The problem that motivated the introduction of homomorphisms of signed graphs (by B. Guenin) is the following conjecture in extension of the Four-Color Theorem, proposed in [START_REF] Naserasr | Homomorphisms and edge-colorings of planar graphs[END_REF] and [START_REF] Guenin | Packing odd circuit covers: A conjecture[END_REF]:

Conjecture 33. We propose:

Combined with a result of [START_REF] Naserasr | Walk-powers and homomorphism bounds of planar signed graphs[END_REF] and terminology introduced here the conjecture amounts to claiming that i. for K = L = (∞, ∞, 2k + 1) the (K, L)-chromatic number of planar graphs is 2 2k , ii. for K = L = (∞, 2k, ∞, ) the (K, L)-chromatic number of planar graphs is 2 2k-1 .

It is then natural to ask more generally for the (K, L) chromatic number of planar graphs, for each value of K and L. For K = (3, 4, 3), and L = (3, 2, 1) it was proposed by Máčajová, Raspaud and Škoviera [START_REF] Máčajová | The chromatic number of a signed graph[END_REF] that the (K, L)-chromatic number of the class of planar signed graphs is 2. This conjecture has recently been disproved in [START_REF] Kardǒs | On the Four-Color Theorem for signed graphs[END_REF]. For K = L = (3, 4, 3), the question is about finding a smallest simple signed graph admitting a homomorphism from every simple planar signed graph; the best known bounds so far are a lower bound of 10 given in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] and an upper bound of 40 given in [START_REF] Ochem | Homomorphisms of 2-edge-colored triangle-free planar graphs[END_REF]. T

The question captures some other well-known results or conjectures in the theory of coloring planar graphs, such as the Grötzsch theorem and the Jaeger-Zhang conjecture.

Conjecture 33 is related to several other conjectures, a notable one being a conjecture of P. Seymour on the edge-chromatic number of planar multigraphs. The connection with homomorphisms to projective cubes and edge-partitioning problems is stated in the following theorem, we refer to [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF] for a proof and further details on connections to Seymour's edge-coloring conjecture.

Theorem 34 ( [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF]). A signed graph (G, σ) maps to SPC(k) if and only if E(G) can be partitioned into k + 1 sets E i such that each E i is the set of negative edges of a signature that is switching equivalent to σ.


J Vicente

F Da Silva

S Heuraux

G D Conway

C Silva

T Ribeiro

Turbulence level effects on conventional reflectometry using 2D full-wave simulations

Numerical simulations are critical in improving the capabilities of microwave diagnostics. In this work, the 2D finite-difference time-domain full-wave code REFMUL was applied to broadband turbulent plasmas using the conventional reflectometry setup. Simulations were performed with O-mode waves, fixed frequency probing, and I/Q detection. The plasma density, determining O-mode propagation, was modeled as the sum of a slab background plasma with a fluctuating component following a Kolmogorov-like amplitude k-spectrum. The density turbulence level δn e /n e was scanned over several orders of magnitude for simulated plasma flows of constant plasma velocity in either the radial or the poloidal direction. Simulations show trends, such as spectral broadening of the complex A(t)e iϕ(t) signals and increasing fluctuations in A(t) and ϕ(t) with increasing δn e /n e , that are similar for both plasma flow directions. These together with possibilities to reconstruct a poloidal wavenumber spectrum are discussed in view of extending the measuring capabilities. The onset of non-linear effects associated with phase runaway, as previously observed with other 1D and 2D codes, as well as radial Doppler effects is also observed and discussed.

I. INTRODUCTION

Full-wave simulations have been instrumental in understanding reflectometry measurements and plasma-wave interactions, such as Bragg backscattering or forward scattering. 1 In this work, the response of ordinary wave polarization (Omode) reflectometry to analytically prescribed turbulent plasmas in simplified slab geometry is studied by performing 2D simulations in a conventional setup (i.e., perpendicular incidence) for both cases of poloidal and radial plasma flows. Fixed frequency probing is employed, and the reflectometry complex amplitude A(t)e iϕ (t) , phase ϕ(t), and amplitude A(t) signals are characterized while scanning the plasma turbulence level.

II. BRAGG BACKSCATTERING

The most efficient scattering process of the probing wave is caused by density fluctuations that meet the Bragg resonant rule. [2][3][4] For conventional reflectometry, Bragg backscattering can occur when the local radial wavenumber of the injected wave k(r) is resonant with the radial wavenumber of a given Fourier component of the density fluctuations, k rad = 2k(r). The Bragg relation holds up to the limit wavenumber k rad = 2k o set by the vacuum wavenumber of the probing wave k o , near the plasma entrance. Moreover, only a) Author to whom correspondence should be addressed: jvicente@ipfn.

tecnico.ulisboa.pt fluctuations with k rad > 2k A can satisfy the Bragg condition, where k A is the Airy wavenumber, k A = 0.63(k o 2 L n -1 ) 1/3 with L n being the density gradient scale length. While the poloidal characteristics of turbulence should not be responsible for any backscattering, in 2D it is impossible to neglect the radiation pattern of the emitter which contains poloidal wavenumbers and could thus resonate with poloidal fluctuations. In the case of O-mode probing and small coherent perturbations in a linear radial profile, a linear relation between the phase perturbations of the reflectometer signal δϕ and the density perturbation amplitude δn has been shown, 5,6

δφ = √ πk o L n k f δn n c , (1)
where n c is the cutoff density and k f is a given wavenumber component of the density fluctuation spectrum. However, additional non-linear contributions to phase variations may occur due to higher orders of Bragg backscattering. 7

III. TURBULENCE MODEL

For O-mode propagation, the plasma cutoff for a given probing wavenumber k o depends only on the plasma electron density n e . Thus, a numerical plasma is sufficiently modeled by the definition of the electron density. In this work, the total density n e (r, t) = n eo (r, t) + δn e (r, t) accounts for a linear radial electron density profile n eo (r, t) and a broadband density turbulence term δn e (r, t). While the background profile is simply set through a given density gradient, the turbulence is defined by a sum of modes with random phase, 8,9

δn e = i M i=i m j M j=j m A(i, j) cos k x (i)x + k y (j)y + φ(i, j) .
(2)

The coefficients A(i, j) allow establishing a Kolmogorov-like amplitude k-spectrum, which is in line with several experimental observations in the edge fusion plasmas, 10 while ϕ(i, j) is a random generated phase that sets a particular turbulence snapshot with the target spectral conditions. The 2D k-spectrum is defined by constant amplitude at low k and up to a chosen wavenumber k knee followed by a power law decay k -α along both the xand y-directions, corresponding to the radial and poloidal directions in a tokamak. The wavenumber knee is set to k knee = 400 rad/m or k knee = 4 cm -1 in usual (perhaps misleading) notation. The amplitude rolls off dropping to 1% of the flat top value at k = 15 cm -1 , along with a spectral index α = 3. A realization of the turbulence model is shown in Fig. 1.

The root mean square value δn e,RMS of the density fluctuations generated with the above model can be easily modified and sets the turbulence level at the radial position r c of the cutoff density in the slab linear profile, δn e n e ≡ δn e,RMS n e (r c ) × 100%.

(

) 3
The total density, obtained by adding the linear profile and the turbulent density terms, results in a radial variation of the local turbulence level, which increases toward the periphery of the plasma as the background density decreases (see Fig. 2). This radial trend is also in general agreement with the experimental observations at the edge and scrape-off layer regions of tokamaks. 11 In this work, two different electron density gradient lengths L n have been used for background profiles, corresponding to shallow (long L n ≈ 0.16 m) and steep (short L n ≈ 0.05 m) density profiles, for which the minimum Bragg wavenumbers (2k A ) are 1.8 cm -1 and 2.6 cm -1 , respectively. Once a total density matrix was generated, simulations were carried out imposing a bulk plasma movement in either the poloidal or radial direction. In both cases, the Taylor "frozen turbulence" hypothesis 12 is assumed, which considers that advection contribution by turbulent eddies is small and that therefore the advection past a fixed point can be taken to be entirely due to the mean flow. This hypothesis actually holds if the eddy mutation rate is much smaller than the mean plasma velocity.

IV. SIMULATION SETUP

The full-wave code REFMUL used in this work solves the Maxwell equations for O-mode. 13 Both electric and magnetic fields are coupled to the plasma electron density n e (r, t) which is used as a fusion plasma model, as mentioned in Sec. III. Simulations were designed with a monostatic setup, i.e., one antenna for both emission and reception. A unidirectional transparent source was used for injection of the signal allowing separation of the emitted probing wave from any returning waves. For directivity, a monostatic 2D H-plane horn antenna with a half-power beam width ≤ 6.5 cm at the plasma entry was employed. Probing waves with two different frequencies f p = 33 GHz and f p = 49 GHz, corresponding to cutoff densities of n c33 = 1.35 × 10 19 m -3 and n c49 = 2.99 × 10 19 m -3 , respectively, were used in separate runs. The two slab plasma profiles with the radial cutoff locations of the two probing frequencies that were used are shown in Fig. 2. Also shown are the several turbulence level profiles that were employed in both radial and poloidal plasma flow simulations.

The synthetic reflectometry phase ϕ(t) and amplitude A(t) signals were obtained by performing identical simulation runs with sin and cos excitation signals allowing in-phase

I(t) = A(t)cos(ϕ(t)) and quadrature Q(t) = A(t)sin(ϕ(t)) detec- tion. These signals combined provide directly A(t) = [I(t) 2 + Q(t) 2 ] 1/2 and ϕ(t) = a tan[Q(t)/I(t)].
The simulation box comprised a rectangular grid while the plasma itself was quadrangular with side length L = 1859 grid points since a radial block of the simulation box was used for the antenna setup and a vacuum distance (d vac = 15.5 cm) to the plasma. The spatial grid resolution was ∆x = ∆y = λ 40GHz /20 = 3.75 × 10 -4 m, where λ 40GHz is the vacuum wavelength of an f = 40 GHz wave frequency. The required time resolution of the simulations (∆t = 6.25 × 10 -13 s) impose that the duration of any simulated phenomena must be scaled down and any velocities involved scaled up. A rescaling is done such that v siml = R t v real , where v real is the characteristic velocity of a given plasma feature and v siml is the velocity in the simulation. To avoid relativistic effects, the scaled-up velocities v siml are restricted to values of v siml < 0.1c, where c is the speed of light. In this work, simulations of plasma propagation in both radial and poloidal directions have been performed with 28 × 10 4 time iterations, corresponding to v siml = 0.013c.

V. SIMULATION RESULTS

A. Poloidal plasma flow

Independent simulations were performed for each turbulence level, in a range of 0.02%-20%. The power spectra of the reflectometry complex amplitude signal A(t)e iϕ(t) for the unperturbed profile case and a set of turbulence levels are shown in Fig. 3, for each density gradient length and probing frequency that were studied.

In general, spectral broadening is observed with increasing turbulence level. The usual increase in central peak amplitudes and integrated spectral powers (see also Fig. 4) with increasing turbulence level is also observed. Similar results were obtained previously with simple physical optics model. 8 It is known that fluctuations moving in the poloidal direction, acting as a phase grating, may result in frequency shifted sidebands at the receiver antenna. 14 The amplitudes of those sidebands are expected to be equal in conventional reflectometry, at least for geometrically symmetric perturbations and low propagation velocities. On the other hand, the poloidal propagation of density structures results in radial displacements of the cutoff layer as the 2D structures project different radial profiles in a perpendicular line of sight. Thus, any radial movements of the reflecting layer should lead to a phase modulation of the reflected signal, resulting in a symmetric broadening of the central line in the frequency spectrum. After rescaling the frequency axis, according to the ratio of velocities, assuming v real = 5 km/s and taking into account that the frequency of the density fluctuations is related to the poloidal (or equivalently in this case, perpendicular) wavenumber v pol k pol = 2πf, the wavenumber spectra can be reconstructed. This is shown in Fig. 4 for one probing frequency and a comprehensive set of turbulence levels.

The spectral shape of the input Kolmogorov-like amplitude k-spectrum (shown as a dashed line) is fairly well recovered. The flat amplitude region at low-k followed by a strong roll-off region is observed. The values from the original model k knee = 4 cm -1 and k = 15 cm -1 (1% of the flat top value) are also shown in Fig. 4 by vertical dashed lines. Applying an identical spectral analysis and re-scaling procedure to ϕ(t) and A(t) followed by linear fitting the data in the roll-off region (4 cm -1 < k ⊥ < 15 cm -1 ) allows obtaining estimates of the spectral index which are shown in Fig. 5.

At low turbulence levels, the spectral index is mostly under-estimated. However, for δn e /n e > 2%-4%, the phase spectra do allow to recover the spectral index value (-3) of the 2D model, suggesting that the sensitivity to high k fluctuations may increase at higher turbulence levels or that simply 2D effects farther from the cutoff become increasingly more important. On the other hand, the evolution of the integrated spectral power of the A(t)e iϕ(t) signals with the turbulence level, displayed in Fig. 6, shows a linear relation between these two quantities only up to δn e /n e ≈ 2%-4% followed by non-linear behavior at higher turbulence levels.

A similar relation is also observed between the phase fluctuations and the turbulence level, as shown in Fig. 7 Starting at moderate turbulence levels, the phase time traces (not shown here) display phase drifting and phase runaway effects that become ubiquitous at higher turbulence levels. The evolution of the average and fluctuating components of the reflectometry amplitude A(t) is shown in Fig. 8. The average amplitude of the reflected signal decreases with increasing turbulence level and is lower, at each turbulence level, in the case of higher L n . These results must be interpreted in the light of 2D effects since 1D backscattering efficiency is proportional to √ L n ; however, the beam spreading associated to a longer path into the turbulent plasma should provide a competing geometrical effect. 15 A rebound in the average amplitude is also observed at the highest turbulence levels. This could be explained by a transition to a secondary cutoff from the slab plasma to a high amplitude density front. While the low turbulence range of linear reflectometry phase response has been previously predicted with 1D analytical reasoning, 16 2D physical optics, 17,18 and full-wave models, 18 these results suggest a possible extension to measuring capabilities, for instance, through proper modeling of the amplitude signals.

B. Radial plasma flow

The numerical plasmas employed in Sec. V A were also used in simulations with radial plasma flow in both the inward (V r > 0) and outward (V r < 0) directions. The double-sided Fourier spectra of the complex amplitude signals obtained with the f p = 33 GHz cases are shown in Fig. 9.

The effect of spectral broadening with increasing turbulence levels is observed again. This is more pronounced than in the poloidal flow cases, shown previously in Fig. 3. The spectra become increasingly asymmetric with increasing 9 by dashed vertical lines. In cases of short L n , the observed Doppler shift is in agreement with the reflecting layer movement. For long L n , the Doppler shifts are larger due to the increased plasma path and Bragg contributions. This is additionally leading to phase runaway, as seen in Fig. 10, where the phase also changes sign with opposite propagation directions.

Despite this, phase fluctuations behave similarly for the inward and outward directions at low turbulence levels, becoming somewhat distinct at high δn e /n e possibly due to trapped waves responding differently when being pushed out or into the probing wave. For low δn e /n e values, phase fluctuations scale linearly as predicted by Eq. ( 1) and shown in Fig. 11 where an average (effective) k f = 3 cm -1 was assumed to calculate the theoretical Bragg Backscattering values for two of the outward propagation cases.

Standard deviation values σϕ(t) largely exceeding 2π are perhaps a good proxy for the phase drift slope rather than the phase fluctuations. Nevertheless, this quantity seems to be useful in tracking (quasi-linearly) the turbulence level. The reduction in the average amplitude with both increasing turbulence levels and density gradient length is also observed again, as displayed in Fig. 12. Nevertheless, it is arguable for both A(t) and ϕ(t) fluctuations (and for radial and poloidal plasma flow cases for that matter) if non-linear or saturation regimes are reached at high δn e /n e . Further simulations, extending the turbulence level range, are planned to clarify this behavior.

Also, simulations with plasmas obtained from the output of gyro-fluid or gyro-kinetic turbulence codes are ongoing to have more realistic plasma models, which can then be benchmarked against the results presented here.

FIG. 1 .

 1 FIG. 1. Example of a 2D density turbulence realization (left) generated with a Kolmogorov-like model of a given amplitude k-spectrum (right).

FIG. 2 .

 2 FIG.2. Linear background density profiles (solid blue) and radial positions of the f p = 33 GHz and f p = 49 GHz cutoffs, together with the set of density turbulence level profiles (dashed red) employed for the numerical plasmas.

FIG. 3 .

 3 FIG. 3. Power spectra of complex amplitude signals A(t)e iϕ(t) for turbulence level scans, in two different density gradient lengths L n and two probing frequencies f p . Turbulence was generated using a Kolmogorov-like model and set to flow in the poloidal direction.

FIG. 4 .

 4 FIG. 4. Power spectra of A(t)e iϕ(t) signals on the re-scaled single-sided frequency axis and corresponding k ⊥ -axis, for a turbulence level scan with probing frequency f p = 33 GHz and short density gradient scale length L n .

FIG. 5 .FIG. 6 .FIG. 7 .

 567 FIG. 5. Spectral index obtained from the fluctuating components of A(t) and ϕ(t) signals in turbulence level scans with 2 probing frequencies f p and 2 density gradient scale lengths L n .

FIG. 8 .

 8 FIG.8. Average and standard deviation of reflectometry amplitude A(t) signals for turbulence level scans with 2 probing frequencies f p and 2 density gradient scale lengths L n .

FIG. 10 .

 10 FIG. 10. Time traces of reflectometry ϕ(t) signals for turbulence level scans with f p = 33 GHz probing frequency and 2 density gradient scales L n for both cases of inward and outward radial plasma flow.

FIG. 12 .

 12 FIG. 12. Average and standard deviation of the reflectometry amplitude A(t) signals for turbulence level scans in the case of outward radial plasma flow for 2 probing frequencies f p and 2 density gradient scale lengths L n .

ACKNOWLEDGMENTS

This work has been carried out within the framework of the EUROfusion Consortium and has received funding from the Euratom research and training programme 2014-2018 under Grant Agreement No. 633053. The views and opinions expressed herein do not necessarily reflect those of the European Commission. IST activities also received financial support from "Fundac ¸ão para a Ciência e Tecnologia" through Project No. UID/FIS/50010/2013.