Deepak Sehrawat, Bikash Bhattacharjya

Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati, India - 781039

deepakmath55555@iitg.ac.in, b.bikash@iitg.ac.in

In this paper we find the number of different signatures of P(3, 1), P(5, 1) and P(7, 1) up to switching isomorphism, where P(n, k) denotes the generalised Petersen graph, 2k < n. We also count the number of non-isomorphic signatures on P(2n + 1, 1) of size two for all n ≥ 1, and we conjecture that any signature of P(2n + 1, 1), up to switching, is of size at most n + 1.

Keywords: signed graph, generalised Petersen graph, balance, switching, switching isomorphism Mathematics Subject Classification: 05C22, 05C75

DOI: 10.5614/ejgta.2021.9.2.1

1. Introduction

Throughout the paper we consider simple graphs. For all the graph-theoretic terms that have not been defined but are used in the paper, see Bondy [1]. Harary [4] firstly introduced the notion of signed graph and balance. Harary [2] used them to model social stress in small groups of people in social psychology. Subsequently, signed graphs have turned out to be valuable. The fundamental property of signed graphs is balance. A signed graph is balanced if all its cycles have positive sign product. The second basic property of signed graphs is switching equivalence. Switching is a way of turning one signature of a graph into another, without changing cycle signs. Many properties of signed graphs are unaltered by switching, the set of negative cycles is a notable example. In [6], the non-isomorphic signatures on the Heawood graph are studied. The author in [9] determined the non-isomorphic signed Petersen graph, using the fact that the minimum signature on a cubic

Received: 27 March 2019, Revised: 6 January 2021, Accepted: 27 February 2021.

graph is a matching. Using the same technique, we find the number of non-isomorphic signatures on P(3, 1), P(5, 1) and P(7, 1). We also determine the number of non-isomorphic signatures of size two in P(2n + 1, 1) for all n ≥ 1.

2. Preliminaries

A signified graph is a graph G together with an assignment of + or − signs to its edges. If Σ is the set of negative edges, then we denote the signified graph by (G, Σ). The set Σ is called the signature of (G, Σ). Signature Σ can also be viewed as a function from E(G) into {+1, −1}. A resigning (switching) of a signified graph at a vertex v is to change the sign of each edge incident to v. We say (G, Σ2) is switching equivalent to (G, Σ1) if it is obtained from (G, Σ1) by a sequence of switchings. Equivalently, we say that (G, Σ2) is switching equivalent to (G, Σ1) if there exists a function f : V → {+1, −1} such that Σ2(e) = f(u)Σ1(e)f(v) for each edge e = uv of G. Resigning defines an equivalence relation on the set of all signified graphs over G (also on the set of signatures). Each such class is called a signed graph and is denoted by [G, Σ], where (G, Σ) is any member of the class.

We say two signified graphs (G, Σ1) and (H, Σ2) to be isomorphic if there exists a graph isomorphism ψ : V (G) → V (H) which preserve the edge signs. We denote it by Σ¹ ∼= Σ2. They are said to be switching isomorphic if Σ¹ is isomorphic to a switching of Σ2. That is, there exists a representation (H, Σ 0 2 ) which is equivalent to (H, Σ2) such that Σ¹ ∼= Σ 0 2 . We denote it by Σ¹ ∼ Σ2.

Proposition 2.1. [5] If G has m edges, n vertices and c components, then there are 2 (m−n+c) distinct signed graphs of G.

A cycle in a signified graph (G, Σ) is called positive if the product of its edge signs is positive and negative, otherwise. A signified graph (G, Σ) is called balanced if each cycle in (G, Σ) is positive and unbalanced, otherwise. One of the first theorems in the theory of signed graphs tells that the set of negative cycles uniquely determines the class of signed graphs to which a signified graph belongs. More precisely, we state the following theorem.

Theorem 2.1. [8] Two signatures Σ¹ and Σ² of a graph G are equivalent if and only if they have the same set of negative cycles.

3. Notations

The distance between two vertices x and y in a graph G, denoted by dG(x, y), is the length of a shortest path connecting x and y. The distance between two edges e¹ = u1u² and e² = v1v² in a graph G, denoted by dG(e1, e2), is min{dG(uⁱ , v^j ) : i ∈ {1, 2}, j ∈ {1, 2}}. For example, dG(e1, e2) = 1 for the edges e¹ = u0u¹ and e² = u2v² of the graph P(3, 1) in Figure 1. Throughout this paper, the solid lines and dotted lines in a graph represent positive and negative edges respectively.

In a signed graph [G, Σ], a signature Σ 0 which is equivalent to Σ is said to be a minimum signature if the number of edges in Σ 0 is minimum among all equivalent signatures of Σ. We

denote the number of edges in \(\Sigma'\) by \(|\Sigma'|\). For example, if \([G,\Sigma]\) is balanced then \(\Sigma'=\emptyset\) and thus \(|\Sigma'|=0\). A signed graph may have more than one minimum signatures. To see this, take a signified complete graph \((K_3,\Sigma)\), where \(\Sigma=\{12,23,31\}\). Switching \((K_3,\Sigma)\) by vertex 3 gives an equivalent signature \(\Sigma_1=\{12\}\) and by vertex 1 gives an equivalent signature \(\Sigma_2=\{23\}\). Clearly, \(\Sigma_1\) and \(\Sigma_2\) are minimum signatures of \((K_3,\Sigma)\).

The following theorem tells about the maximum degree of a vertex in a minimum signature, when the signature is considered as a spanning subgraph of a given graph G.

Theorem 3.1. Let \([G, \Sigma]\) be a signed graph on n vertices and let \(\Sigma'\) be an equivalent minimum signature of \(\Sigma\). Then \(d_{G_{\Sigma'}}(v) \leq \lfloor \frac{n-1}{2} \rfloor\) for each vertex \(v \in V(G_{\Sigma'})\).

Proof. Let, if possible, there exists a vertex \(u \in V(G_{\Sigma})\) such that \(d_{G_{\Sigma}}(u) > \frac{n-1}{2}\). Resign at u to get an equivalent signature \(\Sigma_1\). It is clear that \(|\Sigma| > |\Sigma_1|\). We apply the same operation on \(\Sigma_1\), if \(G_{\Sigma_1}\) has a vertex of degree greater than \(\frac{n-1}{2}\). Repeated application, if needed, of this process will ultimately give us an equivalent signature \(\tilde{\Sigma}\) of minimum number of edges such that degree of every vertex of \(\tilde{\Sigma}\) is at most \(\lfloor \frac{n-1}{2} \rfloor\). It is clear that \(|\tilde{\Sigma}| = |\Sigma'|\), and every vertex of \(\Sigma'\) has degree at most \(\lfloor \frac{n-1}{2} \rfloor\).

The following theorem will remain our key result throughout this paper.

Theorem 3.2. [9] Every minimum signature of a cubic graph is a matching.

From now onward, matching of a graph G stands for a minimum signature. With a few exceptions, most of the time switching transforms a matching (when considered as a signature) of P(n,1) to a new matching. The notation \(\Sigma(e_1,e_2,\ldots,e_k)\) denotes a signature or a set of edges \(\Sigma\) which contains the edges \(e_1,e_2,\ldots,e_k\) of a graph. For example, in the graph P(3,1) of Figure 1, \(\Sigma(u_0u_1,v_1v_2)\) denotes a signature containing the edges \(u_0u_1\) and \(v_1v_2\).

Further, we say that two signatures \(\Sigma_1\) and \(\Sigma_2\) of a graph G are automorphic if there exists an automorphism f of G such that \(uv \in \Sigma_1\) if and only if \(f(u)f(v) \in \Sigma_2\). If two signatures are automorphic then they are said to be automorphic type signatures. If two signatures \(\Sigma_1\) and \(\Sigma_2\) of a graph G are not automorphic to each other, then we say that they are distinct automorphic type signatures. For example, in the signed graphs \([P(5,1),\{u_1u_2\}]\) and \([P(5,1),\{u_3u_4\}]\), the signatures \(\{u_1u_2\}\) and \(\{u_3u_4\}\) are automorphic type signatures.

4. Generalised Petersen Graph

Let n and k be positive integers such that \(2 \le 2k < n\). The generalized Petersen graph, denoted by P(n,k), is defined to have the vertex set \(\{u_0,u_1,\ldots,u_{n-1},v_0,v_1,\ldots,v_{n-1}\}\) and edge set

\[\{u_i u_{i+1} : i = 0, 1, \dots, n-1\} \cup \{v_i v_{i+k} : i = 0, 1, \dots, n-1\} \cup \{u_i v_i : i = 0, 1, \dots, n-1\},\\]

where the subscripts are read modulo n. We call the cycle \(u_0u_1 \dots u_{n-1}u_0\) as outer cycle and the cycle \(v_0v_kv_{2k}\dots v_0\) as inner cycle of P(n,k). The edges of the form \(u_iv_i\) are called the spokes of P(n,k). It is clear that P(2n+1,1) has 4n+2 vertices and 6n+3 edges. Now we discuss certain structural facts of P(2n+1,1), where \(n \ge 1\).

Theorem 4.1. For \(n \ge 1\) and \(2 \le l \le 2n+1\), the number of 2l-cycles and the number of (2n+1)-cycles of P(2n+1,1) are 2n+1 and 2, respectively.

Proof. It is obvious that the cycles given by \(\{u_0, u_1, \dots, u_{2n}\}\) and \(\{v_0, v_1, \dots, v_{2n}\}\) are the only cycles of length 2n + 1. This proves the second part of the theorem.

We prove the first part of the theorem by counting the number of 2l-cycles, where \(2 \le l \le (2n+1)\). It is important to note that any even cycle in P(2n+1,1) must contain as many \(u_i\)'s as \(v_i\)'s. It is clear that for each \(i=0,1,\ldots,2n\), the cycle \(u_iv_iv_{i+1}\ldots v_{i+(l-1)}u_{i+(l-1)}u_{i+(l-2)}\ldots u_{i+1}u_i\) is of length 2l, and any even cycle of P(2n+1,1) is of this form. Hence there are 2n+1 cycles of P(2n+1,1) of length 2l, where \(2 \le l \le (2n+1)\). This proves the theorem.

Theorem 4.2. The distance between any two edges in P(2n + 1, 1) is at most n for all \(n \ge 1\).

Proof. It is clear that the distance between any two spokes of P(2n+1,1) is at most n. Further, the distance between any two edges of the outer, as well as of the inner cycle, is at most n. Without loss of generality, if we pick the edge \(u_0u_1\) from the outer cycle, then the edges \(v_nv_{n+1}\) and \(v_{n+1}v_{n+2}\) are the only edges of the inner cycle which are at maximum distance of n from \(u_0u_1\). Similarly, \(u_{n+1}v_{n+1}\) is the only spoke which is at maximum distance of n from \(u_0u_1\). This completes the proof of the theorem.

For each k = 0, 1, 2, ..., 2n, we define the permutations \(\gamma, \rho_k, \delta_k\) of V(G) such that for all i = 0, 1, 2, ..., 2n, we have

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Note that each \(\rho_k\) represents a clockwise rotation of P(2n+1,1). Also each \(\delta_k\) represents a reflection of P(2n+1,1) about a line induced by the edge \(u_k v_k\). Further, \(\gamma\) just swaps the inner and outer cycles of P(2n+1,1). Thus the automorphism group of P(2n+1,1) is given by

\[Aut(P(2n+1,1)) = \langle \rho_k, \delta_k, \gamma | k = 0, 1, 2, \dots, 2n \rangle.\]

Accordingly, the automorphisms of P(2n+1,1) are some combination of rotations, reflections and interchanges of \(v_i\)'s with \(u_i\)'s. Using this fact, if \(H_1\) and \(H_2\) are two given subgraphs of P(2n+1,1), it is easier to decide whether there is an automorphism of P(2n+1,1) that maps \(H_1\) onto \(H_2\).

Example 1. The graph P(3,1) is given in Figure 1. The automorphism \(\rho_1\) rotates the graph P(3,1) clockwise through the angle \(\frac{2\pi}{3}\), the automorphism \(\delta_1\) flips P(3,1) about the line containing the edge \(u_1v_1\) as its segment, and \(\gamma\) switches the cycles \(u_0u_1u_2\) and \(v_0v_1v_2\) to each other.

For more on automorphism group of generalised Petersen graph, see [3]. Yegnanarayanan [7] studied various aspects of the generalised Petersen graph.

Figure 1: The graph P(3, 1).

5. Signings on P (3, 1)

From Theorem 3.2, it is easy to see that finding non-isomorphic signatures on P(3, 1) is equivalent to determining the non-isomorphic matchings of P(3, 1) of size up to three. Let M^k denotes a matching of size k, where k = 0, 1, 2, 3. We classify all the automorphic type matchings of P(3, 1) of size up to three in the following lemmas. Let a matching of size zero be denoted by Σ0.

Lemma 5.1. The number of distinct automorphic type matchings of P(3, 1) of size one is two.

Proof. A matching of size one that does not contain a spoke is Σ1(u0u1). A matching of size one containing a spoke is Σ2(u0v0). It is easy to see that any other matching of size one is automorphic to either Σ¹ or Σ2, and that Σ¹ is not automorphic to Σ2. This proves the lemma.

Lemma 5.2. The number of distinct automorphic type matchings of P(3, 1) of size two is four.

Proof. We classify the matchings of size two by looking at the distance between their edges. Theorem 4.2 gives us that the distance between any two edges of P(3, 1) is at most one.

• (i) Let M² have no spoke. We may assume that one edge is u0u1. There are two possibilities for such matchings of size two. One of such matchings is Σ3(u0u1, v0v1) and another is Σ4(u0u1, v1v2).
• (ii) Let M² have one spoke and let it be u0v0. One of such matchings is Σ5(u0vo, u1u2).
• (iii) Let M² have two spokes. One of such matchings is Σ6(u0v0, u1v1).

Any other matching of P(3, 1) of size two is automorphic to Σ3, Σ4, Σ⁵ or Σ6. Further, no two of these matchings are automorphic. This concludes the proof of the lemma.

Lemma 5.3. The number of distinct automorphic type matchings of P(3, 1) of size three is two.

Proof. Any M³ must contain at least one spoke, as at most one edge can be taken from the inner cycle as well as from the outer cycle. If a matching of size three contains two spokes of P(3, 1), then no other edge can be included in that matching. Thus, following are the possibilities for M3.

(i) Let M³ have one spoke and let it be u0v0. There is only one possibility for such a matching, and let it be Σ7(u0v0, u1u2, v1v2).

(ii) Let M³ has three spokes and let that M³ be Σ8(u0v0, u1v1, u2v2).

Any other matching of size three is automorphic to Σ⁷ or Σ8, and that Σ⁷ is not automorphic to Σ8. This completes the proof.

The matchings obtained in the preceding lemmas along with Σ⁰ give us nine different automorphic type matchings of P(3, 1) viz., Σ0, Σ1, . . . , Σ8. However, some of these nine matchings may be switching isomorphic to each other. We have the following observations.

• In Σ6, by resigning at u0, u1, u2; we get a matching automorphic to Σ2. Thus Σ⁶ ∼ Σ2.
• In Σ7, by resigning at u1, v1, v0; we get a matching automorphic to Σ4. Thus Σ⁷ ∼ Σ4.
• In Σ8, by resigning at u0, u1, u2; we get a matching automorphic to Σ0. Thus Σ⁸ ∼ Σ0.

So we are left with the matchings Σ0, Σ1, Σ2, Σ3, Σ4, Σ5, and their corresponding signed graphs are depicted in Figure 2, where the label of the vertices correspond to that of Figure 1. In the following theorem we show that these six matchings are not switching isomorphic to each other.

Theorem 5.1. There are exactly six signed P(3, 1) up to switching isomorphisms.

Proof. The number of negative 3-cycles and negative 4-cycles for the signed P(3, 1) shown in Figure 2 are given in Table 1. We see that the set of negative cycles are different for all these six

Table 1: Number of negative 3-cycles and negative 4-cycles of some signed P(3, 1).

signatures. So by Theorem 2.1, we conclude that all these six signatures are pairwise not switching isomorphic. This completes the proof.

Figure 2: The six signed P(3, 1).

6. Signings on P (5, 1)

The graph P(5, 1) is shown in Figure 3. Recall from Theorem 3.2 that finding non-isomorphic signatures of P(5, 1) is equivalent to finding matchings of P(5, 1) of sizes 0, 1, 2, 3, 4 and 5, up to switching isomorphism. We now classify all the automorphic type matchings of P(5, 1) of sizes up to five. We denote a matching of size zero by Σ0. We emphasize that at most two edges of a matching may lie on the outer cycle or on the inner cycle. We use this fact to get the possible automorphic type matchings of different sizes.

Figure 3: The graph P(5, 1).

Lemma 6.1. The number of distinct automorphic type matchings of P(5, 1) of size one is two.

Proof. We have only the following two cases.

• (i) Let M¹ have no spoke. There is only one automorphic type matching of size one. One of such matchings is Σ1(u0u1).
• (ii) Let M¹ have one spoke. There is also only one automorphic type matching of size one. One of such matchings is Σ2(u0v0).

Any other matching of P(5, 1) of size one is automorphic to Σ¹ or Σ2, and that Σ¹ is not automorphic to Σ2. This completes the proof.

Lemma 6.2. The number of distinct automorphic type matchings of P(5, 1) of size two is eight.

Proof. We classify the matchings of size two by looking at the distance between the edges of the matching.

• (i) Let the edges of the matching be at distance one. There are five different automorphic type matchings of size two and one of each such automorphic type matchings is Σ3(u0u1, v0v1), Σ4(u0u1, v1v2), Σ5(u0u1, u2u3), Σ6(u0u1, v2u2) and Σ7(u0v0, u1v1). Let M² be a matching of size two other than Σ3, Σ4, Σ5, Σ⁶ and Σ⁷ whose edges are at distance one. Note that M² must contain either two spokes, or two edges from outer cycle, or two edges from inner cycle, or one edge from outer cycle and one from inner cycle, or one edge from outer/inner cycle and one spoke. In each of these cases, M² is automorphic to either Σ7, Σ5, Σ3, Σ⁴ or Σ6. Thus Σ3, Σ4, Σ5, Σ⁶ and Σ⁷ are the only automorphic type matchings of size two whose edges are at distance one. It is clear that these matchings are pairwise non-automorphic.
• (ii) Let edges of M² be at distance two. There are three automorphic type matchings of size two whose edges are at distance two. We denote them by Σ8(u0u1, v2v3), Σ9(u0u1, v3u3) and Σ10(u0v0, u2v2). In a similar manner (as in case(i)), one can show that any other matching of size two whose edges are at distance two is automorphic to one of Σ8, Σ⁹ and Σ10. The matchings Σ8, Σ⁹ and Σ¹⁰ are clearly pairwise non-automorphic.

This concludes the proof of the lemma.

Lemma 6.3. The number of distinct automorphic type matchings of P(5, 1) of size three is 11.

Proof. We classify all the automorphic type matchings of size three by looking at the number of spokes contained in these matchings.

• (i) Let M³ have no spoke. Out of three edges of M3, two edges lie on outer (inner) cycle and the remaining one edge lies on inner (outer) cycle. Because of the automorphism γ, we may assume that two edges are lying on the outer cycle, and let they be u0u¹ and u2u3. Therefore, the possible automorphic type matchings for this case are Σ11(u0u1, v0v1, u2u3), Σ12(u0u1, v1v2, u2u3) and Σ13(u0u1, v3v4, u2u3). Any other matching of size three which does not contain a spoke is automorphic to one of Σ11, Σ¹² and Σ13. Further, these matchings are not automorphic to each other.
• (ii) Let M³ have one spoke and let it be u0v0. If the other two edges of M³ lie either on the outer cycle or on the inner cycle, then one of such matchings is Σ14(u0v0, u1u2, u3u4). If one edge of M³ lies on the outer cycle and one lies on the inner cycle, then following are the only possibilities: Σ15(u0v0, u1u2, v1v2), Σ16(u0v0, u1u2, v2v3) and Σ17(u0v0, u2u3, v2v3). Any other matching of size three containing only one spoke is automorphic to one of Σ14, Σ15, Σ¹⁶ and Σ17. Further, no two of these matchings are automorphic.
• (iii) Let M³ have two spokes. If the spokes are consecutive then there is only one possibility, viz., Σ18(u0v0, u1v1, u2u3). If the spokes are not consecutive then there is also only one possibility, viz., Σ19(u0v0, v2u2, u3u4). Any other matching of size three containing only two spokes is automorphic to Σ¹⁸ or Σ19, and that Σ¹⁸ is not automorphic to Σ19.
• (iv) Let M³ have three spokes. In this case, there are only two automorphic type matchings of size three and one of each such type of matchings is Σ20(u0v0, u1v1, u2v2) and Σ21(u0v0, u1v1, u3v3). Any other matching of size three containing only spokes is automorphic Σ²⁰ or Σ21.

Lemma 6.4. The number of distinct automorphic type matchings of P(5, 1) of size four is 10.

Proof. We classify the matchings of size four by considering the number of spokes contained in these matchings.

• (i) Let M⁴ have no spoke. Note that, at most two edges of M⁴ may lie on the outer cycle and at most two edges may lie on the inner cycle. So, without loss of generality, let the edges u0u¹ and u2u³ be lie on the outer cycle. Thus following are the only possibilities for the matchings of size four having no spoke: Σ22(u0u1, u2u3, v0v1, v2v3), Σ23(u0u1, u2u3, v0v1, v3v4) and Σ24(u0u1, u2u3, v1v2, v3v4). Any other matching of size four which does not contain a spoke is automorphic to one of Σ22, Σ²³ and Σ24. Further, these matchings are pairwise non-automorphic.
• (ii) Let M⁴ have one spoke and let it be u0v0. Out of the three remaining edges, two edges will lie on the outer (inner) cycle and one edge will lie on inner (outer) cycle. The two edges which lie on the outer cycle can be taken to be u1u² and u3u4. Thus the possible automorphic type matchings of size four are Σ25(u0v0, u1u2, u3u4, v1v2) and Σ26(u0v0, u1u2, u3u4, v3v2). Any other matching of size four having only one spoke is automorphic to either Σ²⁵ or Σ26, and that Σ²⁵ is not automorphic to Σ26.
• (iii) Let M⁴ have two spokes. If spokes are at distance one then let they be u0v⁰ and u1v1. Further, out of remaining two edges, only one edge may lie on outer cycle and other may lie on inner inner. Let u2u³ lies on outer cycle. Then, the possible automorphic type matchings are Σ27(u0v0, u1v1, u2u3, v2v3) and Σ28(u0v0, u1v1, u2u3, v3v4). If the two spokes are at distance two then let they be u0v⁰ and u2v2. The only possibility for such matching is Σ29(u0v0, u2v2, u3u4, v3v4). Any other matching of size four with only two spokes is automorphic to one of Σ27, Σ²⁸ and Σ29. Also these matchings are pairwise non-automorphic.
• (iv) Let M⁴ have three spokes. If one of the spokes is at distance two from the other two spokes, then no edge from the outer or inner cycle can be contained in M4. Therefore, the only possibility is Σ30(u0v0, u1v1, u2v2, u3u4).
• (v) Let M⁴ have four spokes. One of such matchings is Σ31(u0v0, u1v1, u2v2, u3v3). Any other matching for this case is automorphic to Σ31.

This completes the proof of the lemma.

Lemma 6.5. The number of distinct automorphic type matchings of P(5, 1) of size five is three.

Proof. It is clear that a matching M⁵ of size five must have at least one spoke. Further, if M⁵ has exactly two spokes, then only three vertices are unsaturated in the outer cycle as well as in the inner cycle. However, we must have at least two edges in M⁵ either from the outer cycle or from the inner cycle. Therefore, M⁵ cannot have exactly two spokes. Similarly, M⁵ cannot have four spokes. Thus following are the only possible cases.

• (i) Let M⁵ have one spoke. There is only one such automorphism type M5. We denote it by Σ32(u0v0, u1u2, v1v2, u3u4, v3v4).
• (ii) Let M⁵ have three spokes. There is only one automorphism type of M5. We denote it by Σ33(u0v0, u1v1, u2v2, u3u4, v3v4).

(iii) Let M⁵ have five spokes. There is also only one automorphism type of M5. We denote it by Σ34(u0v0, u1v1, u2v2, u3v3, u4v4).

This completes the proof of lemma.

The matchings obtained in the preceding lemmas along with Σ⁰ give us 35 different automorphic type matchings of P(5, 1) viz., Σ0, Σ1, . . . , Σ34. However, some of these 35 matchings may be switching isomorphic to each other. We have the following observations.

• In Σ7, by resigning at u0, u1; we get a matching automorphic to Σ5. Thus Σ⁷ ∼ Σ5.
• In Σ11, by resigning at u1, u2, v1, v2; we get a matching automorphic to Σ1. Thus Σ¹¹ ∼ Σ1.
• In Σ12, by resigning at u1, u2, v1; we get a matching automorphic to Σ6. Thus Σ¹² ∼ Σ6.
• In Σ13, by resigning at u1, v1, u2, v2, v3; we get a matching automorphic to Σ9. Thus Σ¹³ ∼ Σ9.
• In Σ14, by resigning at u0, u1, u4; we get a matching automorphic to Σ10. Thus Σ¹⁴ ∼ Σ10.
• In Σ15, by resigning at u0, u1, v1; we get a matching automorphic to Σ4. Thus Σ¹⁵ ∼ Σ4.
• In Σ17, by resigning at u0, u1, u2, v1, v2; we get a matching automorphic to Σ4. Thus Σ¹⁷ ∼ Σ4.
• In Σ18, by resigning at u1, u2, u0; we get a matching automorphic to Σ9. Thus Σ¹⁸ ∼ Σ9.
• In Σ20, by resigning at u0, u1, u2; we get a matching automorphic to Σ5. Thus Σ²⁰ ∼ Σ5.
• In Σ21, by resigning at u0, u1, u2, u3, u4; we get a matching automorphic to Σ10. Thus Σ²¹ ∼ Σ10.
• In Σ22, by resigning at u1, v1, u2, v2; we get a matching automorphic to Σ0. Thus Σ²² ∼ Σ0.
• In Σ23, by resigning at u1, u2, v1, v2, v3; we get a matching automorphic to Σ2. Thus Σ²³ ∼ Σ2.
• In Σ24, by resigning at u1, u2, v2, v3; we get a matching automorphic to Σ6. Thus Σ²⁴ ∼ Σ6.
• In Σ25, by resigning at u0, u1, u4, v0, v1, v4; we get a matching automorphic to Σ6. Thus Σ²⁵ ∼ Σ6.
• In Σ26, by resigning at u0, u1, u4; we get a matching automorphic to Σ19. Thus Σ²⁶ ∼ Σ19.
• In Σ27, by resigning at u0, u1, u2, v2; we get a matching automorphic to Σ8. Thus Σ²⁷ ∼ Σ8.
• In Σ28, by resigning at u0, u1, u2; we get a matching automorphic to Σ16. Thus Σ²⁸ ∼ Σ16.
• In Σ29, by resigning at u3, v2, v3; we get a matching automorphic to Σ16. Thus Σ²⁹ ∼ Σ16.

• In Σ30, by resigning at u0, u1, u2, u4; we get a matching automorphic to Σ6. Thus Σ³⁰ ∼ Σ6.
• In Σ31, by resigning at u0, u1, u2, u3, u4; we get a matching automorphic to Σ2. Thus Σ³¹ ∼ Σ2.
• In Σ32, by resigning at v2, u2, u3, v3; we get a matching automorphic to Σ2. Thus Σ³² ∼ Σ2.
• In Σ33, by resigning at u0, u1, u2, u3, v3; we get a matching automorphic to Σ8. Thus Σ³³ ∼ Σ8.
• In Σ34, by resigning at u0, u1, u2, u3, u4; we get a matching automorphic to Σ0. Thus Σ³⁴ ∼ Σ0.

Thus we are left with 12 different matchings viz., Σ0, Σ1, Σ2, Σ3, Σ4, Σ5, Σ6, Σ8, Σ9, Σ10, Σ16, and Σ19. The corresponding signified graphs of these 12 matchings are shown in Figure 4, where the label of the vertices correspond to that of Figure 3.

Figure 4: Twelve signed P(5, 1).

Theorem 6.1. There are exactly twelve signed P(5, 1) up to switching isomorphism.

Proof. The number of negative 4-cycles, negative 5-cycles and negative 6-cycles for the 12 signed P(5, 1) in Figure 4 are given in Table 2.

From Theorem 2.1 and Table 2, it is easy to see that the twelve signed P(5, 1), shown in Figure 4, are non-switching isomorphic. This concludes the proof of the theorem.

7. Signings on P (7, 1)

The graph P(7, 1) is shown in Figure 5. From Theorem 4.1, we see that the number of 4 cycles, 6-cycles, 7-cycles and 8-cycles in P(7, 1) are 7, 7, 2 and 7, respectively. We now find the non-isomorphic matchings of sizes 0, 1, 2, 3, 4, 5, 6 and 7, up to switching isomorphism. We have the following lemmas to settle the possible cases of matchings of different sizes.

Figure 5: The graph P(7, 1).

Lemma 7.1. Consider the subsets σ¹ = {u0u1, v0v1, v2u2}, σ² = {u0u1, v1v2, u2u3}, σ³ = {u0u1, v1v2, v4v5}, σ⁴ = {u0u1, v0v1, u3u4}, σ⁵ = {u0u1, v0v6, u3u4}, σ⁶ = {u0v0, u1v1, v2v3} and σ⁷ = {u0v0, u1v1, u2v2} of edges of P(7, 1). If any one of these seven signatures appears in a matching M^l of P(7, 1), where l ≥ 3, then M^l is switching equivalent to M^{l 0}, where l ⁰ ≤ l − 1.

Proof. Let M j l be a matching of size j which contains the set σ^j , where j = 1, . . . , 7 and l ≥ 3. Consider the sets S¹ = {u1, v1, v2}, S² = {u1, v2, u2}, S³ = {u1, v2, u2, u3, u4, v3, v4}, S⁴ = {u1, v1, u2, v2, v3, u3}, S⁵ = {v0, u1, v1, u2, v2, u3, v3}, S⁶ = {v1, v2, v0} and S⁷ = {u0, u1, u2}. If we resign at the vertices belonging to S^j , then we get a signature of size up to l −1, i.e., M^l ∼ M^l 0, where l ⁰ ≤ l − 1. This proves the lemma.

In Lemma 7.1, the inequality l ⁰ ≤ (l − 1) may be strict. For example, if M³ = σ4, then by resigning at the vertices u1, v1, u2, v2, v³ and u3, we get M³ ∼ M1. The matchings σⁱ , where 1 ≤ i ≤ 7, are said to be forbidden matchings of P(7, 1). Let M⁰ denotes the matching Σ¹ = ∅ of size zero. Further, there are only two automorphic type matchings of size one, we denote them by Σ2(u0u1) and Σ3(u0v0). Any other matching of P(7, 1) of size one is automorphic to either Σ² or Σ3, and that Σ² is not automorphic to Σ3.

Lemma 7.2. The number of distinct automorphic type matchings of P(7, 1) of size two is 12.

Proof. We classify these matchings by looking at the distance of their edges. Recall that the distance between any two edges of P(7, 1) is at most three.

• (i) Let the edges of M² be at distance one. Five such possible matchings of size two are Σ4(u0u1, v0v1), Σ5(u0u1, v1v2), Σ6(u0u1, v2u2), Σ7(u0u1, u2u3) and Σ8(u0v0, u1v1). Note that any matching of P(7, 1) of size two contains either two consecutive spokes, or one spoke and one edge from outer (inner) cycle or two edges from the outer (inner) cycle, or one edge from the inner cycle and one from the outer cycle. Each such possible M2, whose edges are at distance one, is automorphic to one of Σ8, Σ6, Σ7, Σ⁴ and Σ5. These five matchings are also pairwise non-automorphic.
• (ii) Let the edges of M² be at distance two. There are only four automorphic type matchings of size two having edges at distance two. We denote them by Σ9(u0u1, v2v3), Σ10(u0u1, v3u3), Σ11(u0v0, v2u2) and Σ12(u0u1, u3u4). It is easy to see that any other matching of size two whose edges are at distance two is automorphic to one of Σ9, Σ10, Σ¹¹ and Σ12. Further, these matchings are pairwise non-automorphic.
• (iii) Let the edges of M² be at distance three. There are only three automorphic type matchings of size two whose edges are at distance three. We denote them by Σ13(u0u1, v3v4), Σ14(u0u1, v4u4) and Σ15(u0v0, v3u3). Any other M² whose edges are at distance three is automorphic to one of Σ13, Σ¹⁴ and Σ15. Further, no two of these matchings are automorphic to each other.

This completes the proof.

Lemma 7.3. The number of distinct automorphic type matchings of P(7, 1) of size three is 23.

Proof. We classify matchings of size three on the basis of the number of spokes contained in it. Since each forbidden matching is a matching of size three and that they are switching equivalent to a matching of size at most two, we consider matchings other than the forbidden matchings.

• (i) Let M³ have no spoke. The possible distinct automorphic type matchings of size three without spokes are denoted by Σ16(u0u1, u2u3, u4u5), Σ17(u0u1, u2u3, v4v5) and Σ18(u0u1, u4u3, v5v6). Any other matching of size three with no spokes is either a forbidden matching or automorphic to one of Σ16, Σ¹⁷ and Σ18. Further, it is easy to see that they are pairwise non-automorphic.
• (ii) Let M³ have only one spoke, say u0v0. Possible automorphic type matchings are Σ19(u0v0, u1u2, u3u4), Σ20(u0v0, u1u2, u4u5), Σ21(u0v0, u1u2, u5u6), Σ22(u0v0, u2u3, u4u5), Σ23(u0v0, u1u2, v2v3), Σ24(u0v0, u1u2, v3v4), Σ25(u0v0, u1u2, v4v5), Σ26(u0v0, u1u2, v5v6), Σ27(u0v0, u2u3, v3v4), Σ28(u0v0, u2u3, v4v5), Σ29(u0v0, u2u3, v5v6) and Σ30(u0v0, u3u4, v5v6). Any other matching of size three containing only one spoke is automorphic to one of these twelve matchings. Further, any two of these matchings are pairwise non-automorphic.
• (iii) Let M³ have only two spokes. If the spokes are consecutive then let they be v0u⁰ and v1u1. Thus the only possible automorphic type matching is Σ31(v0u0, v1u1, u3u4). If spokes are at distance two then let the spokes be v0u⁰ and v2u2. The possible automorphic type

matchings are Σ32(v0u0, v2u2, u3u4) and Σ33(v0u0, v2u2, u4u5). If the spokes are at distance three then let they be v0u⁰ and v3u3. The possible automorphic type matchings are Σ34(v0u0, v3u3, u1u2) and Σ35(v0u0, v3u3, u4u5). Because of the forbidden matchings and the automorphism group of P(7, 1), it is easy to see that any other matching of size three containing only two spokes is automorphic to one of Σ31, Σ32, Σ33, Σ³⁴ and Σ35. Further, these matchings are pairwise non-automorphic.

(iv) Let M³ have three spokes. The possible automorphic type matchings of size three having three spokes are Σ36(v0u0, v1u1, u3v3), Σ37(v0u0, v1u1, u4v4) and Σ38(v0u0, v2u2, u4v4). Any matching of size three with three spokes is automorphic to Σ36, Σ³⁷ or Σ38. Also, these matchings are pairwise non-automorphic.

This completes the proof of the lemma.

Lemma 7.4. The number of distinct automorphic type matchings of P(7, 1) of size four is 10.

Proof. We classify the matchings of size four on the basis of number of spokes contained in it. If any M⁴ contains a forbidden matching then that matching is not considered as a possible candidate for distinct automorphic type matching of size four.

• (i) Let M⁴ have no spoke. It is clear that any such M⁴ has its three edges on outer cycle and the remaining edge on the inner cycle, or two edges on the inner cycle and other two edges on the outer cycle. Therefore, any such M⁴ must contain one of σ2, σ³ and σ4. Hence by Lemma 7.1, every matching of size four containing no spoke is equivalent to a matching M^l 0, where l ⁰ ≤ 3.
• (ii) Let M⁴ have one spoke and let it be u0v0. It is clear that the remaining three edges of M⁴ either lie on the outer (inner) cycle, or two edges lie on the outer cycle and one edge lies on the inner cycle. If three edges lie on the outer cycle, then one such matching is Σ39(v0u0, u1u2, u3u4, u5u6). If two edges lie on the outer cycle and one edge lies on the inner cycle, then the possible automorphic type matchings are Σ40(v0u0, u1u2, u3u4, v5v6) and Σ41(v0u0, u1u2, v3v4, u5u6). Any other matching of size four containing only one spoke either contains one of the forbidden matchings or automorphic to one of Σ39, Σ⁴⁰ and Σ41. Further, these three matchings are pairwise non-automorphic.
• (iii) Let M⁴ have two spokes. If the spokes are consecutive then by resigning at the end vertices of the spokes lying on the outer cycle, we find that the matching is equivalent to a matching (signature) of size four. Note that this resultant signature is either equivalent to a matching of size four of case (i) or it is not a matching. Therefore in both cases, it is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 3. If the spokes are at distance two or three, then the possible automorphic type matchings of size four are Σ42(v0u0, v2u2, u3u4, u5u6), Σ43(v0u0, v2u2, u3u4, v5v6), Σ44(v0u0, v2u2, u4u5, v5v6), Σ45(v0u0, v3u3, u1u2, u4u5), Σ46(v0u0, v3u3, u1u2, v4v5) and Σ47(v0u0, v3u3, u4u5, v5v6). Any other matching of size four containing only two spokes is automorphic to one of these six matchings. Further, any two of these matchings are pairwise non-automorphic.
• (iv) Let M⁴ have three spokes. It is clear that a matching of size four cannot contain two or three consecutive spokes up to switchings. Thus the only possible automorphic type matching is Σ48(v0u0, v2u2, v4u4, u5u6).

(v) Let M⁴ have four spokes. By resigning at the vertices from the set {u0, u1, u2, u3, u4, u4, u6}, we see that such a matching is equivalent to a matching of size three containing three spokes.

This proves the lemma.

Theorem 7.1. Every matching of P(7, 1) of size five is switching equivalent to a matching M^l 0, where l ⁰ ≤ 4.

Proof. We prove the theorem by classifying the matchings of size five on the basis of number of spokes contained in it.

• (i) Let M⁵ have no spoke. Note that three edges of M⁵ may lie on the outer (inner) cycle and remaining two edges lie on the inner (outer) cycle. It is easy to see that each such combination of five edges of P(7, 1) must contain either σ² or σ4. Therefore by Lemma 7.1, each such M⁵ is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4.
• (ii) Let M⁵ have only one spoke and let it be u0v0. There are two possibilities for the remaining four edges of M5.
  • (a) Three edges of M⁵ lie on the outer (inner) cycle and one edge lies on the inner (outer) cycle.
  • (b) Two edges of M⁵ lie on the outer cycle and remaining two edges lie on the inner cycle. Note that in (a), the three edges lying on the outer cycle must be u1u2, u3u⁴ and u5u6. Therefore for the fifth edge of M5, whichever edge we choose from the inner cycle, M⁵ will contain either σ² or σ4. Hence by Lemma 7.1, each such M⁵ is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4.
  • In (b), let two edges of M⁵ lying on the outer cycle be u1u² and u3u4. The possibilities for the remaining two edges from the inner cycle are {v1v2, v3v4}, {v1v2, v4v5}, {v1v2, v5v6}, {v2v3, v4v5}, {v2v3, v5v6} and {v3v4, v5v6}. In all of these possible cases, it is easy to see that M⁵ contains a forbidden matching. Hence by Lemma 7.1, each such M⁵ is switching equivalent to some matching M^{l 0}, where l ⁰ ≤ 4. In the similar way, it can be proved that any other matching of size five, containing one spoke and two edges from both outer as well as inner cycles, is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4.
• (iii) Let M⁵ have two spokes. If M⁵ has two consecutive spokes, i.e., spokes at distance two, then by switching at their end vertices lying on outer cycle, we find that M⁵ is switching equivalent to either a signature of P(7, 1) of size five with no spokes or a matching of size five with no spoke. In both cases, M⁵ is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4.
  • If two spokes of M⁵ are at distance two then let they be u0v⁰ and u2v2. The remaining three edges have to be chosen from {u3u4, u4u5, u5u6, v3v4, v4v5, v5v6}. We can take two edges from outer cycle and one edge from inner cycle or vice-versa. If the two edges from the outer cycle are u3u⁴ and u5u6, then for all possible choices of the edge from the inner cycle, M⁵ must contain either σ¹ or σ2. Similarly, if two edges are taken from the inner cycle, M⁵ will contain some forbidden matching. Hence each such M⁵ is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4. Similarly, it can be shown that if the two spokes of M⁵ are at distance three, then also M⁵ is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4.

• (iv) Let M⁵ have three spokes. It is clear from part (iii) that, out of the three spokes, no two spokes can be at distance one. Hence the only possibility for such a matching of size five is {u0v0, u2v2, u4v4, u5u6, v5v6}. But this matching contains σ1, hence by Lemma 7.1, we get that this M⁵ is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4.
• (v) Let M⁵ have four spokes. Obviously, resigning at u0, u1, u2, u3, u4, u⁵ and u6, each such matching of size five becomes switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4.
• (vi) Let M⁵ have five spokes. Resigning at u0, u1, u2, u3, u4, u⁵ and u6, we see that each such matching of size five is switching equivalent to a matching of size two.

This completes the proof of theorem.

Note that any matching of P(7, 1) of size six or seven contains some M5. So by Theorem 7.1, we get the following corollary.

Corollary 7.1. Every matching of P(7, 1) of size six or seven is switching equivalent to a matching M^{l 0}, where l ⁰ ≤ 4.

In the preceding lemmas, along with the signatures Σ1, Σ² and Σ3, we get 48 distinct automorphic type matchings of P(7, 1) of different sizes. However, among these 48 automorphic type matchings, some of them may be switching isomorphic to each other. Now we attempt to eliminate such switching isomorphic matchings. We have the following observations.

• In Σ8, by resigning at u0, u1; we get a matching of size two automorphic to Σ7. Therefore Σ⁸ ∼ Σ7.
• In Σ17, by resigning at u1, v1, u2, v² and using the automorphism γ; we get a matching automorphic to Σ16. Thus Σ¹⁷ ∼ Σ16.
• In Σ18, by resigning at u0, v0, u6, v⁶ and using the automorphisms δ³ followed by δ5; we get a matching automorphic to Σ17. Thus Σ¹⁸ ∼ Σ17.
• In Σ20, by resigning at u1, u0; we get a matching automorphic to Σ19. Thus Σ²⁰ ∼ Σ19.
• In Σ21, by resigning at u1, u0, u6; we get a matching automorphic to Σ11. Thus Σ²¹ ∼ Σ11.
• In Σ25, by resigning at u0, u1, and using the automorphism δ1; we get a matching automorphic to Σ24. Thus Σ²⁵ ∼ Σ24.
• In Σ26, by resigning at v1, v0, v6, u1; we get a matching automorphic to Σ23. Thus Σ²⁶ ∼ Σ23.
• In Σ29, by resigning at v6, v⁰ and using the automorphism γ; we get a matching automorphic to Σ24. Thus Σ²⁹ ∼ Σ24.
• In Σ30, by resigning at v6, v⁰ and using the automorphism γ; we get a matching automorphic to Σ25. Thus we get Σ³⁰ ∼ Σ25.
• In Σ31, by resigning at u0, u1; we get a matching automorphic to Σ16. Thus Σ³¹ ∼ Σ16.

• In Σ34, by resigning at u2u3; we get a matching automorphic to Σ32. Thus Σ³⁴ ∼ Σ32.
• In Σ36, by resigning at u0, u¹ and using the automorphism δ5; we get a matching automorphic to Σ19. Thus Σ³⁶ ∼ Σ19.
• In Σ37, by resigning at u0, u1; we get a matching automorphic to Σ22. Thus Σ³⁷ ∼ Σ22.
• In Σ39, by resigning at u6, u0, u1; we get a matching automorphic to Σ33. Thus Σ³⁹ ∼ Σ33.
• In Σ40, by resigning at u0, u1, u4, u5, u6, v4, v⁵ and using γ; we get a matching automorphic to Σ33. Thus Σ⁴⁰ ∼ Σ33.
• In Σ41, by resigning at u0, u1, u⁶ and using γ; we get a matching automorphic to Σ33. Thus Σ⁴¹ ∼ Σ33.
• In Σ42, by resigning at u0, u1, u2, u3, u6, v⁴ and v5; we get matching automorphic to Σ38. Thus Σ⁴² ∼ Σ38.
• In Σ44, by resigning at u0, u5, u6, v⁵ and using δ4; we get a matching automorphic to Σ46. Thus Σ⁴⁴ ∼ Σ46.
• In Σ45, by resigning at u0, u1; we get a matching automorphic to Σ42. Thus Σ⁴⁵ ∼ Σ42.
• In Σ46, by resigning at u2, u³ and using δ5; we get a matching automorphic to Σ43. Thus Σ⁴⁶ ∼ Σ43.
• In Σ47, by resigning at u4, v5, v4, v³ and using γ; we get a matching automorphic to Σ44. Thus Σ⁴⁷ ∼ Σ44.

Hence we are left with the following matchings: Σ1, Σ2, Σ3, Σ4, Σ5, Σ6, Σ7, Σ8, Σ9, Σ10, Σ11, Σ12, Σ13, Σ14, Σ15, Σ18, Σ19, Σ22, Σ23, Σ25, Σ27, Σ32, Σ33, Σ36, Σ37, Σ⁴¹ and Σ47. The corresponding signed graphs of these matchings are shown in Figure 6, where the label of the vertices correspond to that of Figure 5.

Theorem 7.2. There are exactly 27 different signed P(7, 1) up to switching isomorphism.

Proof. Let |C − 4 |, |C − 6 |, |C − 7 | and |C − 8 | denote the number of negative 4-cycles, negative 6-cycles, negative 7-cycles and negative 8-cycles of a signed graph. These numbers for the signed graphs shown in Figure 6 are given in Table 3 and Table 4. From Table 3, Table 4 and Theorem 2.1, it is clear that all these 27 signed P(7, 1) are switching non-isomorphic. This concludes the proof of theorem.

Figure 6: Twenty seven signed P(7, 1).

\(\Sigma_9\)\(\Sigma_{15}\)\(\sum_{1}\)\(\Sigma_2\)\(\Sigma_3\)\(\Sigma_4\)\(\Sigma_5\)\(\Sigma_6\)\(\Sigma_7\)\(\Sigma_{10}\)\(\Sigma_{11}\)\(\Sigma_{12}\)\(\Sigma_{13}\)\(\Sigma_{14}\)\(\overline{|C_4^-|}\)\(\overline{|C_6^-|}\)\(|C_7|\)

Table 3: The number of negative 4, 6, 7, and 8-cycles of some signed graphs of Figure 6.

Table 4: The number of negative 4, 6, 7 and 8-cycles of some signed graphs of Figure 6.

8. Conclusions and Remarks

In the Sections 5, 6 and 7, we have found the exact number of non-isomorphic signatures of P(3,1), P(5,1) and P(7,1) up to switching. However this number for the general case is still unknown. So, it is natural to pose the following problem.

Problem 1. What is the exact number of non-switching isomorphic signatures on P(2n+1,1) for all \(n \ge 4\) up to switching?

We have a partial answer towards the solution of Problem 1, that is, we give the answer for non-isomorphic matchings (or minimum signatures) of size two of P(2n+1,1) for all \(n \ge 4\). We have the following theorem.

Theorem 8.1. Up to switching isomorphism, the number of matchings of P(2n + 1, 1) of size two is 4n - 1, where \(n \ge 4\).

Proof. From Theorem 4.2, we know that edges of any \(M_2\) can be at maximum distance n. Four matchings of size two, whose edges are at distance one are \(M_2^{11} = \{u_0u_1, v_0v_1\}\), \(M_2^{12} = \{u_0u_1, u_2v_2\}\), \(M_2^{13} = \{u_0u_1, v_1v_2\}\) and \(M_2^{14} = \{u_0u_1, u_2u_3\}\). For any matching of size two whose edges lie either on the inner cycle or on the outer cycle of P(2n+1,1), there exists some automorphism \(\rho_k\) of P(2n+1,1) which maps the matching onto \(M_2^{14}\). If a matching of size two contains any two spokes which are at distance one, then by resigning at their end points lying on the outer cycle, we see that resultant matching is automorphic to \(M_2^{14}\). Similarly, it can be shown that all other matchings of size two whose edges are at distance one are automorphic to one of \(M_2^{11}\), \(M_2^{12}\) and \(M_2^{13}\).

Further, the number of negative 4-cycles in \(M_2^{11}\), \(M_2^{12}\), \(M_2^{13}\) and \(M_2^{14}\) are 0, 3, 2 and 2, respectively. The number of negative 2n + 1-cycles in \(M_2^{11}, M_2^{12}, M_2^{13}\) and \(M_2^{14}\) are 2, 1, 2 and 0, respectively. These numbers of negative cycles show that \(M_2^{11}, M_2^{12}, M_2^{13}\) and \(M_2^{14}\) are pairwise non-isomorphic. Hence up to switching isomorphism, \(M_2^{11}, M_2^{12}, M_2^{13}\) and \(M_2^{14}\) are the only matchings of size two whose edges are at distance one. Similarly, For each i, one can show up to switching isomorphism that there are exactly four matchings of size two whose edges are at distance i, where \(2 \le i < n\).

Three matchings of size two whose edges are at distance n are \(M_2^{n_1} = \{u_0u_1, u_{n+1}v_{n+1}\},\)\(M_2^{n2} = \{u_0u_1, v_nv_{n+1}\}\) and \(M_2^{n3} = \{u_0v_0, u_nv_n\}\). It is clear that any other matching of size two whose edges are at distance n is automorphic to one of \(M_2^{n1}, M_2^{n2}\) and \(M_2^{n3}\). Further, the number of negative 4-cycles in \(M_2^{n1}\), \(M_2^{n2}\) and \(M_2^{n3}\) are 3, 2 and 4, respectively. Thus these three matchings are pairwise non-isomorphic.

It is easy to see that any two matchings of size two whose edges are at different distances are different up to switching isomorphisms. This concludes the proof of theorem.

Having proved this theorem, we propose the following problem.

Problem 2. Can we find the number of non-isomorphic matchings of sizes \(3, \ldots, 2n+1\) in P(2n+1)1, 1) for all \(n \ge 4\)?

In Section 5, we noticed that P(3,1) has no matching (or minimum signature) of size 3, up to switching isomorphism. In Section 6, we noticed that P(5,1) has no matching of sizes 4 and 5, up to switching isomorphism. In Section 7, we noticed that P(7,1) has no matching of sizes 5, 6 and 7, up to switching isomorphism. On the basis of these observations, we propose the following conjecture.

Conjecture 1. Any matching in P(2n+1,1) can be of size at most n+1, where \(n \ge 4\).

Now Problem 2 can be reformulated as follows.

Problem 3. Can we find the number of non-isomorphic matchings of size \(3, 4, 5, \ldots, n+1\) in P(2n+1,1) for all n > 4?

Acknowledgement

We sincerely thank the anonymous referee for useful comments to improve the paper.

References

• [1] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008.
• [2] D. Cartwright and F. Harary, Structural balance: a generalization of Heiders theory, Psychol. Rev. 63 (1956), 277–293.
• [3] R. Frucht, J.E. Graver and M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971), 211–218.

• [4] F. Harary, On the notion of balance of a signed graph. Michigan Math. J. 2 (1953-54), 143– 146.
• [5] R. Naserasr, E. Rollova, and E. Sopena, Homomorphisms of signed graphs, J. Graph Theory, 79 (2015), 178–212.
• [6] V. Sivaraman, Some topics concerning graphs, signed graphs and matroids, PhD Thesis, The Ohio State University, 2012.
• [7] V. Yegnanarayanan, On some aspects of the generalized Petersen graph, Electron. J. Graph Theory Appl. 5 (2) (2017), 163–178.
• [8] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1) (1982), 47–74.
• [9] T. Zaslavsky, Six signed Petersen graphs, and their automorphisms, Discrete Math. 312 (9) (2012), 1558–1583.