The degree sequence on tensor and cartesian products of graphs and their omega index

1.   Introduction and preliminaries

Let $G = (V, E)$ be a finite, simple and undirected graph (molecular graph) with vertex set $|V(G)| = n$ and edge set $|E(G)| = m$. The degree $deg_G(v)$ of a vertex $v$ of $G$ is the number of vertices adjacent to $v$. We denote by $\delta$ and $\Delta$ the minimum and maximum degrees of vertices of $G$, respectively. The degree sequence of $G$, $DS(G) = \{ 1^{(a_1)}, 2^{(a_2)}, 3^{(a_3)}, \ldots, \Delta^{(a_{\Delta})}\}$, is a sequence of degrees of vertices of $G$. We may suggest the book ^[13] for some unmentioned terminology in here.

Let $P_n$, $K_n$, $C_n$, $S_n$, $K_{m, n}$ be path, complete, cycle, star, complete bipartite graphs, respectively. (See Figure 1 for examples of them).

The number of vertices, edges and degree sequences of these well known graph classes are presented in Table 1.

By considering the degree sequence, it has been introduced a new graph invariant

under the name of omega index $\Omega(G)$ (see ^[4]). Clearly $\Omega(G)$ can also be written as $a_3+2a_4+3a_5+\cdots+(\Delta-2)a_{\Delta}-a_1$. This invariant presented direct information on the realizability, number of realizations, connectedness, being acyclic or cyclic, number of components, chords, loops, pendant edges, faces and bridges etc. Besides, the significant difference of $\Omega(G)$ from other graph invariant is that it is an index defined over only a given degree sequence. According to ^[5], omega indices of above indicated well-known graph classes having $n$ vertices are

To have a brief look on the different results of omega index, one may read ^[1,5,6,7].

It is well known that one of the aim to study on graph operations is to produce some new graphs from initial ones. So far, although several studies on different graph operations have been studied (see, for instance, ^[22,27]), it still takes interest because of the aim indicated just in the previous sentence. We refer to ^[12] for a recent survey on graph operations. In fact the tensor and cartesian products are well known operations among the others.

The tensor product of two graphs $G_1$ and $G_2$ is the graph $G_1 \otimes G_2$ with the vertex set $V(G_1 \otimes G_2) = V(G_1) \times V(G_2)$, and any two vertices $(u_1, v_1)$ and $(u_2, v_2)$ are adjacent whenever $u_1$ is adjacent to $u_2$ in $G_1$ and $v_1$ is adjacent to $v_2$ in $G_2$. On the other hand, the cartesian product $G_1 \times G_2$ of two graphs $G_1$ and $G_2$ is the graph with the vertex set $V(G_1) \times V(G_2)$ and any two vertices $(u_1, u_2)$ and $(v_1, v_2)$ are adjacent if and only if $u_1 = v_1 \in V(G_1)$ and $u_2v_2 \in E(G_2)$ or $u_2 = v_2\in V(G_2)$ and $u_1v_1\in E(G_1)$. These two products have been studied to expose some results on graph colorings, decompositions of graphs, graph embeddings and topological indices; see ^{[17,18,19,23,28]}.

This paper is structured as follows. In Section 2, we calculate the degree sequence of tensor products of two graphs (Theorem 2.1) and present the general degree sequence formula of $G_1 \otimes G_2 \otimes \cdots \otimes G_n$ (Theorem 2.2). In the same section, we count the omega invariant of the tensor product of any two graphs (Theorem 2.4) and then state with proofs some consequences (Corollarys 2.6 and 2.7) of this last theorem. The other key point of this section is investigating the algebraic properties (Theorem 2.8) over tensor products via the degree sequence obtained in Theorem 2.1 and Theorem 2.2. In Section 3, by applying same approximation and transferring the similar ideas from the previous section, we obtain important results (Theorems 3.1, 3.3, Corollary 3.5 and Teorem 3.6) over cartesian products of graphs. Finally, in the light of Theorem 3.6, we pay attention to distributive law over tensor and cartesian products (see Theorem 3.7) in which we believe that it would be useful for future studies.

2.   Results on tensor products

We may remind some other studies mentioned in the first sections over tensor products of graphs as in the following: In ^[23], the author obtained a characterization and some properties of $G \otimes K_2$, and in ^[29], the author studied the connectedness of the tensor product of two graphs. Furthermore, in ^[28], it has been obtained the Randic, geometric-arithmetic, first and second Zagreb indices, first and second Zagreb coindices of tensor product of two graphs. Additionally, in ^[2], the authors have been recently introduced four new tensor products of graphs and studied the first and second Zagreb indices and coindices of the resulting graphs and their complements.

Despite so many studies, the tensor product of graphs over degree sequences has not been studied in the literature. In fact degree sequences on graph operations considered only in the paper ^[1] in terms of join and corona products of two simple connected graphs. Therefore the studies and their results in this and next sections are quite original and interesting in the literature.

2.1.   Degree sequence for tensor product of graphs

In this section, we focus on how to obtain the degree sequence of the tensor product of two graphs. We firstly start to find the degree sequence on the case $G_1 \otimes G_2$ and then present a general formula for $DS\left(G_1 \otimes G_2 \otimes \cdots \otimes G_n\right)$.

The proof of the following result will be omitted since it is quite clear by considering the definition of tensor products over graphs and then applying the meaning of degree sequence on these graphs obtained by tensor products.

Theorem 2.1. Suppose that the degree sequences of two connected graphs $G_1$ and $G_2$ are defined by $DS(G_1) = \{ d_1^{a_1}, d_2^{a_2}, \ldots, d_n^{a_n} \}$ and $DS(G_2) = \{ e_1^{b_1}, e_2^{b_2}, \ldots, e_m^{b_m} \}$, respectively. Then

As an example of the above result, let us consider the degree sequences $DS(P_n) = \{ 1^2, 2^{n-2} \}$ and $DS(C_m) = \{ 2^{m} \}$ of $P_n$ and $C_m$, respectively. Thus the degree sequence of the tensor product (see Figure 2 for a simple numerical plotting) is defined by $DS(P_n \otimes C_m) = \{ 2^{2m}, 4^{nm-2m}\}$.

Now, by taking into account the tensor product of $n$ simple connected graphs $G_1, G_2, \ldots, G_n$, where $n\geq 2$, we can state and prove a generalization of Theorem 2.1 as in the following.

Theorem 2.2. Consider $n$ simple connected graphs $G_1, G_2, \ldots, G_n$ with the degree sequence of each $G_i$ is $DS(G_i) = \{ d_{i1}^{a_{i1}}, \ldots, d_{ik}^{a_{ik}} \}$ for $i = 1, 2, \ldots, n$ and $1 \leq k \leq n$. Then the degree sequence $DS(G_1 \otimes G_2 \otimes \cdots \otimes G_n)$ consists of all terms with the form $(d_{\alpha_{s}\alpha_{t}}d_{\beta_{s}\beta_{t}})^{a_{\alpha_{s}\alpha_{t}}a_{\beta_{s}\beta_{t}}}$, where $\alpha_{s}, \beta_{s} = 1, 2, \ldots, n$ and $1\leq \alpha_{t}, \beta_{t}\leq n$.

Proof. For arbitrary the degree sequences $DS(G_1) = \{ d_1^{a_1}, d_2^{a_2}, \ldots, d_n^{a_n} \}$ and $DS(G_2) = \{ e_1^{b_1}, e_2^{b_2}, \ldots, e_m^{b_m} \}$, if we apply Theorem 2.1, then we obtain

Let us take into account an another arbitrary degree sequence $DS(G_3) = \{ x_1^{y_1}, x_2^{y_2}, \ldots, x_t^{y_t} \}$.

Then, by applying a similar approach $n$ times, the form of the element of degree sequences $DS(G_1 \otimes G_2 \otimes \cdots \otimes G_n)$ is $(d_{\alpha_{s}\alpha_{t}}d_{\beta_{s}\beta_{t}})^{a_{\alpha_{s}\alpha_{t}}a_{\beta_{s}\beta_{t}}}$, as required. □

Example 2.3. Assume that $n = 3$ in Theorem 2.2. Then we obtain the degree sequence

for special path and cycle graphs.

2.2.   Omega invariant of tensor product of graphs

The degree sequence of a graph is one of the oldest notions in graph theory. Its applications are legion; they range from computing science to real-world networks such as social contact networks where degree distributions play an important role in the analysis of the network. On the other hand the concept of degree sequence is closely related to computable. It is an open problem to determine that which DSs are realizable and there are several algorithms to determine that. Omega invariant, many properties of its have been obtained ^[5], directly say whether the given degree sequence is realizable (see ^[4]). So this invariant is essential. There are several graph operations used in calculating some chemical invariants of graphs. In ^[1], the authors studied omega invariant of union and corona product of two graphs. This section emphasizes on the omega invariant for the tensor product of two graph.

Firstly we calculate the degree sequence and omega invariant of the tensor product of two special graphs such as path, complete, cycle, star and complete bipartite graphs. (See Table 2).

Now, we give the omega invariant of the tensor product of any two graphs in general.

Theorem 2.4. For any two connected graphs $G_1$ and $G_2$ having $n_1$ vertices, $m_1$ edges and $n_2$ vertices, $m_2$ edges, respectively, the omega index of their tensor product is

Proof. Let us suppose that the degree sequences of these graphs are defined by $DS(G_1) = \{ d_1^{a_1}, d_2^{a_2}, \ldots, \Delta_{1}^{a_{\Delta_{1}}} \}$ and $DS(G_2) = \{ e_1^{b_1}, e_2^{b_2}, \ldots, \Delta_{2}^{b_{\Delta_{2}}} \}$, respectively. So, by the definition of omega invariant given in Eq. (1.1), we obtain

as required. □

Example 2.5. Note that $DS(S_r \otimes K_{s, t}) = \{ s^{(rt-t)}, t^{(rs-s)}, (rs-s)^{t}, (rt-t)^{s}\}$. For example, $DS(S_3 \otimes K_{3, 4}) = \{ 3^{8}, 4^{6}, 6^{4}, 8^{3}\}$ and $\Omega(S_3 \otimes K_{3, 4}) = 1\times8+2\times6+4\times4+6\times3 = 54$. On the other hand $S_3$ and $K_{3, 4}$ have $3$ vertices, $2$ edges and $7$ vertices, $12$ edges, respectively. Accordingly Theorem 2.4, $\Omega(S_3 \otimes K_{3, 4}) = 4\times2\times12-2\times3\times7 = 54$ approving the truth of it.

As a consequence of Theorem 2.4, we can restate the omega invariant of the tensor product of two graphs in terms of the omega index of only one of the graphs.

Corollary 2.6. $\Omega(G_1 \otimes G_2) = 2m_2\Omega(G_1)+4m_2n_1-2n_1n_2.$

Proof. We clearly have

which completes the proof. □

With a similar approach as in the proof of Corollary 2.6, one may obtain the following another consequence of Theorem 2.4.

Corollary 2.7.. $\Omega(G_1 \otimes G_2) = 2m_1\Omega(G_2)+4m_1n_2-2n_1n_2.$

2.3.   Algebraic structure of tensor product of graphs in terms of degree sequence

Havel in 1955 ^[14], Erdos and Gallai in 1960 ^[21], Hakimi in 1962 ^[11], Knuth in 2008 ^[16], Tripathi et al. in 2010 ^[25] proposed a method to decide, whether a sequence of nonnegative integers can be the degree sequence of a simple graph. Sierksma and Hoogeven in 1991 ^[24] compared seven known methods. These studies are about whether a graph can be drawn over the degree sequence. On the other hand, in ^[20], the authors studied some algebraic properties of the join and corona product of two graphs. In this section, we obtain new result regarding algebraic structure of the set of graphs accorging to tensor product operation.

Theorem 2.8. Let $\mathcal{G}$ be the set of all simple connected graphs. Then $\mathcal{G}$ defines an abelian semigroup under the operation of tensor products.

Proof. Let us consider any three graphs $G_1$, $G_2$ and $G_3$ from the set $\mathcal{G}$ having degree sequences

respectively. Now our aim is to show that $\mathcal{G}$ satisfies closure, associativity and commutativity properties under the operation of the tensor product.

First of all, the tensor product of two simple connected graph is another graph, so $\mathcal{G}$ is closed. For associativity,

and

In addition, since the property

holds, the operation $\otimes$ is commutative on $\mathcal{G}$.

Clearly, to identify the identity element (if there exists), we need to find a graph $I$ with the property $G_1 \otimes I = G_1$ and $I \otimes G_1 = G_1$. Assume that the degree sequence of the graph $I$ is defined by $DS(I) = \{ k_1^{t_1}, k_2^{t_2}, ..., k_n^{t_n} \}$. Then

However to be held of this equality, the degree sequence must the form of $DS(I) = \{ 1^1\}$. But there is no such a graph since the degree sequence $\{ 1^1\}$ is not realizable. This implies that the identity element does not exist.

Hence the result. □

3.   Results on Cartesian products

Research into the extension of graphs is essential in applied sciences. So, there are many studies on the Cartesian product which is a graph extension. In ^[3], the authors gave sufficient conditions for the Cartesian product of two graphs to be maximum edge-connected, maximum point-connected, super edge-connected. The researchers in ^[9,10] estimated the Wiener index of the Cartesian product of graphs and in ^[15] the authors calculated the Szeged index of the Cartesian product of graphs. Very recently, in ^[26], the author computed Sombor index over the tensor and Cartesian products of a monogenic semigroup graph. In this section we scrutinize the cartesian products of graphs via its degree sequence.

3.1.   Degree sequence for cartesian product of graphs

Now, we consider degree sequence of the cartesian product of two graphs. Firstly we give the degree sequence of cartesian product of two graphs $G_1, G_2$, then we obtain general formula for degree sequence of $G_1 \times G_2 \times \cdots \times G_n$.

With completely the same reason as mentioned for Theorem 2.1, proof of the following result will be omitted.

Theorem 3.1. Suppose that two connected graphs $G_1$ and $G_2$ have the degree sequences $DS(G_1) = \{ d_1^{a_1}, d_2^{a_2}, \ldots, d_n^{a_n} \}$ and $DS(G_2) = \{ e_1^{b_1}, e_2^{b_2}, \ldots, e_m^{b_m} \}$, respectively. Then

A simple example for Theorem 3.1 can be presented by considering the cartesian product of $C_3$ and $P_4$ (see Figure 3). In fact, since $DS(P_4) = \{ 1^2, 2^2\}$ and $DS(C_3) = \{ 2^3\}$, we obtain $DS(P_4 \times C_3) = \{ (2+1)^{2\times3}, (2+2)^{2\times3} \}$.

In the following, as a generalization of Theorem 3.1, we take into account the cartesian product of $n$ simple connected graphs $G_1, G_2, \cdots, G_n$, where $n\geq 2$.

Theorem 3.2. Let $G_1, G_2, \cdots, G_n$ be $n$ simple connected graphs, and let the degree sequence of each $G_i$ be $DS(G_i) = \{ d_{i1}^{a_{i1}}, \ldots, d_{ik}^{a_{ik}} \}$ for $i = 1, 2, \ldots, n$ and $1 \leq k \leq n$. Then $DS(G_1 \times G_2 \times \cdots \times G_n)$ consists of all terms with the form

where $\alpha_{1}, \beta_{1} = 1, 2, \ldots, n$ and $1\leq \alpha_{2}, \beta_{2}\leq n$.

Proof. We will follow a similar way as in the proof of Theorem 2.2. For the degree sequences

if we apply Theorem 3.1, then we obtain

To achieve the truthfulness of Theorem, it is enough to process n times. Thus, it is clear that the form of the element of degree sequences $DS(G_1 \times G_2 \times \cdots \times G_n)$ is $(d_{\alpha_{1}\alpha_{2}}+d_{\beta_{1}\beta_{2}})^{a_{\alpha_{1}\alpha_{2}}a_{\beta_{1}\beta_{2}}}$. □

With a similar manner and using the same graphs as in Example 2.3, by considering Theorem 3.2, the degree sequence of the cartesian product is

3.2.   Omega invariant of cartesian product of graphs

In this section we give the degree sequence and omega invariant of the cartesian product of two special graphs such as path, complete, cycle, star and complete bipartite graphs (See Table 3).

Now, we give the omega invariant of the cartesian product of any two graphs in general.

Theorem 3.3. Let $G_1$ and $G_2$ be a connected graphs with $n_1$ vertices, $m_1$ edges, and $n_2$ vertices, $m_2$ edges, respectively. Then

Proof. Assume $DS(G_1) = \{ d_1^{a_1}, d_2^{a_2}, \ldots, d_n^{a_n} \}$ and $DS(G_2) = \{ e_1^{b_1}, e_2^{b_2}, \ldots, e_m^{b_m} \}$. By Eq. (1.1), we have

as required. □

Example 3.4. Let us consider $DS(C_r \times S_s) = \{ 3^{(rs-r)}, (s+1)^r \}$. In particular, we choose $C_3$ and $S_4$. We have $DS(C_3 \times S_4) = \{ 3^{9}, 5^{3}\}$ and $\Omega(C_3 \times S_{4}) = (3-2)\times9+(5-2)\times3 = 18$. Indeed, $C_3$ and $S_{4}$ have $3$ vertices, $3$ edges and $4$ vertices, $3$ edges, respectively. Accordingly Theorem 3.3, $\Omega(C_3 \times S_{4}) = 2(3\times4+3\times3-3\times4) = 18$ approving the truth of it.

As a result of Theorem 3.3, we can present the omega invariant of the cartesian product of two graphs by the omega index of graphs.

Corollary 3.5. $\Omega(G_1 \times G_2) = n_2\Omega(G_1)+n_1\Omega(G_2)+2n_1n_2.$

Proof. Suppose that $G_1$ and $G_2$ have the same degree sequences as in the proof of Theorem 2.8. In this case, we get

as required. □

3.3.   Algebraic structure of cartesian product of graphs in terms of degree sequence

With a different manner from above topics (Sections 3.1 and 3.2), in this section, we will state and prove some theoretical results. Firstly we consider algebraic structure of set of connected graphs by using cartesian product operation.

Theorem 3.6. Let $\mathcal{G}$ be the set of all simple connected graphs. Thus $\mathcal{G}$ is an abelian monoid under the cartesian product.

Proof. Consider three graphs from the family $\mathcal{G}$ having degree sequences $DS(G_1) = \{ d_1^{a_1}, d_2^{a_2}, \ldots, d_n^{a_n}\}$, $DS(G_2) = \{ e_1^{b_1}, e_2^{b_2}, \ldots, e_m^{b_m}\}$ and $DS(G_3) = \{ x_1^{y_1}, x_2^{y_2}, \ldots, x_t^{y_t}\}$. Aim is to show that $\mathcal{G}$ is closed, associative, commutative and having an identity element under the cartesian product.

By the definition, since the cartesian product of any two simple connected graphs is another simple connected graph in $\mathcal{G}$, we achieve that $\mathcal{G}$ is closed.

For associativity,

and

So $\mathcal{G}$ is associative. Moreover, for any two graphs $G_1, G_2 \in \mathcal{G}$, a simple calculation shows that $G_1 \times G_2 = G_2 \times G_1$ which implies the commutativity of $\mathcal{G}$.

To the identity element, we need to find a suitable graph $I\in \mathcal{G}$ such that the equality $G \times I = G = I \times G$ holds for every $G \in \mathcal{G}$. Let us reconsider $G_1 \in \mathcal{G}$ and assume that $DS(I) = \{ k_1^{t_1}, k_2^{t_2}, \ldots, k_n^{t_n} \}$.

To have this equality, we must have $DS(I) = \{ 0^1\}$. This implies that $k_1 = k_2 = \cdots = k_n = 0$ and $t_1 = t_2 = \cdots = t_n = 1$ and so this graph is order-zero graph, and the unique graph having no vertices (hence its order is zero). Since we have identity element, the cartesian product operation is monoid. Eventually, we consider the inverse element of the graph $DS(G_1) = \{ d_1^{a_1}, d_2^{a_2}, \ldots, d_n^{a_n}\}$. Let us denote the inverse element with $\{ c_1^{x_1}, c_2^{x_2}, \ldots, c_n^{x_n}\}$. Then we have

In this case, this equation cannot be hold and so there is no inverse element of $\mathcal{G}$. Therefore $\mathcal{G}$ is abelian monoid with the cartesian product operation. □

Now, we consider distributive law related to tensor and cartesian product operation.

Theorem 3.7. Tensor and cartesian products do not provide the distributive law over each other. In other words,

Proof. Let us take $DS(G_1) = \{ d_1^{a_1}, d_2^{a_2}, \ldots, d_n^{a_n}\}, DS(G_2) = \{ e_1^{b_1}, e_2^{b_2}, \ldots, e_m^{b_m}\}, DS(G_3) = \{ x_1^{y_1}, x_2^{y_2}, \ldots, x_t^{y_t}\}$. Now, we handle the first case.

On the other hand, the mixed product $(G_1 \otimes G_2) \times (G_1 \otimes G_3)$ is equal to

So this result is required. Second claim follow after following calculations:

and the mixed product $(G_1 \times G_2) \otimes (G_1 \times G_3)$ is equal to

□

Acknowledgments

This paper is supported by the Natural Science Foundation of Anhui Provincial Department of Education (KJ2021A0650), Graduate offline course graph theory (2021aqnuxskc02).

Conflict of interest

The authors declare that there is no conflict of interest in this paper.