MATEMATIQKI VESNIK

59 (2007), 121–124

UDK 519.175

originalni nauqni rad research paper

SIGNED DEGREE SETS IN SIGNED 3-PARTITE GRAPHS

S. Pirzada and F. A. Dar

Abstract. If each edge of a 3-partite graph is assigned a positive or a negative sign then it is called a signed 3-partite graph. Also, signed degree of a vertex x in a signed 3-partite graph is the number of positive edges incident with x less than the number of negative edges incident with x. The set of distinct signed degrees of the vertices of a signed 3-partite graph is called its signed degree set. In this paper, we prove that every set of n integers is the signed degree set of some connected signed 3-partite graph.

1. Introduction

A signed graph is a graph in which each edge is assigned a positive or a negative sign. The concept of signed graph is given by Harary [3]. Let G be a signed graph with vertex set V = {v_{1}, v_{2}, …, v_{n}}. The signed degree of v_{i} ∈ V is sdeg(v_{i}) = d_{i} = d_{i}^{+} − d_{i}^{−}, where d_{i}^{+}(d_{i}^{−}) is the number of positive (negative) edges incident with v_{i}. A signed degree sequence σ = [d_{1}, d_{2}, …, d_{n}] of a signed graph G is formed by listing the vertex signed degrees in non-increasing order. An integral sequence is s-graphical if it is the signed degree sequence of a signed graph. Also, a non-zero sequence σ = [d_{1}, d_{2}, …, d_{n}] is standard sequence if σ is non-increasing, ∑_{i=1}^{n} d_{i} is even, d_{1} > 0, each |d_{i}| < n, and |d_{1}| ≥ |d_{n}|.

Chartrand et al. [1] obtained the necessary and sufficient conditions for an integral sequence to be s-graphical, which is similar to Hakimi’s result for degree sequences in graphs [2]. Another necessary and sufficient conditions for an integral sequence to be the signed degree sequence of a signed graph is given by Yan et al. [8].

The set of distinct signed degrees of the vertices of a signed graph is called its signed degree set. Pirzada et al. [6] proved that every set of positive(negative) integers is the signed degree set of some connected graph and determined the smallest possible order for such a signed graph.

A signed 3-partite graph is a 3-partite graph in which each edge is assigned a positive or a negative sign. Let G(U, V, W) be a signed 3-partite graph with U = {u_{1}, u_{2}, …, u_{p}}, V = {v_{1}, v_{2}, …, v_{q}} and W = {w_{1}, w_{2}, …, w_{r}}. Then, signed degree of u_{i} is sdeg (u_{i}) = d_{i} = d_{i}^{+} − d_{i}^{−}, where d_{i}^{+}(d_{i}^{−}) is the number of positive(negative) edges incident with u_{i}, signed degree of v_{j} is sdeg (v_{j}) = e_{j} = e_{j}^{+} − e_{j}^{−}, where e_{j}^{+}(e_{j}^{−}) is the number of positive(negative) edges incident with v_{j}, and signed degree of w_{k} is sdeg (w_{k}) = f_{k} = f_{k}^{+} − f_{k}^{−}, where f_{k}^{+}(f_{k}^{−}) is the number of positive(negative) edges incident with w_{k}. Then, the sequences α = [d_{1}, d_{2}, …, d_{p}], β = [e_{1}, e_{2}, …, e_{q}] and γ = [f_{1}, f_{2}, …, f_{r}] are called the signed degree sequences of G(U, V, W). Also, the sequences of integers α, β and γ are said to be standard sequences if α is non-zero and non-increasing, ∑_{i=1}^{p} d_{i} + ∑_{j=1}^{q} e_{j} + ∑_{k=1}^{r} f_{k} is even, d_{1} > 0, each |d_{i}| ≤ q + r, each |e_{j}| ≤ r + p, each |f_{k}| ≤ p + q, |d_{1}| ≥ |e_{j}| and |d_{1}| ≥ |f_{k}| for each j and k.

AMS Subject Classification: 05C22

Keywords and phrases: Signed graph, signed tripartite graph, signed degree, signed set.

The following result is given by Pirzada et al. [5].

Theorem 1.1. Let α = [d_{1}, d_{2}, …, d_{p}], β = [e_{1}, e_{2}, …, e_{q}] and γ = [f_{1}, f_{2}, …, f_{r}] be standard sequences. Then, α, β and γ are the signed degree sequences of a signed 3-partite graph if and only if there exists integers g and h with d_{1} = g − h and 0 ≤ h ≤ \frac{q+r−d_{1}}{2} such that α′, β′ and γ′ are the signed degree sequences of a signed 3-partite graph, where α′ is obtained from α by deleting d_{1} and β′ and γ′ are obtained from β and γ by reducing g greatest entries of β and γ by 1 each and adding h least entries of β and γ by 1 each.

The characterization of signed degree sequences in signed bipartite graphs can be found in [7]. That every set of integers is the signed degree set of some connected signed bipartite graph is proved in [4].

For any two sets X and Y, we denote by X ⊕ Y to mean that each vertex of X is joined to every vertex of Y by a positive edge.

2. Main Results

A signed 3-partite graph G(U, V, W) is said to be connected if each vertex of one partite set is connected to every vertex of other partite sets. The set S of distinct signed degrees of the vertices of a signed 3-partite graph G(U, V, W) is called its signed degree set.

First, we obtain the following result which shows that every set of positive integers is a signed degree set of some connected signed 3-partite graph.

Theorem 2.1. Let d_{1}, d_{2}, …, d_{n} be positive integers. Then, there exists a connected signed 3-partite graph with signed degree set S = {s_{i}|i = 1, 2, …, n}, where s_{i} = ∑_{j=1}^{i} d_{j}.

Proof. If n = 1, d_{1} = 1 then a signed 3-partite graph G(U, V, W) with U = {u_{1}, u_{2}}, V = {v_{1}, v_{2}, v_{3}}, W = {w_{1}} and in which u_{1}v_{1}, u_{2}v_{2}, u_{2}v_{3}, v_{1}w_{1} are positive edges and u_{2}v_{1} is negative edge has signed degree set S = {d_{1}}.

Also, if n = 1, d_{1} > 0, then a signed 3-partite graph G(U, V, W) with |U| = 1, |V | = d_{1} − 1, |W | = d_{1}, U ⊕ W and V ⊕ W has signed degree set S = {d_{1}}.

Now, assume that n ≥ 2. Construct a signed 3-partite graph G(U, V, W) as follows.

Let U = X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{n−1} ∪ X_{n}, V = Y_{1} ∪ Y_{2} ∪ ⋯ ∪ Y_{n−1}, W = Z_{1} ∪ Z_{2} ∪ Z′_{2} ∪ ⋯ ∪ Z_{n−1} ∪ Z′_{n−1} ∪ Z_{n} ∪ Z′_{n}, with X_{i} ∩ X_{j} = ϕ, Y_{i} ∩ Y_{j} = ϕ, Z_{i} ∩ Z_{j} = ϕ, Z_{i} ∩ Z′_{j} = ϕ, Z′_{i} ∩ Z′_{i} = ϕ (i ≠ j), |X_{i}| = |Z_{i}| = d_{i} for all i, 1 ≤ i ≤ n, |Y_{i}| = |Z′_{i+1}| = d_{1} +d_{2} +⋯+d_{i} for all i, 1 ≤ i ≤ n−1, X_{i} ⊕Z_{j} whenever i ≥ j, Y_{i} ⊕Z_{i+1} for all i, 1 ≤ i ≤ n − 1, Y_{i} ⊕ Z′_{i+1} for all i, 1 ≤ i ≤ n − 1. Then, the signed degrees of the vertices of G(U, V, W) are as follows.

For 1 ≤ i ≤ n, sdeg(x_{i}) = ∑_{j=1}^{i} |Z_{j}| = ∑_{j=1}^{i} d_{j} = d_{1} + d_{2} + ⋯ + d_{i}, for all x_{i} ∈ X_{i}; for 1 ≤ i ≤ n − 1, sdeg(y_{i}) = |Z_{i+1}| + |Z′_{i+1}| = d_{i+1} + d_{1} + d_{2} + ⋯ + d_{i} = d_{1} + d_{2} + ⋯ + d_{i} + d_{i+1} for all y_{i} ∈ Y_{i}; for 1 ≤ i ≤ n, sdeg(z_{i}) = (∑_{j=i1}^{n} |X_{j}|) + |Y_{i−1}| = ∑_{j=1}^{n} d_{j} + d_{1} + d_{2} + ⋯ + d_{i−1} = d_{1} + d_{2} + ⋯ + d_{n} for all z_{i} ∈ Z_{i}; and for 2 ≤ i ≤ n, sdeg(z′_{i}) = |Y_{i−1}| = d_{1} + d_{2} + ⋯ + d_{i−1}, for all z′_{i} ∈ Z′_{i}.

Therefore, signed degree set of G(U, V, W) is S. Clearly, all the signed 3-partite graphs constructed above are conected. Hence, the result.

The next result follows from Theorem 2.1 by interchanging positive edges with negative edges.

Corolarry 2.1. Every set of negative integers is a signed degree set of some connected signed 3-partite graph.

Now we have the following result.

Theorem 2.2 Every set of integers is a signed degree set of some connected signed 3-partite graph.

Proof. If S is a set of integers, then we have the following cases.

(i) S is a set of positive(negative) integers. Then, by Theorem 2.1(Corollary 2.1), the result follows.

(ii) S = {0}. Then, a signed 3-partite graph G(U, V, W) with U = {u_{1}}, V = {v_{1}, v_{2}}, W = {w_{1}} and in which u_{1}v_{1}, v_{2}w_{1} are positive edges and u_{1}v_{2}, v_{1}w_{1} are negative edges has signed degree set S.

(iii) S is a set of non-negative ( non-positive ) integers. Let S = S_{1} ∪ {0}, where S_{1} is a set of negative (positive) integers. Then, by Theorem 2.1(Corollary 2.1), there is a connected signed 3-partite graph G_{1}(U_{1}, V_{1}, W_{1}) with signed degree set S_{1}. Construct a new signed 3-partite graph G(U, V, W) as follows.

Let U = U_{1} ∪{u}, V = V_{1} ∪{v}, W = W_{1} ∪{w}, with U_{1} ∩{u} = ϕ, V_{1} ∩{v} = ϕ, W_{1} ∩ {w} = ϕ and let uv, v_{1}w be positive edges and uv_{1}, vw be negative edges, where v_{1} ∈ V_{1}. Then, G(U, V, W) has signed degree set S. Also, note that addition of such edges do not effect the signed degrees of the vertices of G_{1}(U_{1}, V_{1}, W_{1}), and the vertices u, v, w have signed degrees zero each.

(iv) S is a set of non-zero integers. Let S = S_{1} ∪ S_{2}, where S_{1} and S_{2} are sets of positive and negative integers respectively. Then, by Theorem 2.1 and Corollary 2.1, there are connected signed 3-partite graphs G_{1}(U_{1}, V_{1}, W_{1}) and G_{2}(U_{2}, V_{2}, W_{2}) with S_{1} and S_{2} respectively.

Construct a new signed 3-partite graph G(U, V, W) as follows.

Let U = U_{1} ∪ U_{2,}V = V_{1} ∪ V_{2}, W = W_{1} ∪ W_{2} with U_{1} ∩ U_{2} = ϕ, V_{1} ∩ V_{2} = ϕ, W_{1} ∩ W_{2} = ϕ and let u_{1}v_{2}, u_{2}w_{1}, v_{1}w_{2} be positive edges and u_{1}w_{2}, u_{2}v_{1}, w_{1}v_{2} be negative edges where u_{i} ∈ U_{i}, v_{i} ∈ V_{i}, w_{i} ∈ W. Then, signed degree set of G(U, V, W) is S. Clearly addition of such edges do not effect the signed degrees of the vertices of G_{1}(U_{1}, V_{1}, W_{1}) and G_{2}(U_{2}, V_{2}, W_{2}).

(v) S is a set of all integers. Let S = S_{1} ∪ S_{2} ∪ {0}, where S_{1} and S_{2} are sets of positive and negative integers respectively. Then, by Theorem 2.1 and Corollary 2.1, there exist connected signed 3-partite graphs G_{1}(U_{1}, V_{1}, W_{1}) and G_{2}(U_{2}, V_{2}, W_{2}) with signed degree sets S_{1} and S_{2} respectively. Construct a new signed 3-partite graph G(U, V, W) as follows.

U = U_{1} ∪ U_{2} ∪ {u}, V = V_{1} ∪ V_{2}, W = W_{1} ∪ W_{2} with U_{1} ∩ U_{2} = ϕ, U_{i} ∩ {u} = ϕ, V_{1} ∩ V_{2} = ϕ, W_{1} ∩ W_{2} = ϕ and let uv_{1}, u_{2}w_{1} be positive edges, where u_{2} ∈ U_{2}, v_{1} ∈ V_{1}, w_{1} ∈ W_{1}. Then, signed degree set of G(U, V, W) is S. We note that addition of such edges do not effect the signed degrees of the vertices of G_{1}(U_{1}, V_{1}, W_{1}) and G_{2}(U_{2}, V_{2}, W_{2}), and the signed degree of u is zero. Clearly, by construction, all the above signed 3-partite graphs are connected. This proves the result.

REFERENCES

[1] G. Chartrand, H. Gavlas, F. Harary and M. Schultz, On signed degrees in signed graphs, Czech. Math. J. 44 (1994) 677–690.

[2] S. L. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, SIAM J. Appl. Math. 10 (1962) 496–506.

[3] F. Harary, On the notion of balance in a signed graph, Michigan Math. J. 2 (1953) 143–146.

[4] S. Pirzada, T. A. Naikoo and F. A. Dar, A note on signed degree sets in signed bipartite graphs, Applicab;e Analysis and Discrete Mathematics, to appear.

[5] S. Pirzada, T. A. Naikoo and F. A. Dar, Signed degree sequences of signed 3-partite graphs, J.Korean Society of Industrial and Applied Mathematics (2007), to appear.

[6] S. Pirzada, T. A. Naikoo and F. A. Dar, Signed degree sets in signed graphs, Czech. Math. J., 57, 3 (2007), 843–848.

[7] S. Pirzada, T. A. Naikoo and F. A. Dar, Signed degree sequences of signed bipartite graphs, to appear.

[8] J. H. Yan, K. W. Lih, D. Kuo and G. J. Chang, Signed degree sequences of signed graphs, J. Graph Theory 26 (1997) 111–117.

(received 13.02.2007, in revised form 10.07.2007)

Department of Mathematics, University of Kashmir, India

E-mail: sdpirzada@yahoo.co.in, sfarooqdar@yahoo.co.in