On balance and consistency preserving 2-path signed graphs

Kshittiz Chettri^a , Biswajit Deb^b , Anjan Gautam^b

chabi.12.in@gmail.com, biswajittalk@gmail.com, anjangautam12@gmail.com

Let Σ = (G, σ) be a balanced and canonically consistent signed graph. The 2-path signed graph Σ#Σ = (G² , σ′ ) of Σ has the underlying graph as G² and the sign σ ′ (uv) of an edge uv in it is −1 whenever in each uv-path of length 2 in Σ all edges are negative; otherwise σ ′ (uv) is 1. Here, G² is the graph obtained from G by adding an edge between u and v if there is a path of length 2 between them. In this article, we have investigated balancedness and canonically consistency of 2-path signed graphs Σ#Σ of a balanced and canonically consistent signed graph Σ. The problem has been resolved completely for cycles, star graphs and trees.

Keywords: signed graphs, balance, consistent, 2-path signed graphs Mathematics Subject Classification: 05C22, 05C38, 05C76

DOI: 10.5614/ejgta.2023.11.2.4

1. Introduction

The signed graphs as a model to study psychological problems have been inspired from work of Fritz Heider[16] which tries to understand attitudes, relationships among various entities like persons, objects etc. It considers preferences like "positive or negative relationship of a person/entity with another person or entity like situations, events, ideas or things". More specifically, like/dislike (social networks), foreground/ background information (multimedia images), activation/inhibition

Received: 8 April 2022, Revised: 28 May 2023, Accepted: 17 June 2023.

^aDepartment of Mathematics, Nar Bahadur Bhandari Govt. College, Tadong, Sikkim, India.

^bDepartment of Mathematics, Sikkim Manipal Institute of Technology, Sikkim Manipal University, Majitar, Sikkim, India.

of brain regions (biological networks) are some of the naturally occurring situation that are modeled by signed graphs. Signed graphs also defines balanced state of an entity/ group of entity by considering their dynamic behaviour. It was systematically presented by Frank Harary [11] wherein signed graphs have been introduced and balancedness of such graphs have been characterized.

Historically, signed graphs have been introduced as a pair Σ = (G, σ) where G is an ordinary graph and σ is a mapping from V (G) to {1, −1}. Such graphs can also be viewed/thought as weighted graphs with edge weight 1 or −1. Signed graphs offer added flexibility to model data having the feature of bi-polar relationship (eg. yes or no, reliable or unreliable, like or dislike, positive correlation or negative correlation, weak or strong,etc.)

In the area of data science, graphs signal processing (GSP) has become a powerful and ground breaking tool for solving various learning and inference tasks[24, 19]. GSP encourage the use of graphs as combined information/data and computational models. Signed GSP is a recent concept and not much work has been done[8]. One of the applications of Signed GSP can be found in clustering problem.

A graph G consists of a finite non-empty set V (G), whose elements are called vertices together with a prescribed set E(G) of unordered pairs of distinct vertices. The elements of E(G) are called edges. By order and size of a graph G we refer to the number of vertices and edges in G, respectively. The basic terminologies and notations used in this article but undefined can be found in the book [12].

A signature on a graph G is a function σ : E(G) → {1, −1}. A graph G provided with a signature σ is called a signed graph, and will be denoted by Σ = (G, σ). The graph G is known as the underlying graph of the signed graph Σ = (G, σ). By vertex set of Σ we refer to the vertex set of the underlying graph of G, etc. For any edge e ∈ E(G), σ(e) is referred as the sign of the edge e in Σ.

By sign of a sub-graph H of a signed graph Σ = (G, σ) we mean the product of the sign of the edges in H and it is denoted by σ(H). The concept of signed graph was first introduced by Frank Harary in [11] to model a social problem. A signed graph is said to be balanced if every cycle in it has sign 1. In [11], Harary discussed a complete characterization of the balanced signed graphs in terms of the following theorem.

Theorem 1.1. (Harary's Balance Theorem). A signed graph Σ is balanced if and only if its vertex set can be partitioned into V1, V² in such a way that each positive edge connects two vertices either from V¹ or from V² and each negative edge connects a vertex from V¹ to a vertex from V2.

A marking on a graph G is a function µ : V (G) → {1, −1}. A graph G provided with a marking µ is called a marked graph. A signed graph Σ = (G, σ) provided with a marking µ is called a marked signed graph and it is denoted by Σµ.

Let µ be a marking on a graph G. By mark of a sub-graph H of G we mean the product of the marks of the vertices in H and it is denoted by µ(H). The concept of marked graph was first introduced by Harary and Cartwright in [7] to model a social problem. A marked graph is said to be consistent if every cycle in it has mark 1. The following characterization of marked graphs was given in [5].

Theorem 1.2. Any marked graph with only positive vertices is consistent.

Theorem 1.3. Any marked graph with only negative vertices is consistent if and only if its underlying graph is bipartite.

Corollary 1.1. If a marked graph is consistent then the sub-graph induced by its negative vertices is bipartite.

Further, in [17], it was noted that a marked graph is consistent if and only if, for any spanning tree T, all fundamental cycles are positive and all common paths of pairs of fundamental cycles have end points with the same marking.

Given a signed graph P = (G, σ) we can associate a natural marking

\[\mu : V(G) \to \{-1, 1\}\]

as follows: For any vertex v ∈ V (G)

\[\mu(v) = \begin{cases} +1, & \text{if } v \text{ is isolated;} \\ \prod_{u \in N(v)} \sigma(uv), & \text{otherwise;} \end{cases}\]

where N(v) is the open neighborhood of v in G. This marking µ is known as the canonical marking of the signed graph Σ and we use Σ^µ to denote the corresponding marked signed graph. A signed graph Σ is said to be canonically consistent if it is consistent with respect to the canonical marking.

Remark 1.1. All cycles are canonically consistent. But a cycle with all edges negative is balanced if and only if it has even number of vertices. For further studies on consistent and balanced graphs we refer [3, 4, 6, 5].

In [14, 13], an efficient algorithm was discussed to determine if a given signed graph is balanced or not by setting up a correspondence between marked graphs and balanced signed graphs. Later, this correspondence was exploited to solve the problem of enumeration of balanced signed graphs (Harary and Kabell [15]). The consistent marked graph characterization problem was solved by Beineke and Harary [5]. A polynomial time algorithm for recognizing consistent marked graphs was given by Rao in [20]. Later, a considerably simpler algorithm that is based on the fundamental cycle of a cycle basis for determining consistency was given by Hoede [17].

Some of the earliest works on 2-path graphs are done by Mukhopadhaya [18] where square of a graph G is denoted by adding edges to G that connect pair of vertices at a distance 2 apart. This notion has been generalised by Escalante, Montejano and Teresa [9] by introducing n-path graphs. It can also be seen as a generalization of open neighbourhood graphs first introduced by Acharya and Vartak [2].

The 2-path signed graph is defined by Sinha [31] and discussed the conditions under which a signed graph would be a 2-path signed graph. In this article, we attempted to study the canonically consistent balanced signed graphs whose 2-path signed graphs is also canonically consistent and balanced. For more one power graphs we refer [1].

2. 2-Path Signed Graphs

Given a graph G, we define n-path graph \(G^n\) of G to be the graph with vertex set same as G and two vertices in \(G^n\) are adjacent if and only if there is a path between them of length n in G. Let \(\Sigma = (G, \sigma)\) be a signed graph. The 2-path signed graph \(\Sigma \# \Sigma = (G^2, \sigma')\) of \(\Sigma\) has the underlying graph as \(G^2\) and the sign \(\sigma'(uv)\) of an edge uv in it is -1 whenever in each uv-path of length 2 in \(\Sigma\) all edges are negative; otherwise \(\sigma'(uv)\) is 1.

The signed graph \(\Sigma = (K_{4,1}, \sigma)\) and its 2-path signed graph is shown in the Figures 1 and 2, respectively.

Figure 1. The signed graph \(K_{4,1}^-\).

Figure 2. The 2-path product signed graph of \(K_{4,1}^-\).

Let \(\Sigma = (G, \sigma)\) be any signed graph and \(\Sigma \# \Sigma\) be the 2-path signed graph of it. Define

\(S_{bc} = \{\Sigma = (G, \sigma) \mid \Sigma \text{ is balanced and canonically consistent}\}\)

\(S_{bc}^{\#} = \{ \Sigma \in S_{bc} \mid \Sigma \# \Sigma \text{ is balanced and canonically consistent} \}\)

\(S_b^{\#} = \{ \Sigma \in S_{bc} \mid \Sigma \# \Sigma \text{ is balanced but not canonically consistent} \}\) \(S_c^{\#} = \{ \Sigma \in S_{bc} \mid \Sigma \# \Sigma \text{ is canonically consistent but not balanced} \}\) \(S_{\phi}^{\#} = \{ \Sigma \in S_{bc} \mid \Sigma \# \Sigma \text{ is neither canonically consistent nor balanced} \}\)

For any graph G, \(G^+\) denotes the sign graph with the underlying graph as G and in which each edge has sign 1. The following proposition shows that \(S_{bc}^{\#} \neq \phi\).

Proposition 2.1. For any graph G, \(G^+ \# G^+\) is balanced and canonically consistent.

Proof. For any graph G, all edges in \(G^+\) are positive and so \(G^+ \in S_{bc}\). By definition, all edges in \(G^+ \# G^+\) are also positive and the result follows.

Remark 2.1. If \(\Sigma = (C_n, \sigma)\), then the underlying graph of \(\Sigma \# \Sigma\) will consist of either a cycle or a pair of disjoint cycles. So, \(\Sigma \# \Sigma\) will be canonically consistent and hence \(\Sigma \not\in S_{\phi}^{\#}\).

For any graph G, \(G^-\) denotes the sign graph with the underlying graph G and in which each edge has sign -1. Clearly, \(C_{2n}^- \in S_{bc}\) but \(C_{2n+1}^- \notin S_{bc}\) for each positive integer n.

Proposition 2.2. \(C_{2n}^- \in S_{bc}^{\#}\) if and only if n is even.

Proof. \(C_{2n}^-\#C_{2n}^-\) is acyclic if and only if n=2 and so \(C_{2n}^-\in S_{bc}^\#\) for n=2. For \(n\geq 3\), \(C_{2n}^-\#C_{2n}^-\) consist of two disjoint copies of \(C_n^-\). So, \(C_{2n}^-\in S_{bc}^\#\) if and only if \(C_n^-\in S_{bc}\). But \(C_n^-\in S_{bc}\) if and only if n is even. Hence the result follows.

Proposition 2.3. \(C_{2n}^- \in S_c^{\#}\) if and only if n is odd.

Proof. Clearly \(n \geq 3\) and so \(C_{2n}^- \# C_{2n}^-\) consist of two disjoint copies of \(C_n^-\). But for odd values of \(n, C_n^-\) is canonically consistent and not balanced. Hence the result follows.

Theorem 2.1. For odd n, let the subgraph of \(\Sigma = (C_n, \sigma)\) induced by its negative edges has k components of order 3 or more. If the order of these k components are \(n_1, n_2, ..., n_k\) and n is odd then \(\Sigma\) is in \(S_{bc}^{\#}\) or \(S_c^{\#}\) according as \(\sum_{i=1}^k n_i\) is even or odd.

Proof. Let \(\Sigma_1, \Sigma_2, \ldots, \Sigma_k\) be the k components with order \(n_1, n_2, \ldots, n_k\) induced by the negative edges of \(\Sigma\), respectively. No other negative edge of \(\Sigma\) other than those corresponding to these k component contributes a negative edge to \(\Sigma \# \Sigma\). Also, the negative edges corresponding to the component \(\Sigma_i\), for \(i=1,2,\ldots,k\) contribute \(n_i-2\) edges with negative sign to \(\Sigma \# \Sigma\). Therefore, total number of negative edges in \(\Sigma \# \Sigma\) is \(\sum_{i=1}^k n_i-2k\).

So for odd n, \(\Sigma \# \Sigma\) is a cycle with \(\sum_{i=1}^k n_i - 2k\). Therefore, \(\Sigma \# \Sigma\) is balanced if and only if \(\sum_{i=1}^k n_i - 2k\) is even, that is, if and only if \(\sum_{i=1}^k n_i\) is even. Since a cycle is always consistent, so the result follows.

Theorem 2.2. For even n, let the vertices of \(\Sigma = (C_n, \sigma)\) are labeled cyclically using \(1, 2, \ldots, n\) and \(\Sigma^*\) be the subgraph of \(\Sigma\) induced by its negative edges. Let k be the number of components in \(\Sigma^*\) of even order congruent to 0 modulo 4. If \(t_{ei}(t_{oi})\) be the number of components in \(\Sigma^*\) that has odd order congruent to i modulo 4 with end vertices labeled by even (odd) vertices and \(\Sigma\) has at least one positive edge, then

\[\Sigma \in \begin{cases} S_{bc}^{\#}, & \text{if } k + t_{o1} + t_{e3} \text{ and } k + t_{o3} + t_{e1} \text{ are even.} \\ S_{c}^{\#}, & \text{otherwise.} \end{cases}\]

Proof. By assumption, two vertices i, j are adjacent in \(\Sigma \# \Sigma\) if and only if |i - j| = 2 or n - 2. Thus, we start by noting that \(\Sigma \# \Sigma\) has exactly two components each of which is a cycle. One of

these cycles consist of vertices with even labels and the other other one consist of vertices with odd labels. We denote the cycle with even(odd) labeled vertices by \(\Gamma_e\) (\(\Gamma_o\)) and refer it as even (odd) cycle. Since, cycles are always consistent, so is \(\Sigma \# \Sigma\).

Further, each component of even order in \(\Sigma^*\) contributes equal number of negative edges in both the cycles. Precisely, a component of even order in \(\Sigma^*\) contributes odd number of negative edges to each cycle if and only if the order is congruent to 0 modulo 4. Therefore, if k be the number of components in \(\Sigma^*\) of even order congruent to 0 modulo 4, the product of all the negative edges contributed to a cycle in \(\Sigma\#\Sigma\) by the components of even order in \(\Sigma^*\) is \((-1)^k\).

Let \(\Sigma_1^*\) be a component of order 4l+1 in \(\Sigma^*\) that starts with an even vertex. \(\Sigma_1^*\) will contribute 2l(2l-1) negative edges to \(\Gamma_e\) (\(\Gamma_o\)). So, the product of all these negative edges contributed to \(\Gamma_e\) (\(\Gamma_o\)) by each component of odd order congruent to 1 modulo 4 that starts with an even vertex is \(1((-1)^{t_{e1}})\).

Let \(\Sigma_1^*\) be a component of order 4l+1 in \(\Sigma^*\) that starts with an odd vertex. \(\Sigma_1^*\) will contribute 2l(2l-1) negative edges to \(\Gamma_o\) (\(\Gamma_e\)). So, the product of all these negative edges contributed to \(\Gamma_o\) (\(\Gamma_e\)) by each component of odd order congruent to 1 modulo 4 that starts with an odd vertex is \(1((-1)^{t_{o1}})\).

Let \(\Sigma_2^*\) be a component of order 4l+3 in \(\Sigma^*\) that starts with an odd vertex. \(\Sigma_2^*\) will contribute 2l(2l+1) negative edges to \(\Gamma_e\) (\(\Gamma_o\)). So, the product of all these negative edges contributed to \(\Gamma_e\) (\(\Gamma_o\)) by each component of odd order congruent to 3 modulo 4 that starts with an odd vertex is \(1((-1)^{t_{o3}})\).

Similarly, the product of all the negative edges contributed to \(\Gamma_o\) (\(\Gamma_e\)) by each component of odd order congruent to 3 modulo 4 that starts with an even vertex is \(1((-1)^{t_{e3}})\).

So, the product of the sign of the edges in \(\Gamma_e\) (\(\Gamma_o\)) is \((-1)^{k+t_{o1}+t_{e3}}((-1)^{k+t_{o3}+t_{e1}})\) and the result follows.

For any positive integer n if \(\Sigma = (K_{n,1}, \sigma)\) then two vertices in \(\Sigma \# \Sigma\) are adjacent if and only if they are the pendant vertices in \(\Sigma\). So, the underlying graph of \(\Sigma \# \Sigma\) consist of two components, namely \(K_n\) and \(K_1\). Also, the vertex in the component \(K_1\) is the center of \(\Sigma\).

Remark 2.2. For n=1,2 if \(\Sigma=(K_{n,1},\sigma)\) then \(\Sigma\#\Sigma\) is not cyclic and so \(\Sigma\#\Sigma\in S_{bc}^\#\).

Proposition 2.4. Let \(\Sigma = (K_{n,1}, \sigma)\) and \(n \geq 3\). If t be the number of negative edges in \(\Sigma\), then

• 1. \(\Sigma \in S_{bc}^{\#}\), if t = 1.
• 2. \(\Sigma \in S_c^{\#}\), if t = 2k + 1, k > 0 or t = 2, n = 3.
• 3. \(\Sigma \in S_{\phi}^{\#}\), otherwise.

Proof. If t>1 we will have a triangle in \(\Sigma\#\Sigma\) with one negative edge or three negative edges. So, it is not balanced.

Case 1. t=1 or 0. In this case, all edges in \(\Sigma \# \Sigma\) are positive and hence mark of all vertices is positive. So, the result is trivial.

Case 2a. t = 2k + 1, k > 0. In this case, every vertex of \(\Sigma \# \Sigma\) will have even number of negative edges incident with it. So, the mark of every vertex is positive and hence mark of every cycle is positive.

Case 2b. t = 2, n = 3. In this case Σ#Σ is a triangle with exactly one negative edge. As a signed cycle is always consistent, hence, it is consistent.

Case 3. t = 2k, k ≥ 1, n > 3. Let V ⁻ be the collection of all pendent vertices in Σ which has the sign of the edge incident with it as negative. In this case, each vertex of V ⁻ has 2k − 1 negative edges incident with it in Σ#Σ and all other vertices are incident with positive edges only. For k = 1, there will be a triangle in Σ#Σ with exactly one vertex in V ⁻ and for k > 1 there will be a triangle in Σ#Σ with three vertices from V ⁻. In either case, the resultant triangle is not consistent.

Theorem 2.3. If T is a tree and Σ = (T, σ), then Σ#Σ is balanced if and only if Σ does not have a sub-graph isomorphic to K1,³ with two or more negative edges. or If T is a tree and Σ = (T, σ), then Σ#Σ is balanced if and only if the number of negative edges incident with a vertex of degree 3 or more does not exceed 1.

Proof. First assume that, Σ has a sub-graph isomorphic to K1,³ with two or more negative edges. Then Σ#Σ contains a triangle with one or three negative edges. So, Σ#Σ is not balanced.

Conversely, assume that Σ#Σ contains a cycle C^k : v1v² · · · vkv¹ that is not balanced. Then, there exist vertices wⁱ , such that vⁱ ∼ wⁱ ∼ vi+1 in Σ for i = 1, 2, 3 · · · k, where vk+1 = v1. So, P : v1w1v² · · · vkwkv¹ is closed walk in Σ of length 2k. We claim that wi's are all same. To prove our claim, we apply induction on k.

For k = 3, P : v1w1v2w2v3w3v¹ is closed walk of length 6 and if all wi's are distinct then P is a cycle in Σ, a contradiction. Hence, at least one pair of wi's must be same. If w¹ = w² ̸= w³ then P ′ : v1w1v3w3v¹ is closed walk of length 4 and if w¹ ̸= w³ the P ′ is a cycle in Σ, a contradiction. So w¹ = w² = w³ = w.

As an induction hypothesis, assume that the claim is true for closed walks in Σ of length 2k or less. Let Ck+1 : v1v² · · · vk+1v¹ be an unbalanced cycle of size k + 1 in Σ#Σ. Then, there exist vertices wⁱ , such that vⁱ ∼ wⁱ ∼ vi+1 in Σ for i = 1, 2, 3 · · · k + 1, where vk+2 = v1. So, P : v1w1v² · · · vk+1wk+1v¹ is closed walk in Σ of length 2(k + 1). If for i = 1, 2, 3 · · · k + 1, wⁱ ,'s are distinct, then P is a cycle in Σ, a contradiction. So, let wⁱ = w^j for some i ̸= j. We now consider the following cases

Case 1. i + 1 = j

In this case, P¹ : v1w1v² · · · viwivj+1 · · · vk+1wk+1v¹ is closed walk of length 2k or less in Σ. So, by induction hypothesis all wi's must be same.

Case 2. j + 1 = i

In this case, P² : vi+1wi+1vi+2 · · · vjwivi+1 is a closed walk of length 2k or less in Σ. So, by induction hypothesis all wi's must be same.

Case 3. j + 1 ̸= i and i + 1 ̸= j

In this case, both P ′ : v1w1v² · · · viwivj+1 · · · vk+1wk+1v¹ and P ′′ : vi+1wi+1vi+2 · · · vjwivi+1 are closed walks of length less than 2k. So, by induction hypothesis all wi's must be same.

Let wⁱ = w for all i = 1, 2, · · · , k. Then v1, v2, · · · , vk, w induces a sub-graph of Σ that is a star with center at w. Since C^k : v1v² · · · vkv¹ is not balanced so it will contain odd number of negative edges. Hence the sub-graph Kk,¹ induced by v1, v2, · · · , vk, w has at least two negative edges.

Corollary 2.1. Let T be a tree and Σ = (T, σ) be a signed graph. Then Σ#Σ is balanced if and only if every vertex v in T with degree 3 or more has at most one negative edge incident with v.

The following notations are introduced to set the stage for our next result. For a vertex v in a signed graph Σ, define N ⁻(v) = {u ∈ N(v) | the edge {u, v} has negative sign} and n ⁻(v) = |N ⁻(v)|.

N − 2 (v) = {u ∈ N(x) − {v} | x ∈ N ⁻(v) and the edge {u, x} has negative sign} and n − 2 (v) = |N − 2 (v)|.

Theorem 2.4. Let T be a tree and Σ = (T, σ). Let W = {v ∈ V (T) | deg(v) ≥ 3}. Then Σ#Σ is canonically consistent if and only if each v ∈ W satisfies one of the following

• 1. P x∈N(v) n − 2 (x) even if |N(v)| = 3.
• 2. n − 2 (w) is even for each w ∈ N(v), otherwise.

Proof. We start by noting that, for x ∈ V (Σ), each negative edge incident with x in Σ#Σ is corresponding to a vertex in N − 2 (x). So the number of negative edges incident with x in Σ#Σ is n − 2 (x).

First assume that Σ#Σ is canonically consistent. Let v ∈ W be arbitrary. We consider the following cases.

Case 1. |N(v)| = 3.

Let N(v) = {x, y, z}. Then x, y, z, x is a cycle in Σ#Σ and no other cycle in Σ#Σ contains all these vertices. This cycle will be consistent if and only if the product of the negative edges incident with x, y, z in Σ#Σ is positive. That is, n − 2 (x) + n − 2 (y) + n − 2 (y) is even.

Case 2. |N(v)| ≥ 4.

Let N(v) = {x1, x2, . . . , xk} where k ≥ 4. Then any subset of size 3 or more in N(v) induces a cycle in Σ#Σ. Since Σ#Σ is consistent, so each of these cycles must have positive mark. That is, the sum of the number of negative edges incident with the vertices of each of these cycles should

be even. Which in turn implies P k i=1 n − 2 (xi) and P k i = 1 i ̸= j n − 2 (xi) are even for each j = 1, 2, . . . , k.

Hence the result follows.

Conversely, assume that Σ#Σ is not consistent. Then there exist a cycle C : x1, x2, . . . , xk, x¹ in Σ#Σ with negative mark. Without loss of generality, let no other cycle in Σ#Σ contains all the vertices x1, x2, . . . , xk. Then there exist a vertex v in Σ such that N(v) = {x1, x2, . . . , xk}.

If k = 3 and P 3 i=1 n − 2 (xi) is even then C is consistent, a contradiction. So, P 3 i=1 n − 2 (xi) must be odd.

If k > 3 and n − 2 (xi) is even for each i = 1, 2, . . . , k then P k i=1 n − 2 (xi) is even and hence C is consistent, a contradiction. Hence, n − 2 (xi) is odd for at least one i = 1, 2, . . . , k. This completes the proof of the theorem.

The results in the Proposition 2.4 and the Theorems 2.3, 2.4 are summarized in terms of the following theorem and so proof of this theorem is omitted. This theorem gives a complete characterization of the signed trees whose 2—path signed graph is balanced and canonically consistent.

Theorem 2.5. Let T be a tree, \(\Sigma = (T, \sigma)\) be a signed graph and \(W = \{v \in V(T) \mid deg(v) \geq 3\}\). Let

\[\begin{array}{lll} P1 & : & n^{-}(v) \leq 1 \, for \, all \, v \in W; \\ P2 & : & \sum_{x \in N(v)} n_{2}^{-}(x) \, even \, if \, |N(v)| = 3; \\ P3 & : & n_{2}^{-}(w) \, is \, even \, for \, each \, w \in N(v). \end{array}\]

Then

• (i) \(\Sigma \in S_{bc}^{\#}\), if P1 is true and either P2 or P3 is true.
• (ii) \(\Sigma \in S_b^{\#}\), if P1 is true and neither P2 nor P3 is true.
• (iii) \(\Sigma \in S_{c_{\cdot}}^{\#}\), if P1 is not true and either P2 or P3 is true.
• (iv) \(\Sigma \in S_{\phi}^{\#}\), otherwise.

3. Conclusion

In this article balancedness and consistency of 2-path signed graph[31] of a balanced and consistent signed graph have been discussed for cycles, star graphs and trees. We have obtained necessary and sufficient condition under which 2-path signed graph of a balanced and consistent graph \(\Sigma\) is consistent and balanced when G is a cycle, star graph or tree. The problem remain open for other classes of graphs. A similar study of 2-path product signed graphs is straight forward as 2-path product signed graphs of a signed graph is always balanced and consistent.

References

• [1] J. Abawajy, A. Kelarev, and M. Chowdhury, Power graphs: A survey, Electron. J. Graph Theory Appl. 1 (2) (2013), 125–147. http://dx.doi.org/10.5614/ejgta.2013.1.2.6.
• [2] B.D. Acharya and M.N. Vartak, Open neighborhood graphs, Indian Institute of Technology Department of Mathematics Research Report 6 (1973).
• [3] B. D. Acharya, A characterization of consistent marked graph, National Academy Science Letters 6 (1983), 431–440.
• [4] B.D. Acharya, Some further properties of consistent marked graphs, Indian Journal of Pure and Applied Mathematics 15 (8) (1984), 837 842.
• [5] L.W. Beineke and F. Harary, Consistency in marked digraphs, Journal of Mathematical Psychology 18 (1978), 260–269. https://doi.org/10.1016/0022-2496(78)90054-8.

• [6] L.W. Beineke and F. Harary, Consistent graphs with signed points, Rivista di matematica per le scienze economiche e sociali 1 (2) (1978), 81–88. https://link.springer.com/article/10.1007/BF02631374
• [7] D. Cartwright and F. Harary, Structural balance: a generalization of Heider's theory, Psychological review 63 (5) (1956), 277-293. https://psycnet.apa.org/doi/10.1037/h0046049
• [8] T. Dittrich and G. Matz, Signal Processing on Signed Graphs: Fundamentals and Potentials. IEEE Signal Processing Magazine 37 (6) (2020) 86–98. https://doi.org/10.1109/MSP.2020.3014060.
• [9] J. Escalante, L. Montejano, and T. Ceballos, Characterization of n-path graphs and of graphs having n-th root, J. Combin. Theory Ser. B 16 (6) (1974), 282–289. https://doi.org/10.1016/0095-8956(74)90074-4
• [10] M.K. Gill, Contributions to some topics in graph theory and its applications, Ph. D. thesis, The Indian Institute of Technology, Bombay, (1983).
• [11] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (2) (1953), 143– 146. doi: 10.1307/mmj/1028989917
• [12] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, (1969).
• [13] F. Harary and J.A. Kabell, A simple algorithm to detect balance in signed graphs, Mathematical Social Sciences 1 (1) (1980), 131–136. https://doi.org/10.1016/0165-4896(80)90010-4
• [14] F. Harary and J.A. Kabell, Counting balanced signed graphs using marked graphs, Proceedings of the Edinburgh Mathematical Society 24 (2) (1981), 99–104. https://doi.org/10.1017/S0013091500006398
• [15] F. Harary, E.M. Palmer, R.W. Robinson, and A.J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (4) (1977), 295–308. https://doi.org/10.1002/jgt.3190010405
• [16] F. Heider, Attitudes and cognitive organization, The Journal of Psychology 21 (1) (1946), 107–112. https://doi.org/10.1080/00223980.1946.9917275.
• [17] C. Hoede, A characterization of consistent marked graphs, J. Graph Theory 16 (1) (1992), 17–23. https://doi.org/10.1002/jgt.3190160104
• [18] A. Mukhopadhyay, The square root of a graph, J. Combin. Theory Ser. A 2 (1967), 290–295. https://doi.org/10.1016/S0021-9800(67)80030-9.
• [19] A. Ortega, P. Frossard, J. Kovacevi ˇ c, and J.M.F. Moura, and P. Vandergheynst, Graph Sig- ´ nal Processing: Overview, Challenges, and Applications. Proceedings of the IEEE 106 (5) (2018), 808–828. https://doi.org/10.1109/JPROC.2018.2820126.

• [20] S.B. Rao, Characterization of harmonious marked graphs and consistent nets, Journal of Combinatorics, Information and System Sciences, 9 (1984), 97 – 112.
• [21] F. S. Roberts, On the problem of consistent marking of a graph, Linear Algebra and its Applications 217 (1995), 255 – 263. https://doi.org/10.1016/0024-3795(94)00193-H
• [22] F.S Roberts and S. Xu, Characterizations of consistent marked graphs, Discrete Appl. Math. 127 (2) (2003), 357–371. https://doi.org/10.1016/S0166-218X(02)00254-8
• [23] D. Sehrawat and B. Bhattacharjya, Non-isomorphic signatures on some generalised Petersen graph, Electron. J. Graph Theory Appl. 9 (2) (2018), 235–256. http://dx.doi.org/10.5614/ejgta.2021.9.2.1
• [24] D.I. Shuman, S.K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine 30 (3) (2013), 83–98. https://doi.org/10.1109/MSP.2012.2235192.
• [25] D. Sinha and A. Dhama, Negation switching invariant signed graphs, Electron. J. Graph Theory Appl. 2 (1) (2014), 32–41. http://dx.doi.org/10.5614/ejgta.2013.2.1.3
• [26] D. Sinha and P. Garg, Balance and consistency of total signed graphs. Indian J. Math. 53 (1) (2011), 71– 81. https://doi.org/10.1007/s40009-015-0374-4
• [27] D. Sinha and P. Garg, Characterization of total signed graph and semi-total signed graphs, International Journal of Contemporary Mathematical Sciences 6 (5) (2011), 221– 228.
• [28] D. Sinha and P. Garg, On the regularity of some signed graph structures, AKCE Int. J. Graphs Comb. 8 (1) (2011), 63–74. https://www.tandfonline.com/doi/abs/10.1080/09728600.2011.12088931
• [29] D. Sinha and P. Garg, A characterization of canonically consistent total signed graphs, Notes on Number Theory and Discrete Mathematics, 19 (3) (2013), 70–77.
• [30] D. Sinha and P. Garg, Canonical consistency of semi-total point signed graphs, Nat. Acad. Sci. Lett. 38 (6) (2015), 497–500.
• [31] D. Sinha and D. Sharma, On 2-path signed graphs, International Workshop on Computational Intelligence (IWCI), IEEE, (2016), 218–220. https://ieeexplore.ieee.org/document/7860369.