����������� ������ 47 (1995), 57–60

UDC 519.175

���������� ������ ��� research paper

INDEX OF IMPRIMITIVITY OF THE NON-COMPLETE EXTENDED p-SUM OF DIGRAPHS

Milenko V. Petrić

Abstract. We prove that all components of the non-complete extended p-sum (NEPS) of strongly connected digraphs have the same index of imprimitivity. This index is given in dependence of the indices of imprimitivity of digraphs on which the operation is performed.

Let h(G) = h be the greatest common divisor of the lengths of all the cycles in a digraph G. The digraph G is called primitive if it is strongly connected and h = 1 and imprimitive if it is strongly connected and h > 1. In the second case h is called the index of imprimitivity (h is the index of imprimitivity of the adjacency matrix of the digraph G as well ([1, p. 183])). Non-connected digraph is primitive if all its components are primitive.

The presence of loops in a strongly connected digraph results in that the digraph is primitive, while the multiple arcs do not affect its index of imprimitivity at all. In view of that the multiple arcs and loops in the digraphs throughout this paper are allowed.

Definition 1. Let B ⊆ {0, 1}^{n} \ {(0, 0,…, 0)}. The NEPS with basis B of digraphs G_{1}, G_{2}, …, G_{n} is the digraph G whose vertex set is the Cartesian product of the vertex sets of digraphs G_{1}, G_{2}, …, G_{n}. For two vertices, say u = (u_{1}, u_{2},…, u_{n}) and v = (v_{1}, v_{2},…, v_{n}), of G construct all the possible arc selections of the following type. For each n-tuple (β_{1}, β_{2},…, β_{n}) ∈ B, such that u_{k} = v_{k} holds whenever β_{k} = 0, select an arc going from u_{i} to v_{i} in G_{i} whenever β_{i} = 1. The number of arcs going from u to v in G is equal to the number of such selections.

If B consists of all the possible n-tuples (of course, without the n-tuple (0, 0,…, 0)) the operation is called the strong product. The p-sum is obtained if B consists of all the possible n-tuples with exactly p 1’s. If p = n, the p−sum is called the product.

AMS Subject Classification: Primary 05C40, Secondary 05C20.

Keywords and phrases: Index of imprimitivity, product of digraphs.

It is shown in [4] that all components, of the product of strongly connected digraphs G_{1}, G_{2}, …, G_{n}, have the same index of imprimitivity, given by^{1} h = l. c. m.(h_{1}, h_{2},…, h_{n}) and the sum of these digraphs have the index of imprimitivity given by^{2} h = g. c. d.(h_{1}, h_{2},…, h_{n}), where h(G_{j}) = h_{j} is the index of imprimitivity of G_{j}. It is shown in [5] and [6] that all components of the NEPS of undirected, connected graphs are primitive or all are bipartite. Necessary and sufficient conditions for primitivity and bipartiteness are given too. Here we show that all components of a NEPS, of strongly connected digraphs, have the same index of imprimitivity and determine it in dependence of the indices of imprimitivity of digraphs on which the operation is performed.

We shall consider the NEPS basis B of which has property (D): for each j ∈ {1, 2,…, n} there exists in B at least one n-tuple (β_{1}, β_{2},…, β_{n}) with β_{j} = 1. This condition implies that the NEPS, effectively, depends on each G_{j}.

The index of a strongly connected digraph is its greatest real eigenvalue. A maximal eigenvalue of a digraph G is an eigenvalue of G modulus of which is equal to its index. As is well known [1] the index of imprimitivity of a strongly connected digraph is equal to the number of its maximal eigenvalues.

The following theorem from [3] has essential role in further considerations.

Theorem 1. If, for i = 1, 2,…, n, λ_{ij_{i}}, j_{i} = 1, 2, …, p_{i}, is the spectrum of a digraph G_{i} (p_{i} being its number of vertices), then the spectrum of NEPS with the basis B of digraphs G_{1}, G_{2}, …, G_{n}, consists of all possible values Λ_{j_{1},j_{2},...,j_{n}}, where

Λ_{j_{1},j_{2},...,j_{n}} = ∑_{β∈B} λ_{1j_{1}}^{β_{1}} · λ_{2j_{2}}^{β_{2}} ⋯ λ_{nj_{n}}^{β_{n}}, (j_{i} = 1, 2,…, p_{i}; i = 1, 2,…, n).

The eigenvector x_{j_{1},j_{2},...,j_{n}} = x_{1j_{1}} ⊗ x_{2j_{2}} ⊗ ⋯ ⊗ x_{nj_{n}} belongs to the eigenvalue Λ_{j_{1},j_{2},...,j_{n}}, where x_{ij_{i}} is an eigenvector belonging to the eigenvalue λ_{ij_{i}} of G_{i}.

Here β = (β_{1}, β_{2},…, β_{n}) and ⊗ denotes the Kronecker product of matrices.

Theorem 2. Let G_{1}, G_{2}, …, G_{n} be strongly connected digraphs each containing at least two vertices out of which G_{i_{1}}, G_{i_{2}}, …, G_{i_{s}}, ({i_{1}, i_{2},…, i_{s}} ⊂ {1, 2,…, n}) are imprimitive with the imprimitivity indices h_{i_{1}}, h_{i_{2}}, …, h_{i_{s}}, respectively. All components of a NEPS, with basis B satisfying condition (D), of digraphs G_{1}, G_{2}, …, G_{n} are primitive or imprimitive with the same index of imprimitivity. This index of imprimitivity is equal to the greatest natural number h, for which there exist integers ξ_{i_{1}}, ξ_{i_{2}}, …, ξ_{i_{s}}, 0 ≤ ξ_{i_{k}} ≤ h_{i_{k}} − 1, such that for each β ∈ B the expression

\frac{ξ_{i_{1}}}{h_{i_{1}}} β_{i_{1}} + \frac{ξ_{i_{2}}}{h_{i_{2}}} β_{i_{2}} + ⋯ + \frac{ξ_{i_{s}}}{h_{i_{s}}} β_{i_{s}} − \frac{1}{h}

is an integer.

1l.c.m. denotes the least common multiple

2g.c.d. denotes the greatest common divisor

Index of imprimitivity of the non-complete extended p-sum of digraphs 59

Proof. First, we note that all components of a NEPS of strongly connected digraphs are its strong components, too [3]. Thus, from theorem of Frobenius ([2], p. 18), it follows that it is sufficient to prove that the multiplicity of each maximal eigenvalue of the NEPS is equal to the number of components of the NEPS. Then the index of imprimitivity is equal to the number of its distinct maximal eigenvalues.

By Theorem 1 the maximal eigenvalue of NEPS can be obtained only from those eigenvalues of the digraphs G_{j} (j = 1, 2,…, n) which have a modulus equal to its index r_{j}. All these eigenvalues of G_{j} can be written in the form r_{j} exp(ℓ_{j} \frac{2π}{h_{j}} i), 0 ≤ ℓ_{j} ≤ h_{j} − 1, i^{2} = −1 (theorem of Frobenius).

Thus, a maximal eigenvalue of the NEPS is obtainable from

Λ_{j_{1},j_{2},...,j_{n}} = ∑_{β∈B} r_{1}^{β_{1}}r_{2}^{β_{2}} ⋯ r_{n}^{β_{n}} exp ((\frac{j_{1}}{h_{1}} β_{1} + \frac{j_{2}}{h_{2}} β_{2} + ⋯ + \frac{j_{n}}{h_{n}} β_{n}) 2πi) , (1)

where 0 ≤ j_{k} ≤ h_{k} − 1.

Let h be the index of imprimitivity of any component of the NEPS. That means that there exist integers ξ_{1}, ξ_{2}, …, ξ_{n}, 0 ≤ ξ_{j} ≤ h_{j} − 1, such that

\frac{ξ_{i_{1}}}{h_{i_{1}}} β_{i_{1}} + \frac{ξ_{i_{2}}}{h_{i_{2}}} β_{i_{2}} + ⋯ + \frac{ξ_{i_{s}}}{h_{i_{s}}} β_{i_{s}} − \frac{1}{h} = y_{β}, y_{β} ∈ Z, β ∈ B,  (2)

holds. Then, from (1) we get h − 1 maximal eigenvalues of the NEPS. They can be obtained from (1) with j_{1}, j_{2}, …, j_{n} obtained from (2) by multiplying (2) by s = 1, 2,…, h − 1, respectively, and taking j_{k} = s · ξ_{k} (mod h_{k}). Each component of the NEPS is corresponded to a solution [3] in integers x_{k}, y_{β} (0 ≤ x_{k} ≤ h_{k} − 1) of the system of equations

\frac{x_{i_{1}}}{h_{i_{1}}} β_{i_{1}} + \frac{x_{i_{2}}}{h_{i_{2}}} β_{i_{2}} + ⋯ + \frac{x_{i_{s}}}{h_{i_{s}}} β_{i_{s}} = y_{β}, y_{β} ∈ Z, β ∈ B.  (3)

In fact, each solution of (3) provides by (1), an eigenvalue, equal to the index. Further, to each such solution, h − 1 new systems of numbers satisfying (2) are corresponded. These ones can be obtained by sums x_{k} + ξ_{k} (mod h_{k}), where x_{k} is a solution of (3) and ξ_{k} is a solution of (2) (k = 1, 2,…, n). These systems of numbers when put into (1) yield h − 1 maximal eigenvalues. It can easily be shown that all solutions of (2), obtained in this way, are different. In such a way we get all systems of numbers satisfying (2) (i.e., all maximal eigenvalues of the NEPS). If, on the contrary, there exists a system of numbers ξ′_{1}, ξ′_{2},…, ξ′_{n} satisfying (2) which is obtained neither from (2) by multiplying by 1, 2,…, h − 1 nor as sums x_{k} +ξ_{k} (mod h_{k}), where x_{k} and ξ_{k}, (k = 1, 2,…, n), are the solutions of systems of equations (3) and (2), respectively, then ξ′_{k} − ξ_{k}, (k = 1, 2,…, n), is a new solution of (3), which is a contradiction. That means that all components of the NEPS have the same index of imprimitivity given by h.

This completes the proof of the theorem.

According to this theorem it follows that the index of imprimitivity of the NEPS, under above conditions, is equal to the quotient of the number of maximal eigenvalues of the NEPS and the number of components (i.e., multiplicity of the index) of the NEPS. It is shown in [3] and [6] that the number of components and the number of maximal eigenvalues of the NEPS is given by the number of solutions of the systems of equations (4) and (5), respectively. Thus, we have proved the following theorem.

Theorem 3. Let G_{1}, G_{2}, …, G_{n} be strongly connected digraphs each containing at least two vertices out of which G_{i_{1}}, G_{i_{2}}, …, G_{i_{s}} ({i_{1}, i_{2},…, i_{s}} ⊂ {1, 2,…, n}) are imprimitive with the imprimitivity indices h_{i_{1}}, h_{i_{2}}, …, h_{i_{s}}, respectively. Let K be the number of solutions in integers x_{i}, y_{β} (0 ≤ x_{i} ≤ h_{i} − 1) of the system of equations:

\frac{x_{i_{1}}}{h_{i_{1}}} β_{i_{1}} + \frac{x_{i_{2}}}{h_{i_{2}}} β_{i_{2}} + ⋯ + \frac{x_{i_{s}}}{h_{i_{s}}} β_{i_{s}} = y_{β}, β ∈ B,  (4)

and let N be the number of solutions in integers x_{i}, y_{β} (0 ≤ x_{i} ≤ h_{i} − 1) of the system of equations (α ∈ B):

\frac{x_{i_{1}}}{h_{i_{1}}} (β_{i_{1}} − α_{i_{1}}) + \frac{x_{i_{2}}}{h_{i_{2}}} (β_{i_{2}} − α_{i_{2}}) + ⋯ + \frac{x_{i_{s}}}{h_{i_{s}}} (β_{i_{s}} − α_{i_{s}}) = y_{β}, β ∈ B, β ≠ α. (5)

Then the index of imprimitivity of the NEPS with basis B (|B| ≥ 2) satisfying condition (D), of digraphs G_{1}, G_{2}, …, G_{n} is given by h = N/K.

In the case when the basis of the NEPS contains only one element this operation is reduced to ordinary product of digraphs and solution of the problem is given in [4].

Acknowledgement. Finally I wish to thank the referee for carefully reading the paper and for giving helpful suggestions.

REFERENCES

[1] D. M. Cvetković, Combinatorial Matrix Theory (in Serbian), Naučna knjiga, Beograd 1980.

[2] D. M. Cvetković, M. Doob, H. Sachs, Spectra of Graphs-Theory and Applications, third edition, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.

[3] D .M. Cvetković, M. V. Petrić, Connectedness of the non-complete extended p-sum of graphs, Univ. u Novom Sadu Zb. Rad. Prirod.-Mat. Fak. Ser. Mat. 13 (1983), 345–352.

[4] M. H. McAndrew, On the product of directed graphs, Proc. Amer. Math. Soc. 14 (1963), 600– 606.

[5] M .V. Petrić, Bipartiteness of certain graph products, Univ u Novom Sadu Zb. Rad. Prirod.- Mat. Fak. Ser. Mat. (to appear)

[6] M. V. Petrić, Primitivity of the generalized direct product of digraphs, Publ. Inst. Math (Beograd), to appear.

(received 07.03.1995., in revised form 01.11.1995.)

Advanced Technical School, Školska 1, 21000 Novi Sad, POB 316, Yugoslavia