Generalized the Liouville’s and Möbius functions of graph

Author(s): Hariwan Fadhil M. Salih1, Shadya Merkhan Mershkhan2
1Department of Mathematics, College of Science, University of Duhok, IRAQ.
2Department of Mathematics, Faculty of Science, University of Zakho, IRAQ.
Copyright © Hariwan Fadhil M. Salih, Shadya Merkhan Mershkhan. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Let \(G = (V,E)\) be a simple connected undirected graph. In this paper, we define generalized the Liouville’s and Möbius functions of a graph \(G\) which are the sum of Liouville \(\lambda\) and Möbius \(\mu\) functions of the degree of the vertices of a graph denoted by \(\Lambda(G)=\sum\limits_{v\in V(G)}\lambda(deg(v))\) and \(M(G)=\sum\limits_{v\in V(G)}\mu(deg(v))\), respectively. We also determine the Liouville’s and Möbius functions of some standard graphs as well as determining the relationships between the two functions with their proofs. The sum of generalized the Liouville and Möbius functions extending over the divisor d of degree of vertices of graphs is also given.

Keywords: Generalized Liouville \(\Lambda\)-function, generalized Möbius \(M\)-function, Liouville \(\lambda\)-function, Möbius \(\mu\)-function.

1. Introduction

The Liouville and Möbius functions arise and play an important role in various places in number theory which are denoted by \( \lambda \) and \( \mu \), respectively. The Liouville \( \lambda \)-function is defined as: \begin{equation*} \lambda(n) = \begin{cases} \,\,\,1 & \text{if} \; n=1; \\ \left(-1\right)^{a_1+…+a_k} & \text{if}\; n={{p_1}^{a_1}}{{p_2}^{a_2}}\dots {{p_k}^{a_k}}. \end{cases} \end{equation*} For instance, since \( 8=2^3 \), thus \( \lambda(8)=(-1)^3=-1 \) [1]. The Möbius \( \mu \)-function \( f:N\rightarrow\{-1,0,1\} \) is defined as: \begin{equation*} \mu(n) = \begin{cases} 1 & \text{if} \; n=1; \\ \left(-1\right)^t & \text{if}\; n={p_1}{p_2}\dots {p_t}\;\text{ where the}\; p_i \;\text{ are distinct primes}; \\ 0 & \text{otherwise.} \end{cases} \end{equation*}

For example, since there are two distinct primes in factorizing \( 10=2*5 \), therefore, \( \mu(10)=(-1)^2 \). Also, there are no distinct primes in \( 9=3^2 \), hence, \( \mu(9)=0 \) [1]. A function \( f \) is said to be multiplicative if for all positive integers \( m \), \( n \) such that\( m \), \( n \) are relatively primes, then \( f(mn)=f(m)f(n) \) [2]. A function \( f \) is said to be completely multiplicative if for all positive integers \( m \), \( n \), we have \( f(mn)=f(m)f(n) \) [3]. The Liouville’s \( \lambda \)-function is an important example of a completely multiplicative function [3], whereas, the Möbius \( \mu \)-function is multiplicative [2]. Salih and Ibrahim in [4] defined the generalized Euler’s \( \Phi\)-function of a graph which is summation of the Euler’s \(\Phi\)-function of degree of the vertices of a graph and it is denoted by \( \Phi(G)\). The general form of Euler’s \( \Phi\)-function of some standard graphs is known. For all other standard terminologies and notations we follow [5, 6, 7, 8, 9, 10].

In this paper, we utilize two number theory functions called the Liouville’s \( \lambda \)-function and the Möbius \( \mu \)-function into graph theory in order to define new functions called the generalized Liouville’s \( \Lambda \)-function \( \Lambda(G) \) and the generalized Möbius \( M \)-function \( M(G) \) of a graph \( G \), which are defined as the sum of the Liouville’s \( \lambda \)-function and the Möbius \( \mu \)-function of the degree of vertices of a graph \( G \), respectively. In addition, the generalized Liouville’s and Möbius functions of some standard graphs are determined along with determining the relationships between the two functions.

2. Generalized the Liouville’s and Möbius Functions of Some Standard Graphs

In this section, the generalized Liouville’s and Möbius functions of some important graphs which are the path graph \( P_n \), cycle graph \( C_n \), complete graph \( K_n \), complete bipartite graph \( K_{(m,n)} \), \( k \)-partite graph \( K_{(m_1,m_2…,m_n )} \), star graph \( S_n \), and wheel graph \( W_n \) are determined.

Definition 1. Let \(G\) be a simple connected graph. The generalized Liouville,s \( \Lambda \)-function is defined as the sum of the Liouville \( \lambda \)-function of the degree of vertices \( v \) of a graph \( G \) which is denoted by \( \Lambda(G) \). That is \[\Lambda(G)=\sum\limits_{v\in V(G)}\lambda(deg(v)).\]

Definition 2. Let \( G \) be a simple connected graph. The generalized Möbius \( M \)-function is defined as the sum of the Möbius \( \mu \)-function of the degree of vertices \( v \) of a graph \( G \) which is denoted by \( M(G) \). That is \[M(G)=\sum\limits_{v\in V(G)}\mu(deg(v)).\]

In the following propositions, we determine general form and exact values of the generalized Liouville \( \Lambda \)-function and the generalized Möbius \( \mu \)-function of some standard graphs.

Proposition 1.

  1. The generalized Liouville \( \Lambda \)-function of the path graph \( G=P_n \), for \( n\ge2 \) vertices, is \(\Lambda (P_n)=4-n.\)
  2. The generalized Liouville \( \Lambda \)-function of the cycle graph \( G=C_n \), for \( n\ge3 \) vertices, is \( \Lambda(C_n )=-n .\)
  3. The generalized Liouville \( \Lambda \)-function of the complete graph \( G=K_n \), for \( n\ge3 \) vertices, is \(\Lambda(K_n)=n \lambda(n-1)=n(-1)^{a_1+a_2+\dots+a_k},\) where \( (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \).
  4. The generalized Liouville \( \Lambda \)-function of the complete bipartite graph \( G=K_{m,n} \), for any positive integers \( m \), \( n \) vertices, is \( \Lambda(K_{m,n})=(m*\lambda(n))+(n*\lambda(m))=(m*(-1)^{a_1+a_2+\dots+a_k})+(n*(-1)^{b_1+b_2+\dots+b_j}), \) where \( m={p_1}^{a_1}{p_2}^{a_2}\dots{p_k}^{a_k} \) and \( n={q_1}^{b_1}{q_2}^{b_2}\dots{q_j}^{b_j}\).
  5. The generalized Liouville \( \Lambda \)-function of the star graph \( G=S_n \), for \( n\ge 2 \) vertices, is \(\Lambda(S_n)=\lambda(n-1)+(n-1)=(-1)^{a_1+a_2+\dots+a_k}+(n-1),\) where \( (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \).
  6. The generalized Liouville \( \Lambda \)-function of the \( k \)-partite graph \( G=K_{m_1,m_2,\dots,m_n} \), for any positive integers \( m_1,m_2,\dots,m_n \) vertices, is \( \Lambda(K_{m_1,m_2,\dots,m_n})=\sum\limits_{i=1}^{n}\left(m_i*\lambda\left(\sum\limits_{j\neq i,\ j=1,2,\dots n}m_j\right)\right)=\sum\limits_{i=1}^{n}\left(m_i*(-1)^{a_1+a_2+\dots+a_k}\right), \) where \(\left(\sum\limits_{j=1,2,\dots n}m_j={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k}\right).\)
  7. The generalized Liouville \( \Lambda \)-function of the Wheel graph \( G=W_n \), for \( n\ge 4 \) vertices, is \(\Lambda(W_n )=(1-n)+\lambda(n-1)=(1-n)+(-1)^{a_1+a_2+\dots+a_k},\) where \( (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \).

Proof.

  1. In the path graph \( P_n \) of order \( n \), if \( n=2 \), we have two vertices of degree one, then we have \( \Lambda(P_2 )=\lambda(1)+\lambda(1)=2 \). If \( n\ge 3 \), we have two vertices of degree one and \( n-2 \) vertices of degree two, then we have: \begin{equation*} \begin{cases} &\Lambda(P_3)=2\lambda(1)+\lambda(2)=1;\\ &\Lambda(P_4)=2\lambda(1)+2\lambda(2)=0;\\ &\Lambda(P_5)=2\lambda(1)+3\lambda(2)=-1;\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ &\Lambda(P_n)=2\lambda(1)+(n-2)\lambda(2)=4-n. \end{cases} \end{equation*}
  2. There are \( n \) vertices of degree two in a cycle graph \( C_n \) of order \( n \), hence we have: \begin{equation*} \begin{aligned} \Lambda(C_n)&=\sum\limits_{v\in V(C_n)}\lambda(deg(v))=\lambda(deg(v_1))+\lambda(deg(v_2))+\dots +\lambda(deg(v_n))=n\lambda(2)=-n. \end{aligned} \end{equation*}
  3. There are \( n \) vertices of degree \( n-1 \) in a complete graph \( K_n \) of order \( n \), hence we have: \begin{equation*} \begin{aligned} \Lambda(K_n)&=\sum\limits_{v\in V(K_n)}\lambda(deg(v))=\lambda(deg(v_1))+\lambda(deg(v_2))+\dots +\lambda(deg(v_n))\\ &=n\lambda(n-1)=n*(-1)^{a_1+a_2+\dots+a_k},\;\text{where}\; (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k}. \end{aligned} \end{equation*}
  4. There are \( m \) vertices of degree \( n \) and \( n \) vertices of degree \( m \) in a complete bipartite graph \( K_{m,n} \) of order \( m+n \), hence we have: \begin{equation*} \begin{aligned} \Lambda(K_{m,n})&=\sum\limits_{v\in V(K_{m,n})}\lambda(deg(v))\\ &=\lambda(deg(u_1))+\lambda(deg(u_2))+\dots +\lambda(deg(u_m))+\lambda(deg(v_1))+\lambda(deg(v_2))+\dots +\lambda(deg(v_n))\\ &=\lambda(n)+\lambda(n)+\dots+\lambda(n)+\lambda(m)+\lambda(m)+\dots+\lambda(m)\\ &=(m*\lambda(n))+(n*\lambda(m))\\ &=(m*(-1)^{a_1+a_2+\dots+a_k})+(n*(-1)^{b_1+b_2+\dots+b_j}), \end{aligned} \end{equation*} where \( m={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \) and \( n={q_1}^{b_1}{q_2}^{b_2}\dots {q_j}^{b_j} \)
  5. There are \( n-1 \) vertices of degree one and there is one vertex of degree \( n-1 \), say \( v_1 \), in a star graph \( S_n \) of order \( n \), hence we have: \begin{equation*} \begin{aligned} \Lambda(S_n)&=\sum\limits_{v\in V(S_n)}\lambda(deg(v))\\ &=\lambda(deg(v_1))+\lambda(deg(v_2))+\dots +\lambda(deg(v_n))\\ &=\lambda(n-1)+(n-1)\lambda(1)\\ &=(-1)^{a_1+a_2+\dots+a_k}+n-1,\;\text{where}\; (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k}. \end{aligned} \end{equation*}
  6. There are \( m_i \) vertices of degree \( \sum\limits_{j\neq i}m_j \) where \( j,i=1,2,\dots,n \) in a complete \( k \)-partite graph \( K_{m_1,m_2,\dots,m_n} \) of order \( m_1+m_2+\dots+m_n \), hence we have: \begin{equation*} \begin{aligned} \Lambda(K_{m_1,m_2,\dots,m_n})&=\sum\limits_{v\in V(K_{m_1,m_2,\dots,m_n})}\lambda(deg(v))\\ &=\lambda(deg(v_1))+\lambda(deg(v_2))+\dots +\lambda(deg(v_n))\\ &=(m_1*\lambda(m_2+m_3+\dots +m_n))+(m_2*\lambda(m_1+m_3+\dots +m_n))+\dots\\&\;\;\;+(m_n*\lambda(m_1+m_2+\dots +m_{n-1}))\\ &=\sum\limits_{i=1}^{n}\left(m_i*\lambda\left(\sum\limits_{j\neq i,\ j=1,2,\dots n}m_j\right)\right)\\ &=\sum\limits_{i=1}^{n}\left(m_i*(-1)^{a_1+a_2+\dots+a_k}\right) \end{aligned} \end{equation*} where \(\sum\limits_{j=1,2,\dots n}m_j={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k}.\)
  7. There are \( n-1 \) vertices of degree three and we have one vertex of degree \( n-1 \), say \( v_1 \), in a wheel graph \(W_n\) of order \(n,\) hence we have: \begin{equation*} \begin{aligned} \Lambda(W_n)&=\sum\limits_{v\in V(W_n)}\lambda(deg(v))\\ &=\lambda(deg(v_1))+\lambda(deg(v_2))+\dots +\lambda(deg(v_n))\\ &=\lambda(n-1)+(n-1)\lambda(3)=(-1)^{a_1+a_2+\dots+a_k}-n-1, \end{aligned} \end{equation*} where \( (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \).

Proposition 2.

  1. The generalized Möbius \( M \)-function of the path graph \( G=P_n \), for \( n\ge2 \) vertices, is \(M(P_n)=4-n.\)
  2. The generalized Möbius \( M \)-function of the cycle graph \( G=C_n \), for \( n\ge3 \) vertices, is \( M(C_n )=-n .\)
  3. The generalized Möbius \( M \)-function of the complete graph \( G=K_n \), for \( n\ge3 \) vertices, is
    \( M(K_n)=n \mu(n-1)= \begin{cases} n & \text{if}\; n=2\\ n*(-1)^k& \text{ if} \; (n-1)=p_1p_2\dots p_k,\\ 0& \text{otherwise} \end{cases} \)

    where \( (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \).

  4. The generalized Möbius \( M \)-function of the complete bipartite graph \( G=K_{m,n} \), for any positive integers \( m \), \( n \) vertices, is \begin{equation*} \begin{aligned} M(K_{m,n})&=(m*\mu(n))+(n*\mu(m))\\ &= \begin{cases} m& if\ n=1\\ m*(-1)^k& if \ n=p_1p_2\dots p_k,\\ 0& otherwise \end{cases} + \begin{cases} n& if\ m=1\\ n*(-1)^j& if \ m=p_1p_2\dots p_j,\\ 0& otherwise \end{cases} \end{aligned} \end{equation*} where \( m={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \) and \( n={q_1}^{b_1}{q_2}^{b_2}\dots {q_j}^{b_j} \).
  5. The generalized Möbius \( M \)-function of the star graph \( G=S_n \), for \( n\ge 2 \) vertices, is
    \( M(S_n)=(n-1)+ \mu(n-1) =(n-1)+ \begin{cases} 1& if\ n=1\\ (-1)^k& if \ (n-1)=p_1p_2\dots p_k,\\ 0& otherwise \end{cases} \)
    where \( (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \).
  6. The generalized Möbius \( M \)-function of the \( k \)-partite graph \( G=K_{m_1,m_2,\dots,m_n} \), for any positive integers \( m_1,m_2,\dots,m_n \) vertices, is \begin{equation*} \begin{aligned} M(K_{m_1,m_2,\dots,m_n})&=\sum\limits_{i=1}^{n}\left(m_i*\mu\left(\sum\limits_{j\neq i,\ j=1,2,\dots n}m_j\right)\right)\\ &= \begin{cases} m_1*(-1)^k& if \ \sum\limits_{j\neq 1,\ j=1,2,\dots n}m_j=p_1p_2\dots p_k\\ 0& otherwise \end{cases}\\ &= \begin{cases} m_2*(-1)^t& if \ \sum\limits_{j\neq 2,\ j=1,2,\dots n}m_j=p_1p_2\dots p_t\\ 0& otherwise \end{cases}\\ &\;\;\;\;\;+ \begin{cases} m_n*(-1)^r& if \ \sum\limits_{j\neq n,\ j=1,2,\dots n}m_j=p_1p_2\dots p_t\\ 0& otherwise \end{cases} \end{aligned} \end{equation*} where \(\sum\limits_{j=1,2,\dots n}m_j={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k}.\)
  7. The generalized Möbius \( M \)-function of the Wheel graph \( G=W_n \), for \( n\ge 4 \) vertices, is
    \( M(W_n )=(1-n)+\mu(n-1)=(1-n)+ \begin{cases} (-1)^k& if\ (n-1)=p_1,p_2,\dots,p_k\\ 0& otherwise, \end{cases}, \)
    where \( (n-1)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k} \).

Proof. The proof is similar to the Proposition 1.

3. Summing up generalized the Liouville \( \Lambda \)-function and generalized the Möbius \( M \)-function over the divisor \( d \) and their proofs

In this section, we give some new results of finding the sum of the generalized Liouville \( \Lambda \)-function and the generalized tMöbius \( M \)-function extending over the divisor \( d \) which are the sum of the Liouville \( \lambda \)-function and the Möbius \( \mu \)-function of the divisor of degree of vertices of the above standard graphs.

Theorem 1. For all \( v\in V(G) \), \( deg(v)\ge1 \), and \( \Lambda_d \) refers to the generalized Liouville \(\Lambda\)-function over the divisor \( d \) of \( deg(v) \), we have

  1. \(\sum\limits_{v\in V(P_n),\ d|deg(v)}\Lambda_d(P_n)=\sum\limits_{v\in V(P_n)}\sum\limits_{d|deg(v)} \lambda(d)=2.\)
  2. \(\sum\limits_{v\in V(C_n),\ d|deg(v)}\Lambda_d(C_n)=\sum\limits_{v\in V(C_n)}\sum\limits_{d|deg(v)} \lambda(d)=0.\)
  3. \( \sum\limits_{v\in V(K_n),\ d|deg(v)}\Lambda_d(K_n)=\sum\limits_{v\in V(K_n)}\sum\limits_{d|deg(v)} \lambda(d)= \begin{cases} n & if \ (n-1) \ is \ square;\\ 0 & otherwise. \end{cases}\)
  4. \( \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}\Lambda_d(K_{m,n})=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)} \lambda(d)= \begin{cases} \begin{cases} m+n & if\ n \ is\ a\ square\\ n & otherwise \end{cases} & if\ m\ is\ a\ square;\\ \begin{cases} m & if\ n \ is\ a\ square\\ 0 & otherwise \end{cases} & otherwise. \end{cases}\)
  5. \( \sum\limits_{v\in V(S_n),\ d|deg(v)}\Lambda_d(S_n)=\sum\limits_{v\in V(S_n)}\sum\limits_{d|deg(v)} \lambda(d) = \begin{cases} n & if \ (n-1) \ is \ square;\\ (n-1) & otherwise. \end{cases} \)
  6. \( \sum\limits_{v\in V(W_n),\ d|deg(v)}\Lambda_d(W_n)=\sum\limits_{v\in V(W_n)}\sum\limits_{d|deg(v)} \lambda(d)= \begin{cases} 1&if \ (n-1) \ is \ square;\\ 0& otherwise. \end{cases} \)
  7. \(\sum\limits_{v\in V(K_{m_1,m_2,\dots,m_n}),\ d|deg(v)}\Lambda_d(K_{m_1,m_2,\dots,m_n})=\sum\limits_{v\in V(K_{m_1,m_2,\dots,m_n})}\sum\limits_{d|deg(v)} \lambda(d)=\)
    \( \begin{cases} m_1& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 1}m_j \ is \ square;\\ m_2&if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j \ is \ square;\\ \vdots\\ m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ is \ square;\\ m_1+m_2& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 1}m_j\ and\ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j \ are \ square;\\ \vdots\\ m_1+m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 1}m_j\ and\ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ are \ square;\\ m_2+m_3& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j\ and\ \sum\limits_{j=1,2,\dots,n,\ j\neq 3}m_j \ are \ square;\\ \vdots\\ m_{n-1}+m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq {n-1}}m_j\ and\ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ are \ square;\\ m_1+m_2+m_3& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 1}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j\ and \sum\limits_{j=1,2,\dots,n,\ j\neq 3}m_j \ are \ square;\\ \vdots\\ m_1+m_2+m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 1}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j\ and\ \ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ are \ square;\\ m_1+m_3+m_4 & if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 1}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq 3}m_j\ and \ \ \sum\limits_{j=1,2,\dots,n,\ j\neq 4}m_j \ are \ square;\\ \vdots\\ m_1+m_3+m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 1}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq 3}m_j\ and \ \ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ are \ square;\\ m_2+m_3+m_4& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq 3}m_j\ and \ \ \sum\limits_{j=1,2,\dots,n,\ j\neq 4}m_j \ are \ square;\\ \vdots\\ m_2+m_3+m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq 3}m_j\ and \ \ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ are \ square;\\ \vdots\\ m_2+m_{n-1}+m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq n-1}m_j\ and \ \ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ are \ square;\\ \vdots\\ m_{n-2}+m_{n-1}+m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq {n-2}}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq n-1}m_j\ and \ \ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ are \ square;\\ \vdots\\ m_1+m_2+\dots+m_n& if \ \sum\limits_{j=1,2,\dots,n,\ j\neq 1}m_j,\ \sum\limits_{j=1,2,\dots,n,\ j\neq 2}m_j,\dots, \ \ \sum\limits_{j=1,2,\dots,n,\ j\neq n}m_j \ are \ square;\\ 0 & otherwise. \end{cases} \).

Proof.

  1. There are two vertices of degree \( 1 \) and \( (n-2) \) vertices of degree \( 2 \) in a path graph \( (P_n) \): \begin{equation*} \begin{aligned} \sum\limits_{v\in V(P_n),\ d|deg(v)}\Lambda_d(P_n)&=\sum\limits_{v\in V(P_n)}\sum\limits_{d|deg(v)}\lambda(d)\\ &=2*\sum\limits_{d|1}\lambda(d)+(n-2)*\sum\limits_{d|2}\lambda(d)\\ &=2*\lambda(1)+(n-2)*(\lambda(1)+\lambda(2))=2. \end{aligned} \end{equation*}
  2. There are \( n \) vertices of degree \( 2 \) in a cycle graph \( (C_n) \): \begin{equation*} \begin{aligned} \sum\limits_{v\in V(C_n),\ d|deg(v)}\Lambda_d(C_n)&=\sum\limits_{v\in V(C_n)}\sum\limits_{d|deg(v)}\lambda(d)\\&=n*\sum\limits_{d|2}\lambda(d)\\ &=n*(\lambda(1)+\lambda(2))=0. \end{aligned} \end{equation*}
  3. There are \( n \) vertices of degree \( (n-1) \) in a complete graph \( K_n \): \begin{equation*} \sum\limits_{v\in V(K_n),\ d|deg(v)}\Lambda_d(K_n)=\sum\limits_{v\in V(K_n)}\sum\limits_{d|deg(v)}\lambda(d)=n*\sum\limits_{d|(n-1)}\lambda(d). \end{equation*} When \( (n-1)\ge 3 \) is a square and by the fact that any square number has odd number of divisors and hence we always have the term \( \lambda(n-1) \) at the end of the sum which is equal to \( 1 \) and all the others by the definition of Liouvile \( \lambda \)-function are canceled. Thus \begin{equation*} \sum\limits_{v\in V(K_n),\ d|deg(v)}\Lambda_d(K_n)=\sum\limits_{v\in V(K_n)}\sum\limits_{d|deg(v)}\lambda(d)=n*\lambda(n-1)=n. \end{equation*} When \( (n-1)\ge 3 \) is not a square. There are two cases:
    Case \( 1 \): If \( deg(v) \) is a prime \( (p) \), then the divisors are only \( 1 \) and \( p \) and hence \( \lambda(1)=1 \) and \( \lambda(p)=-1 \). Thus \begin{equation*} \sum\limits_{v\in V(K_n),\ d|p}\Lambda_d(K_n)=\sum\limits_{v\in V(K_n)}\sum\limits_{d|p}\lambda(d)=n*(\lambda(1)+\lambda(p))=0. \end{equation*} Case \( 2 \): If \( deg(v) \) is not a prime, then there are always even number of divisors of \( deg(v) \) and they are always canceled with one another by the definition of Liouvile \( \lambda \)-function and we obtain that \begin{equation*} \sum\limits_{v\in V(K_n),\ d|deg(v)}\Lambda_d(K_n)=\sum\limits_{v\in V(K_n)}\sum\limits_{d|deg(v)}\lambda(d)=n*(0)=0. \end{equation*}
  4. There are m vertices of degree n and n vertices of degree m in a complete bipartite graph \( K_{m,n} \): \begin{equation*} \begin{aligned} \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}\Lambda_d(K_{m,n})&=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)}\lambda(d)\\ &=n*\left(\sum\limits_{d|m}\lambda(d)\right)+m*\left(\sum\limits_{d|n}\lambda(d)\right). \end{aligned} \end{equation*} We denote \( \left(\sum\limits_{d|m}\lambda(d)\right)=S_1 \) and \( \left(\sum\limits_{d|n}\lambda(d)\right)=S_2. \)
    When \( m \) is square. There are two cases:
    Case 1: If \( n \) is a square. By the fact that any square number has odd number of divisors and hence we always have the term \( (\lambda(m)=1) \) and \( (\lambda(n)=1) \) left in \( S_1 \) and \( S_2 \) respectively and all the other terms in \( S_1 \) and \( S_2 \) are canceled by the definition of Liouville \( \lambda \)-function, \( i.e., \) \begin{equation*} \begin{aligned} \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}\Lambda_d(K_{m,n})&=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)}\lambda(d)\\ &=n*\lambda(m)+m*\lambda(n)=n+m. \end{aligned} \end{equation*} Case 2: If \( n \) is not a square, then all the terms in \( S_2 \) are canceled by the definition of Liouville \( \lambda \)-function because there are always even number of divisors of \( n \) in \( S_2 \). Since \( m \) is a square, then \( (\lambda(m)=1) \) is the only term left in \( S_1 \). Hence, \begin{equation*} \begin{aligned} \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}\Lambda_d(K_{m,n})&=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)}\lambda(d)\\ &=n*\lambda(m)+0=n. \end{aligned} \end{equation*} From the above two cases when \( m \) is a square, we obtain that \begin{equation*} \begin{aligned} \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}\Lambda_d(K_{m,n})&=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)}\lambda(d)\\ &=\begin{cases} m+n & \text{if}\;n \; \text{is a square;}\\ n & \text{otherwise.} \end{cases}. \end{aligned} \end{equation*} When \( m \) is not a square. There are also two cases:
    Case 1: If \( n \) is a square, then \( (\lambda(n)=1) \) is the only term left in \( S_2 \). Since \( m \) is not a square, so all the terms in \( S_1 \) are canceled and thus \( S_1=0 \). Hence, \begin{equation*} \begin{aligned} \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}\Lambda_d(K_{m,n})&=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)}\lambda(d)\\ &=n*(0)+m*(\lambda(n))=m. \end{aligned} \end{equation*} Case 2: If \( n \) is not a square and since \( m \) is also not a square, then all the terms in \( S_1 \) and \( S_2 \) are canceled and hence \( S_1=S_2=0 \). Thus \begin{equation*} \begin{aligned} \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}\Lambda_d(K_{m,n})&=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)}\lambda(d)\\ &=n*(0)+m*(0)=0. \end{aligned} \end{equation*} From the two cases above when \( m \) is not a square, we obtain that \begin{equation*} \begin{aligned} \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}\Lambda_d(K_{m,n})&=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)}\lambda(d)\\ &=\begin{cases} m & \text{if}\; n\;\text{is a square;}\\ 0& \text{otherwise.} \end{cases}. \end{aligned} \end{equation*} From all the above investigation for all \( m \) and \( n \), \( (4) \) has been proved.
  5. The proof follows from \( (4) \) by the fact that \( S_n=K_{1,n-1} \).
  6. There are \( (n-1) \) vertices of degree \( 3 \) and one vertex of degree \( (n-1) \), say \( v_1 \), then \begin{equation*} \begin{aligned} \sum\limits_{v\in V(W_n),\ d|deg(v)}\Lambda_d(W_n)&=\sum\limits_{v\in V(W_n)}\sum\limits_{d|deg(v)}\lambda(d)\\ &=(n-1)*\sum\limits_{d|3}\lambda(d)+\sum\limits_{d|(n-1)}\lambda(d)\\ &=(n-1)*(0)+\sum\limits_{d|(n-1)}\lambda(d)\\ &=\sum\limits_{d|(n-1)}\lambda(d)=S. \end{aligned} \end{equation*} In order to prove \( S \), there are two cases:
    Case 1: If \( (n-1) \) is square and by the fact that any square number has odd number of divisors, the term \( \lambda(n-1)=1 \) is always left in \( S \), \( i.e., \) \[S=\sum\limits_{d|(n-1)}\lambda(d)=\lambda(n-1)=1.\] Case 2: If \( (n-1) \) is not square, then there are always even number of divisors in \( S \) and by the definition of the Liouville \( \lambda \)-function, all the terms in \( S \) are canceled with one another. Thus \[S=\sum\limits_{d|(n-1)}\lambda(d)=0.\] From the two cases above, we obtain that \begin{equation*} \begin{aligned} \sum\limits_{v\in V(W_n),\ d|deg(v)}\Lambda_d(W_n)&=\sum\limits_{v\in V(W_n)}\sum\limits_{d|deg(v)}\lambda(d)\\ &=\begin{cases} 1&\text{ if}\; (n-1)\;\text{ is a square;}\\ 0& \text{otherwise.} \end{cases}. \end{aligned} \end{equation*}
  7. The proof follows from \( (4) \) as it is a special case of \( (7) \).

Theorem 2. For all \( v\in V(G) \), \( deg(v)\ge1 \), and \( M_d \) refers to the generalized Möbius \(M\)-function over the divisor \( d \) of \( deg(v) \), we have

  1. \(\sum\limits_{v\in V(P_n),\ d|deg(v)}M_d(P_n)=\sum\limits_{v\in V(P_n)}\sum\limits_{d|deg(v)} \mu(d)=2.\)
  2. \(\sum\limits_{v\in V(C_n),\ d|deg(v)}M_d(C_n)=\sum\limits_{v\in V(C_n)}\sum\limits_{d|deg(v)} \mu(d)=0.\)
  3. \(\sum\limits_{v\in V(K_n),\ d|deg(v)}M_d(K_n)=\sum\limits_{v\in V(K_n)}\sum\limits_{d|deg(v)} \mu(d)=0.\)
  4. \( \sum\limits_{v\in V(K_{m,n}),\ d|deg(v)}M_d(K_{m,n})=\sum\limits_{v\in V(K_{m,n})}\sum\limits_{d|deg(v)} \mu(d)= \begin{cases} m& \text{if}\; n=1;\\ 2& \text{if}\; m=n=1;\\ 0& \text{otherwise.} \end{cases} \)
  5. \(\sum\limits_{v\in V(S_n),\ d|deg(v)}M_d(S_n)=\sum\limits_{v\in V(S_n)}\sum\limits_{d|deg(v)} \mu(d) = \begin{cases} 2& \text{if}\; n=2;\\ n-1& \text{otherwise.} \end{cases}\)
  6. \(\sum\limits_{v\in V(W_n),\ d|deg(v)}M_d(W_n)=\sum\limits_{v\in V(W_n)}\sum\limits_{d|deg(v)} \mu(d)=0.\)
  7. \( \sum\limits_{v\in V(K_{m_1,m_2,\dots,m_n}), d|deg(v)}M_d(K_{m_1,m_2,\dots,m_n})=\sum\limits_{v\in V(K_{m_1,m_2,\dots,m_n})}\sum\limits_{d|deg(v)} \mu(d)=0,\) where \( n\ge 3 \).

Proof. The proof is similar to the Theorem 1.

4. Relationships between the generalized Liouville \(\Lambda \)-function and Möbius \( M \)-function

In this section, some relationships between generalized the Liouville and Möbius functions are determined.

Theorem 3. For all \( v\in V(G), deg(v)\ge 1 \), we have \begin{equation*} \begin{aligned} \Lambda(G)=\sum\limits_{v\in V(G)}\lambda(deg(v))&=\sum\limits_{v\in V(G)}\sum\limits_{d^2|deg(v)}\mu\left(\frac{deg(v)}{d^2}\right)=\sum\limits_{v\in V(G)}\sum\limits_{deg(v)=d^2m}\mu(m). \end{aligned} \end{equation*}

Proof. There is only one nonzero term in the sum, as \( \mu\left(\frac{deg(v)}{d^2}\right)=0 \) except when \( \left(\frac{deg(v)}{d^2}\right) \) is the product of distinct primes. Let \( deg(v)={p_1}^{a_1}{p_2}^{a_2}\dots {p_k}^{a_k}.\) If the odd \( a_i^,\)s as \( a_{i_1}, a_{i_2},\dots, a_{i_j}\) are listed. Then \( \left(\frac{deg(v)}{d^2}\right)= p_{i_1}p_{i_2}\dots p_{i_j}\) is the nonzero term. When \( j \) is even, then \( \mu(p_{i_1}p_{i_2}\dots p_{i_j})=1,\) and when \( j \) is odd, then \( \mu(p_{i_1}p_{i_2}\dots p_{i_j})=-1.\) Therefore, for every \( v\in V(G), \) we have \( \lambda(deg(v))=(-1)^{a_1+a_2+\dots+a_k}=(-1)^j.\) Thus the theorem is proved.

Theorem 4. For all \( v\in V(G), deg(v)\ge 1 \), we have \begin{equation*} \begin{aligned} M(G)=\sum\limits_{v\in V(G)}\mu(deg(v))&=\sum\limits_{v\in V(G)}\sum\limits_{d^2|deg(v)}\mu(d)*\lambda\left(\frac{deg(v)}{d^2}\right)=\sum\limits_{v\in V(G)}\sum\limits_{deg(v)=d^2m}\mu(d)*\lambda(m). \end{aligned} \end{equation*}

Proof. The prove follows from the Theorem 3.

Corollary 1. For any vertices \( v\in V(G) \) such that \( deg(v)=p_1p_2\dots p_k \), where \( p_i \) is distinct for all \( i=1,2,\dots ,k, \) we have \( \lambda(deg(v))=\mu(deg(v))=\mu^2(deg(v))(-1)^{\omega(deg(v))},\) where \( \omega(deg(v)) \) is the number of distinct primes of \(deg(v)\).

Proof. The proof is straightforward as \( \lambda \) and \( \mu \) are multiplicative functions and \( deg(v) \) is the product of distinct primes.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflict of Interests

The authors declare no conflict of interest.

References:

  1. Apostol, T. M. (2013). Introduction to analytic number theory. Springer Science & Business Media, NY.[Google Scholor]
  2. Tattersall, J. J. (2005). Elementary number theory in nine chapters. Cambridge University Press, NY.[Google Scholor]
  3. Borwein, P. B., Borwein, P., Choi, S., Rooney, B., & Weirathmueller, A. (Eds.). (2008). The Riemann hypothesis: a resource for the afficionado and virtuoso alike (Vol. 27). Springer Science & Business Media, NY.[Google Scholor]
  4. Salih, H. F. M., & Ibrahim, N. B. (2019). Generalized Euler’s \(\Phi\)-function of graph. New Trends in Mathematical Sciences, 7(3), 259-267.[Google Scholor]
  5. Baker, A. (1984). A concise introduction to the theory of numbers. Cambridge University Press, NY.[Google Scholor]
  6. Burton, D. M. (2006). Elementary number theory. Tata McGraw-Hill Education.[Google Scholor]
  7. Manin, Y. I., & Panchishkin, A. A. (2005). Introduction to modern number theory (Vol. 49). Springer-Verlag Berlin Heidelberg.[Google Scholor]
  8. Beineke, L. W., & Wilson, R. J. (1997). Graph connections: relationships between graph theory and other areas of mathematics. Oxford University Press, Oxford.[Google Scholor]
  9. Balakrishnan, R., & Ranganathan, K. (2012). A textbook of graph theory. Springer Science & Business Media, NY.[Google Scholor]
  10. Shoup, V. (2009). A computational introduction to number theory and algebra. Cambridge university press, Cambridge.[Google Scholor]