The Euler \(\varphi\)-function, which is also known as the indicator function or totient function where the symbol \(\varphi(n)\) is introduced by Gauss, which counts the positive integers up to a given integer \(n\) that are relatively prime to \(n\). If \(n\) is a prime \(p\), then \(\varphi \left(p\right)=p-1\) and generally,for any positive integer \(k\), \(\varphi\left({p}^k\right)=p^k-p^{k-1}\) . Then, we have that for any positive integer \(n\) \(\varphi\left(n\right)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\dots \left(1-\frac{1}{p_t}\right)\) where \(n={p_1}^{a_1}{p_2}^{a_2}\dots {p_t}^{a_t}\ \) [1,2].
The Möbius function [1] is denoted by \(\mu(n)\) and defined as \[\mu(n) = \begin{cases} \,\,\,1, & \text{if} \ n=1, \\ \left(-1\right)^t, & \text{if} \ n\ \text{is a product of distinct primes}, \\ \ \ 0, & \text{otherwise}. \end{cases}\]
A function \(f\) is multiplicative if for all positive integers \(m,n\) such that \(m,n\) are co-primes, then \(f\left(mn\right)=f(m)f(n)\). Both the Euler \(\varphi-\) function and the Möbius function are proved to be multiplicative [1].
The divisor sum \(T\)-function in number theory was first studied by Ramanujan, which is a number of crucial congruences and identities were given by him; these are preserved separately in the article Ramanujan’s lost notebook in [3]. The sum of the divisor \(\sigma_k\)-function is a related function to the divisor function, denoted by \(\sigma_k(n)\) which is counting the sum of positive divisors of \(n\) to the power \(k\), which was studied in [1]. If \(n\) is a prime \(p\), then \(\sigma_k (p)=p^k+1\) and generally, \(\sigma_k (p^a )=\frac{p^{(a+1)k}-1}{p^k-1}\) for a positive integer \(a\). Then we have that, for any positive integer \(n\), \(\sigma_k (n)=\sum\limits_{d|n}d^k = \prod\limits_{i=1}^{t}\frac{p^{(a_i+1)k}-1}{p_i^k-1}\), where \(n=p_1^{a_1}p_2^{a_2}\dots p_t^{a_t}\). The sum of the divisor \(\sigma_k\)-function is multiplicative [1]. The generalized Euler’s \(\Phi\)-function of a graph which is the summation of the Euler’s \(\phi\)-function of the degree of the vertices of a graph are defined by Salih and Ibrahim in [4] which is denoted by \(\Phi(G)\) and it determines the general form of generalized Euler’s \(\Phi\)-function of some standard graphs. Also, in [5] Salih and Ibrahim defined the generalized divisor sum \(T_k\)-function of a graph which is the summation of \(\sigma_k\)-function of the degree of vertices of a graph and it is denoted by \(T_k(G)\) and it is determined the general form of \(T_k\)-function of some standard graphs.
Wiener in [6] defined the weight \(w(e)\) of an edge \(e={u,v}\) as \(w(e)=deg(u)+ deg(v)\) and the edge degree weight sum \(w(G)\) of \(G\) relative to this edge weighting is \(w(G)=\sum\limits_{e\in E(G)}w(e)\). Wiener also defined the weighted of a graph \(G\) which is the sum of square of the degree of vertex, thus \[w(G)=\sum_{e\in E(G)}w(e)=\sum_{u\in V(G)}(deg(u))^2.\] For all other standard terminology and notations, see [7,8].
It is attempts, in this paper, to utilize two number theory functions called the Euler’s \(\varphi\)-function and the divisor sum \(\sigma_k\)-function into graph theory. Suppose that \(G\) is a simple connected undirected graph. The generalized Euler \(\Phi_w\) and the divisor sum \(T_{k_w}\) functions of any graph are defined. It is proved that for all \(e \in E(G), w(e)\ge 1\) such that \(w(e)\) with at most \(8\) distinct prime factors, we have that \(\Phi_w(G)>\frac{1}{6}\sum\limits_{e \in E(G)}{w(e)}\). A relationship between the Möbius function and the Euler’s \(\varphi-\) function is also shown.
This section shows that for all \(e\in (G)\), \(w(e)\ge 1\) such that \(w(e)\) with at most \(8\) distinct prime factors, we have obtained that \(\Phi(W(G))>\frac{1}{6}\sum\limits_{u,v\in V(G)}d(u,v)\). A relationship between Möbius function and Euler’s \(\varphi-\) function is also shown. Also, some new results of finding generalized divisor \(T_k\)-function of edge weighted graph are given as well as giving a relationship between Euler’s \(\varphi\)-function and generalized divisor sum \(T_k\)– function of edge weighted graphs, where \(k=1\).
Definition 1. Let \(G\) be a simple connected undirected graph. The generalized \(\Phi_w\)-function is defined as the sum of Euler’s \(\phi\)-function of weight of edges \(e\) of a graph \(G\) which is denoted by \(\Phi_w (G)\). That ia \(\Phi_w(G)=\sum\limits_{e\in E(G)}\varphi(w(e))\) or \(\Phi_w(G)=\sum\limits_{i=1}^{q}\varphi(w(e_i))\) where \(q\) is size of a graph \(G\).
Definition 2. Let \(G\) be a simple connected graph. The generalized \(T_{k_w}\)-function is defined as the sum of divisor \(\sigma_k\)-function of weighted edges \(e\) of a graph \(G\) which is denoted by \(T_{k_w} (G)\). That is \(T_{k_w}(G)=\sum\limits_{e\in E(G)}\sigma_k(w(e))\).
Theorem 1. If \(G\) is regular graph of degree \(r\), then \(w(e)=2r\) for each \(e={u,v}\) in \(E(G)\) and we have \[\Phi_w (G)=q\varphi(2r)=\begin{cases} 2q\varphi(r),& \text{if}\ r\ \text{is even},\\ q\varphi(r),& \text{if}\ r\ \text{is odd}. \end{cases}\]
Proof. By Definition 1, \(w(e)=2r\) and we have \[\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))=\sum_{u,v\in V(G)}\varphi(deg(u)+deg(v))=\sum_{u\in V(G)}\varphi(2deg(u))\,.\] Since \(G\) is regular, so \(deg(u)=deg(v)=r\), hence \[\Phi_w(G)=\sum_{u\in V(G)}\varphi(2deg(u))=\sum_{deg(u)=deg(v)=r}\varphi(2r)=q\varphi(2r)=\begin{cases} 2q\varphi(r),& \text{if}\ r\ \text{is even},\\ q\varphi(r),& \text{if}\ r\ \text{is odd}. \end{cases}\] ◻
Theorem 2. If \(G\) is regular graph of degree \(r\), for each \(e={u, v}\) in \(E(G)\), then we have \[T_{k_w}(G)=q\sigma_k (2r).\]
Proof. Similar to the proof of Theorem 1 and by using Definition 2, the result follows. ◻
Theorem 3. For any graph \(G\) with \(deg(u) \ge 2\) and \(p \ge q\), we have \[\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))=\sum_{u\in V(G)}\varphi((deg(u))^2).\]
Proof. Since \(w(e)=deg(u)+deg(v)\) for edge \(e ={u,v}\) in \(E(G)\). Thus, each vertex \(u\) in \(V(G)\) contributes the value \(deg(u)\) to the weights of \(deg(u)\) edges and thus contributes \(deg(u)\) to \(w(e)\). Hence, \[\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))=\sum_{u\in V(G)}\varphi((deg(u))^2).\] ◻
Theorem 4. For any graph \(G\) with \(deg(u)\ge 2\) and \(p\ge q\), we have \[T_{k_w}(G)=\sum_{e\in E(G)}\sigma_k(w(e))=\sum_{u\in V(G)}\sigma_k((deg(u))^2).\]
Proof. Similar to the proof of Theorem 3 and by using Definition 2, the result follows. ◻
Lemma 1. Let \(G\) be a connected graph, then for all \(u,v\in V(G)\), we have \[\sum_{\substack{d|w(e)\\ e\in E(G)}} \Phi_d(e)=\sum_{e\in E(G)}\sum_{d|w(e)} \varphi(d)=\sum_{e\in E(G)}w(e),\] where the divisor of the weight of edges is denoted by \(d\) in a graph \(G\).
Proof. Let, for \(e\in E(G)\), \(F(w(e))=\varphi(d_1)+\varphi(d_2)+\dots+\varphi(d_t)\), where \(d_t\) is any divisor of \((w(e))\) for \(i=1,2,\dots,t\) and \(w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}\). Then, with the use of the telescoping series, we have \(F(p^k)=1+(p-1)+(p^2-p)+(p^3-p^2)+\dots+(p^k-p^{k-1})=p^k\), where \((1,p,p^2,p^3,\dots)\) are counted as divisors of \(p^k\). As \(F\) is multiplicative, so \[\begin{aligned} \sum_{ e\in E(G)} F(w(e))&=\sum_{w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}} F\left(p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}\right)\\ &=\sum_{w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}} \left(F\left(p_{1}^{a_1}\right)*F\left(p_{2}^{a_2}\right)*\dots *F\left (p_{t}^{a_t}\right)\right)\\ &=\sum_{w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}} \left(p_{1}^{a_1}*p_{2}^{a_2}*\dots * p_{t}^{a_t}\right)=\sum_{e\in E(G)}w(e)\,. \end{aligned}\] ◻
Lemma 2. For all \(e\in E(G)\) and \(w(e)\ge 1\), we have \[\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))=\sum_{e\in E(G)}\left(w(e)*\prod_{p|w(e)}\left(1-\frac{1}{p}\right)\right),\] where \(w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}.\)
Proof. Let \(e\in E(G)\), \(\left(w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}\right)\ge 1\) and since \(\varphi\) is multiplicative, thus \[\begin{aligned} \Phi_w(G)&=\sum_{e\in E(G)}\varphi(w(e))=\sum_{w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}\varphi\left(p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}\right)\\ &=\sum_{w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}\left(\varphi\left(p_{1}^{a_1}\right)*\varphi\left(p_{2}^{a_2}\right)\dots \varphi\left(p_{t}^{a_t}\right)\right)\\ &=\sum_{w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}\left(\left(p_{1}^{a_1}-p_{1}^{a_1-1}\right)*\left(p_{2}^{a_2}-p_{2}^{a_2-1}\right)*\dots *\left(p_{t}^{a_t}-p_{t}^{a_t-1}\right)\right)\end{aligned}\] \[\begin{aligned} &=\sum_{w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}\left(p_{1}^{a_1}\left(1-\frac{1}{p_1}\right)*p_{2}^{a_2}\left(1-\frac{1}{p_2}\right)*\dots * p_{t}^{a_t}\left(1-\frac{1}{p_t}\right)\right)\\ &=\sum_{w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}\left(\left(p_{1}^{a_1}*p_{2}^{a_2}*\dots * p_{t}^{a_t}\right)\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\left(1-\frac{1}{p_t}\right) \right)\\ &=\sum_{\substack{e\in E(G)\\w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}}\left(w(e)*\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\left(1-\frac{1}{p_t}\right)\right)\\ &=\sum_{e\in E(G)}\left(w(e)*\prod_{p|w(e)}\left(1-\frac{1}{p}\right)\right). \end{aligned}\] ◻
Lemma 3. For all \(e\in E(G)\) and \(w(e)\ge 1\), we have \[\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))=\sum_{e\in E(G)}\left(\sum_{d|w(e)}\left(\mu(d)*\frac{w(e)}{d}\right)\right),\] where \(\mu\) is Möbius function.
Proof. Let \(e\in E(G)\), \(w(e)\ge 1\). Then by using Lemma 2, we have \[\begin{aligned} \Phi(G)&=\sum_{e\in E(G)}\varphi(d(u,v))=\sum_{e\in E(G)}\left(d(u,v)*\prod_{p|d(u,v)}\left(1-\frac{1}{p}\right)\right)\\ &=\sum_{\substack{e\in E(G)\\w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}}\left(d(u,v)*\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\left(1-\frac{1}{p_t}\right)\right)\\ &=\sum_{\substack{e\in E(G)\\w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}}\left(d(u,v)*\left(1-\sum_{i}\frac{1}{p_i}+\sum_{i\neq j}\frac{1}{p_ip_j}+\dots+(-1)^{t}\frac{1}{p_1p_2\dots p_t}\right)\right)\,. \end{aligned}\]
Let \(\left(1-\sum_{i}\frac{1}{p_i}+\sum_{i\neq j}\frac{1}{p_ip_j}+\dots+(-1)^{t}\frac{1}{p_1p_2\dots p_t}\right)=A\), then each term in \(A\) is \(\frac{\pm 1}{d}\), where \(d\) is \(1\) in the leading (first) term or a product of distinct primes. The signs before each term are being alternated by \({\left(-1\right)}^k\) according to the primes \(p'\)s which is precisely done by the Möbius function. Hence, \[\begin{aligned} \Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))&=\sum_{e\in E(G)}\left(w(e)\sum_{d|w(e)} \frac{\mu(d)}{d}\right)=\sum_{e\in E(G)}\left(\sum_{d|w(e)}\mu(d)*\frac{w(e)}{d}\right). \end{aligned}\] ◻
Theorem 5. For all \(e\in E(G)\) and \(w(e)\ge 1\) such that \(w(e)\) with at most \(8\) distinct prime factors, \[\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))>\frac{1}{6}\sum_{e\in E(G)}w(e).\]
Proof. First of all, a result for \(w(e)\) with 8 distinct prime factors will be shown. Let \(w(e)={p_1}^{a_1}{p_2}^{a_2}\dots {p_t}^{a_t}\), then, by using Lemma 2 for the generalized Euler \(\Phi\)-function, we obtain
\[\begin{aligned}\Phi_w(G)&=\sum\limits_{e\in E(G)}\varphi(w(e))\\ &=\sum\limits_{e\in E(G)}\left(w(e)*\prod\limits_{p|w(e)}\left(1-\frac{1}{p}\right)\right)\end{aligned}\] \[\begin{aligned} &=\sum_{\substack{e\in E(G)\\w(e)=p_{1}^{a_1}p_{2}^{a_2}\dots p_{t}^{a_t}}}\left({p_1}^{a_1}{p_2}^{a_2}\dots {p_t}^{a_t}*\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\left(1-\frac{1}{p_t}\right)\right)\,. \end{aligned}\]
As of the \(8\) distinct prime factors of \(p_1,p_2,p_3,p_4,p_5,p_6,p_7,p_8\), we realize that \(p_1\ge 2,p_2\ge 3,p_3\ge 5,p_4\ge 7,p_5\ge 11,p_6\ge 13,p_7\ge 17,p_8\ge 19,\) since the first \(8\) primes are distinct. Thus, \[\label{eq1} \frac{1}{p_1}\le \frac{1}{2},\ \frac{1}{p_2}\le \frac{1}{3},\ \frac{1}{p_3}\le \frac{1}{5},\ \frac{1}{p_4}\le \frac{1}{7},\ \frac{1}{p_5}\le \frac{1}{11}, \frac{1}{p_6}\le \frac{1}{13},\ \frac{1}{p_7}\le \frac{1}{17},\ \frac{1}{p_8}\le \frac{1}{19}\,, \tag{1}\] so \(\left(1-\frac{1}{2}\right)\ge \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\dots \left(1-\frac{1}{19}\right)\ge \left(1-\frac{1}{19}\right)\). We can now substitute (1) into the equation \(\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))\), we obtain that \[\begin{aligned} \Phi_w(G)&=\sum_{e\in E(G)}\varphi(w(e))\ge \sum_{e\in E(G)}(w(e))*\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\dots \left(1-\frac{1}{19}\right)\\ &=\sum_{e\in E(G)}(w(e))*\left(\frac{1}{2}*\frac{2}{3}*\frac{4}{5}*\frac{6}{7}*\frac{10}{11}*\frac{12}{13}*\frac{16}{17}*\frac{18}{19}\right)\\ &=\frac{1658880}{9699690}\sum_{e\in E(G)}(w(e))=0.171*\sum_{e\in E(G)}(w(e)). \end{aligned}\] However, \[\frac{1}{6}\sum_{e\in E(G)}(w(e))\approx 0.167*\sum_{e\in E(G)}(w(e)).\] This means that \[\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))>\frac{1}{6}\sum_{e\in E(G)}w(e).\]
Each of the following factors \(\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\dots \left(1-\frac{1}{p_8}\right)\) is less than one because two is the smallest prime. Hence, each term in the bracket will not be more than one, it means that once the product is multiplied by it, its value will decline. Thus, if \(e\in E(G)\), \(w(e)\) has no more than \(8\) different prime factors. The value of the generalized Euler \(\Phi_w\)-function of \(w(e)\), for all \(e\in E(G)\) will be smaller than the value for its generalized Euler \(\Phi_w\)-function, with at most \(8\) different prime factors. Therefore, for all \(e\in E(G)\), such that \(w(e)\) with at most \(8\) different prime factors \[\Phi_w(G)=\sum_{e\in E(G)}\varphi(w(e))>\frac{1}{6}\sum_{e\in E(G)}w(e).\] ◻
Theorem 6. For all \(e\in E(G)\), we have \[\sum_{e\in E(G)}\frac{w(e)}{\varphi(w(e))}=\sum_{e\in E(G)}\sum_{d|w(e)}\frac{\mu^2(d)}{\varphi(d)} \,.\]
Proof. From Lemma 2, we observe that for each \(e\in E(G)\) \(w(e)={p_1}^{a_1}{p_2}^{a_2}\dots {p_t}^{a_t}\) we have \[\begin{aligned} \varphi(w(e))&=w(e)*\prod_{p|w(e)}\left(1-\frac{1}{p}\right) =w(e)*\left(1-\frac{1}{p_1}\right)*\left(1-\frac{1}{p_2}\right)*\dots *\left(1-\frac{1}{p_t}\right)\\ &=\frac{w(e)*(p_1-1)*(p_2-1)*\dots *(p_t-1)}{p_1*p_2*\dots *p_t} \,.\end{aligned}\] Hence, for each \(e\in E(G)\), we have that \[\begin{aligned} \frac{w(e)}{\varphi(w(e))}&=\frac{w(e)}{\frac{w(e)*(p_1-1)*(p_2-1)*\dots *(p_t-1)}{p_1*p_2*\dots *p_t}} =\frac{p_1*p_2*\dots *p_t}{(p_1-1)*(p_2-1)*\dots *(p_t-1)} \,. \end{aligned}\] If we take summation over the vertices \(e\in E(G)\), thus \[\sum_{e\in E(G)}\frac{w(e)}{\varphi(w(e))}=\sum_{{p_i}|w(e)}\frac{p_1*p_2*\dots *p_t}{(p_1-1)*(p_2-1)*\dots *(p_t-1)}\,.\]
This is what we have acquired from the left hand side of the above identity directly. Hereafter we will represent \(\sum\limits_{e\in E(G)}\frac{w(e)}{\varphi(w(e))}\) by LHS in this proof.
Also, we will represent the right hand side by RHS of above identity. It is clear from definition of Möbius function, where \(w(e)=p_1p_2\dots p_t\), \(\mu(w(e))=(-1)^t\) and \(\mu(w(e))=0\) if \(w(e)\) has a square term. Therefore, \({\mu }^2(d)=1\) if \(d\) has no any square term and \({\mu }^2(d)=0\) if \(d\) has a square term. Hence, we at most have \(w(e)\) which is able to be factorized as the product of distinct primes or the product of distinct primes is also called square-free. Hereafter in this proof, we will represent \(d_s\) as a square-free. Hence, \[\sum_{{d_s}|w(e)}\frac{\mu^2(d_s)}{\varphi(d_s)}=\sum_{{d_s}|w(e)}\frac{1}{\varphi(d_s)}\,.\]
As \(d_s\) is square-free, therefore, each prime in the factorization of \(w(e)\) is utilized once. Hence, the meaning of the above expression is that each of the value \(1,\ \left(p_1,p_2,\dots ,p_t\right), (p_1*p_2,p_2*p_3,\dots ,p_{t-1}*p_t), \left(p_1*p_2*\dots *p_t\right)\) is taken by \(d_s\). Thus, the RHS becomes \[\begin{aligned} \sum_{{d_s}|w(e)}\frac{1}{\varphi(d_s)}&=\frac{1}{\varphi(1)}+\frac{1}{\varphi(p_1)}+\dots +\frac{1}{\varphi(p_1*p_2)}+\dots +\frac{1}{\varphi(p_1*p_2*\dots p_t)}\\ &=1+\frac{1}{p_1-1}+\dots +\frac{1}{(p_1-1)*(p_2-1)}+\dots +\frac{1}{(p_1-1)*(p_2-1)*\dots *(p_t-1)}\\ &=\frac{\left((p_1-1)*\dots *(p_t-1)\right)+\left((p_2-1)*\dots *(p_t-1)\right)+\dots +\left((p_t-1)+\dots +1\right)}{\prod_{i=1}^{t}(p_i-1)}\\ &=\frac{1+(p_1-1)+\dots +(p_t-1)+(p_1-1)*(p_2-1)+\dots +(p_1-1)*(p_2-1)*\dots *(p_t-1)}{\prod_{i=1}^{t}(p_i-1)}\\ &=\frac{\varphi(1)+\varphi(p_1)+\dots +\varphi(p_t)+\varphi(p_1)*\varphi(p_2)+\dots +\varphi(p_1)*\varphi(p_2)*\dots *\varphi(p_t)}{\prod_{i=1}^{t}(p_i-1)} \,. \end{aligned}\] Since \(\varphi\) is multiplicative because all primes are co-primes. Therefore, the RHS will be \[\begin{aligned} \sum_{{d_s}|w(e)}\frac{1}{\varphi(d_s)}&=\frac{\varphi(1)+\varphi(p_1)+\dots +\varphi(p_t)+\varphi(p_1*p_2)+\dots +\varphi(p_1*p_2*\dots *p_t)}{\prod_{i=1}^{t}(p_i-1)}\\ &=\frac{\sum_{d_N|(p_1*p_2*\dots *p_t) }\varphi(d_N)}{\prod_{i=1}^{t}(p_i-1)} \,. \end{aligned}\] Therefore, for each \(u, v\in V(G)\) we have, from Lemma 2, \[\frac{\sum_{d_N|(p_1*p_2*\dots *p_t) }\varphi(d_N)}{\prod_{i=1}^{t}(p_i-1)}=\frac{w(e)}{\prod_{i=1}^{t}(p_i-1)} \,.\] By taking summation over all vertices \(e\in E(G)\), we have \[\sum_{e\in E(G)}\sum_{{d_s}|w(e)}\frac{1}{\varphi(d_s)}=\sum_{\substack{e\in E(G),\\ {p_i}|w(e)}}\frac{w(e)}{\prod_{i=1}^{t}(p_i-1)}=\sum_{{p_i}|w(e)}\frac{(p_1*p_2*\dots *p_t)}{\prod_{i=1}^{t}(p_i-1)},\] when \(w(e)=(p_1*p_2*\dots *p_t)\), which is equal to the LHS. Hence, \[\sum_{e\in E(G)}\frac{w(e)}{\varphi(w(e))}=\sum_{e\in E(G)}\sum_{d| w(e)}\frac{\mu^2(d)}{\varphi(d)}.\] ◻
The following theorem is about an important properties of generalized the divisor \(T_{k_w}\)-function for the divisor sum of the wiener index of a graph.
Theorem 7. For each \(e\in E(G)\) and \(w(e)= p_1^{a_1}p_2^{a_2}\dots p_t^{a_t}\ge 1\), we have \[T_{k_w}(G)=\sum_{e\in E(G)}\sigma_k(w(e))=\sum_{e\in E(G)}\left(\prod_{p_i|w(e)}\left(\sum_{j=0}^{a_i}p_i^{jk}\right)\right)=\sum_{e\in E(G)}\left(\prod_{i=1, p_i|w(e)}^{t}\frac{p_i^{(a_i+1)k}-1}{p_i^k-1}\right)\,.\]
Proof. Let \(e\in E(G)\), \((w(e)=p_1^{a_1}p_2^{a_2}\dots p_t^{a_t}) \ge 1\) and since \(\sigma_k\) is multiplicative, thus \[\begin{aligned} T_{k_w}(G)&=\sum_{e\in E(G)}\sigma_k(w(e))=\sum_{e\in E(G)}\sigma_k(p_1^{a_1}p_2^{a_2}\dots p_t^{a_t})\\ &=\sum_{e\in E(G)}\left(\sigma_k(p_1^{a_1})*\sigma_k(p_2^{a_2})*\dots *\sigma_k(p_t^{a_t})\right)\\ &=\sum_{e\in E(G)}\left(\left(\frac{p_1^{(a_1+1)k}-1}{p_1^k-1}\right)*\left(\frac{p_2^{(a_2+1)k}-1}{p_2^k-1}\right)*\dots*\left(\frac{p_t^{(a_t+1)k}-1}{p_t^k-1}\right)\right)\\ &=\sum_{e\in E(G)}\left(\prod_{\substack{i=1,\\ p_i|w(e)}}^{t}\frac{p_i^{(a_i+1)k}-1}{p_i^k-1}\right)\,. \end{aligned}\] Or, we can use the geometric formula for series and the result follows. ◻
Lemma 4. If \(w(e)=p^a \ge 1\) for \(e\in E(G)\), then we have \[T_{k_w}(G)=\sum_{d|p^a}\sigma_k(p^a)= \begin{cases} \sum_{d|p^a}\frac{p^{(a+1)k}-1}{p^k-1}, & \text{if}\ \ k\neq 0,\\ \sum_{d|p^a}(a+1),& \text{if}\ \ k=0. \end{cases}\]
Proof. The proof follows directly from Theorem 7. ◻
Theorem 8. For all \(e\in E(G)\) with \(w(e)\ge 1\), we have \[T_{k_w}(G)=\sum_{e\in E(G)}\left(\sum_{w(e)=1}^{N}\sigma_k(w(e))\right)=\sum_{e\in E(G)}\left(\sum_{w(e)=1}^{N}\left((w(e))^k\left[\frac{N}{w(e)}\right]\right)\right)\,,\] where \(\left[\frac{N}{w(e)}\right]\) is the greatest integer less than \(\left(\frac{N}{w(e)}\right)\) and \(N\) is a positive integer.
Proof. Set, for all \(e\in E(G)\), \(B_{(N,w(e))}=\left[\frac{N}{w(e)}\right]-\left[\frac{N-1}{w(e)}\right]\) for \(w(e)\ge 1.\) Then \[(w(e))^k(B_{(N,w(e))})= \begin{cases} (w(e))^k, & \text{when}\ \ w(e)|N;\\ 0 & \text{when} \ \ w(e)\nmid N, \end{cases}\] and then \[\begin{aligned} T_{k_w}(G)&=\sum_{e\in E(G)}\left(\sum_{w(e)=1}^{N}\sigma_k(w(e))\right)=\sum_{e\in E(G)}\left(\sum_{w(e)=1}^{N}\left(\sum_{k=1}^{w(e)}k^{w(e)}B_{(w(e),k)}\right)\right)\\ &=\sum_{e\in E(G)}\left(\sum_{w(e)=1}^{N}\left(\sum_{k=1}^{w(e)}k^{w(e)}\left(\left[\frac{w(e)}{k}\right]-\left[\frac{w(e)-1}{k}\right]\right)\right)\right)\\ &=\sum_{e\in E(G)}\left(\sum_{w(e),k=1}^{N}k^{w(e)} \left[\frac{w(e)}{k}\right]-\sum_{\substack{1\le k\le N,\\ 1\le w(e)\le N-1}}k^{w(e)} \left[\frac{w(e)}{k}\right]\right)\end{aligned}\] \[\label{eq3.1} =\sum_{e\in E(G)}\sum_{\substack{1\le k\le N,\\ w(e)=N}}k^{w(e)} \left[\frac{w(e)}{k}\right]\,. \tag{2}\] The results follows from Theorem 7 by exchanging \(k\) with \(w(e)\) and since \(w(e)=N,\) we obtain that \[T_{k_w}(G)=\sum_{e\in E(G)}\left(\sum_{w(e)=1}^{N}\sigma_k(w(e))\right)=\sum_{e\in E(G)}\left(\sum_{w(e)=1}^{N}\left((w(e))^k\left[\frac{N}{w(e)}\right]\right)\right)\,.\] ◻
Lemma 5. For all \(e\in E(G)\), \(w(e)\) is a prime number if and only if \[T_{k_w}(G)=\sum_{e\in E(G)}\sigma_k(w(e))=\sum_{e\in E(G)}\left((w(e))^k+1\right).\]
Proof. If \(w(e)\) is a prime for all \(e\in E(G)\), then if we have \(t\)-vertices in the graph \(G\), \[\begin{aligned} T_{k_w}(G)&=\sum_{e\in E(G)}\sigma_k(w(e))\\ &=\left(\sigma_k(d(u_1,u_2))+\sigma_k(d(u_1,u_3))+\dots+\sigma_k(d(u_1,u_n))\right)+\dots+\sigma_k(d(u_{n-1},u_n))\,. \end{aligned}\] Since \(e\in E(G)\), \(w(e)\) is a prime number, therefore \(d(u_1,u_2)=d(u_1,u_3)=\dots=d(u_1,u_n)=\dots=d(u_{n-1},u_n)=p\), so
\[\begin{aligned} T_{k_w}(G)&=\sum_{e\in E(G)}\sigma_k(w(e))=\sigma_k(p)+\sigma_k(p)+\dots+\sigma_k(p)=\sum_{p}\sigma_k(p)\\ &=\sum_{p}(p^k+1)=\sum_{e\in E(G)}\left((w(e))^k+1\right). \end{aligned}\] ◻
The following theorem gives a relationship between generalized divisor sum \(T_{k_w}\)-function and the Euler \(\phi\)-function of a graph, where \(k=1\).
Theorem 9. For all \(e\in E(G)\), \(w(e)\ge 1\), we have \[T_{1_w}(G)=\sum_{e\in E(G)}\sigma_1(w(e))=\sum_{e\in E(G)}\left(\sum_{d|w(e)}\varphi(d)*\sigma_0\left(\frac{w(e)}{d}\right)\right),\] where \(d\) is the divisor of the vertices’ degree in a graph \(G\).
Proof. Let \((w(e))= p_1^{a_1}p_2^{a_2}\dots p_t^{a_t}.\) If we choose the left hand side (LHS) to be \(\sum\limits_{e\in E(G)}\sigma_1(w(e)).\) Since the divisor function \(\sigma_k\) and Euler \(\varphi\)-function are multiplicative, so from the Theorem 7, in the case when \(k=1\), we have \[\sum_{e\in E(G)}\sigma_1(w(e))=\sum_{w(e)=\{p_1,p_2,\dots,p_t\}}\sigma_1(p_1^{a_1}p_2^{a_2}\dots p_t^{a_t})=\sum_{w(e)=\{p_1,p_2,\dots,p_t\}}\left(\prod_{i=1}^{t}\frac{p_i^{(a_i+1)k}-1}{p_i^k-1}\right)\,.\] This side will be called the left hand side (LHS). If we see the right hand side (RHS), in our case, \(d\) is our divisor of \(w(e)\) which has the form \(d=p_1^{i_1}p_2^{i_2}\dots p_t^{i_t}\) where \(0\le i_1,i_2,\dots,i_t\le a_1,a_2,\dots,a_t\) respectively. The representation of each divisor will be allowed because in this way the divisors with different primes can be counted with different these primes could have. Since \(w(e)= p_1^{a_1}p_2^{a_2}\dots p_t^{a_t}\). Thus, \[\begin{aligned} &\sum_{e\in E(G)}\left(\sum_{d|w(e)}\varphi(d)*\sigma_0\left(\frac{w(e)}{d}\right)\right) =\sum_{\{p_1,p_2,\dots,p_t\}} \left(\sum_{i_1=0}^{a_1}\sum_{i_2=0}^{a_2}\dots \sum_{i_t=0}^{a_t}\varphi(p_1^{i_1}p_2^{i_2}\dots p_t^{i_t})*\sigma_0\left(\frac{p_1^{a_1}p_2^{a_2}\dots p_t^{a_t}}{p_1^{i_1}p_2^{i_2}\dots p_t^{i_t}}\right)\right)\,. \end{aligned}\]
Since \(\varphi\) and \(\sigma_0\) are multiplicative and by rearranging their terms, we obtain \[RHS=\sum_{\{p_1,p_2,\dots,p_t\}} \left(\sum_{i_1=0}^{a_1}\sum_{i_2=0}^{a_2}\dots \sum_{i_t=0}^{a_t}\varphi(p_1^{i_1})\sigma_0(p_1^{a_1-i_1})*\varphi(p_2^{i_2})\sigma_0(p_2^{a_2-i_2})*\dots *\varphi(p_t^{i_t})\sigma_0(p_t^{a_t-i_t})\right)\,.\] Since we have \(t\)-terms and for each of them we only have two terms to be variable and the rest are constant which can be obtained in front of the sum, so by applying this way \(t-\)times, we obtain that \[\label{thm2} RHS=\sum_{\{p_1,p_2,\dots,p_t\}} \left(\sum_{i_1=0}^{a_1} \varphi(p_1^{i_1})\sigma_0(p_1^{a_1-i_1})*\sum_{i_2=0}^{a_2}\varphi(p_2^{i_2})\sigma_0(p_2^{a_2-i_2})*\dots *\sum_{i_t=0}^{a_t}\varphi(p_t^{i_t})\sigma_0(p_t^{a_t-i_t})\right)\,. \tag{3}\] If the first sum in the bracket is denoted by \(A\), then
\[\begin{aligned} A&=\sum_{i_1=0}^{a_1} \varphi(p_1^{i_1})\sigma_0(p_1^{a_1-i_1})\\ &=\varphi(1)\sigma_0(p_1^{a_1})+\varphi(p_1)\sigma_0(p_1^{a_1-1})+\dots+\varphi(p_1^{i_1-1})\sigma_0(p_1)+\varphi(p_1^{a_1})\sigma_0(1)\\ &=1+p_1+p_1^2+p_1^3+\dots+p_1^{a_1-1}+p_1^{a_1}\,. \end{aligned}\] It can be seen that this is a geometric progression, so we can use its formula here, \[A=\sum_{i_1=0}^{a_1} \varphi(p_1^{i_1})\sigma_0(p_1^{a_1-i_1})=\frac{1-p_1^{a_1+1}}{1-p_1}=\frac{p_1^{a_1+1}-1}{p_1-1}\,.\] This result can be applied to all the \(t-\)terms in (3), so the RHS will be \[\begin{aligned} RHS=\sum_{\{p_1,p_2,\dots,p_t\}}\left(\frac{p_1^{a_1+1}-1}{p_1-1}*\frac{p_2^{a_2+1}-1}{p_2-1}*\dots *\frac{p_t^{a_t+1}-1}{p_t-1}\right)&=\sum_{\{p_1,p_2,\dots,p_t\}}\left(\prod_{i=1}^{t}\frac{p_i^{a_i+1}-1}{p_i-1}\right)=LHS\,. \end{aligned}\] ◻
