Asif Abdur Rehman*and M.Khalid Mahmood
Department of Mathematics, University of the Punjab, Lahore, Pakistan
* Corresponding Author: [email protected]
Divisor function D(n) gives the residues of n which divide it. A function denoted by τ(n) counts the total possible divisors of n and ϕ gives the list of co-prime integers to n. Many graphs had been constructed over these arithmetic functions. Using D(n) and ϕ(n), a well known graph named as divisor Euler function graph has been constructed. In this paper, we use divisor function and anti Euler function ϕ. We label the symbol ϕc(n) to count those residues of n which are not co-prime to n. By using these functions, we find a new graph, called divisor anti-Euler function graph (DAEFG), denoted as G(d(ϕc(n)). Let G(d(ϕc (n))= (V,E) be a DAEFG, where V={di∣ di/n} and E={di dj ∣ gcd(di,dj)≠1}. The objective of this sequel is to introduce and discuss the properties of DAEFG. In this work, we discuss novel classes of proposed graph with its structure using loops, cycles, components of graph, degree of its vertices, components as complete, bipartite, planar, Hamiltonian and Eulerian graphs. Also, we find chromatic number, chromatic index and clique of these graphs.
Keywords: divisor function, divisor Euler function graph, divisor Euler function sub-graph, Euler function graph, metric dimension, resolvent.
The systematic use of number theoretic functions in combinatorial mathematics is an interesting and useful task nowadays. Recently, the study of graphs based on number theoretic functions has become much more motivating. In our work, we use three number theoretic functions and define a new class of graph based on these functions. We familiarize and study the structures of such graphs. Such construction of graphs based on number theory leads to many new useful results. This area of mathematics has a wide range of applications in chemistry, computer science, navigation, robot science and engineering as well. The notion of divisor graph was first introduced by Singh and Santhosh in 2000. In 2015, K. Kannan et al. [1] presented a graph of number theocratic function namely, the divisor function graph. He suggested an idea for constructing graphs on divisors of integers by taking as vertices. We denote the set as the set of positive divisors of . In his contribution, both vertices and edges were based on . Shanmugavelan constructed a graph, namely Euler's phi function graph based on Euler's phi function [2]. He constructed this graph by taking a set of nodes and a set of edges based on this function . Using these co-prime residues, an idea of prime labeling has been introduced and investigated in [3]. Over vertices, the formula for finding the maximal number of edges in this type of labeling has been established as in [3]. The well-known Cayley graph associated with the totient function, known as the Cayley totient graph [4], contains residues modulo namely with the edge set . It is denoted by , where denotes all positive integers which are less than and co-prime to . In the following paragraph, a few definitions are addressed to make this study self-contained.
Metric dimension is an attractive parameter in graph theory. The idea of resolving set for a connected graph was firstly first used by Slater [5] and [6], where he termed it as a locating set. He referred to the least locating set as a reference set and its cardinality as the Metric dimension, which has a wide range of applications in many fields of chemistry computer science physics and robot science. The distance between any two vertices is denoted as which gives the minimum number of edges needed to transverse to reach from to . Let be a graph with one component i.e., a connected graph, a node resolves a pair of vertices and of if . If a subset resolves the whole set of nodes, then is called a resolving set (RS). General results on MD were discussed in [12]. Eccentricity of a particular vertex is defined as the maximum distance between any of the vertices of the graph with that is lies in . Many useful results regarding FMD and LFMD were discussed in [7] and [8], respectively. Results regarding algorithm and graph labeling were discussed in [9-11]. Many results on digraphs and their labeling based on number theory are discussed in [12-15]. Results on upper bound sequence of networks and RN's via Lambert type Map can be seen in [16-18]. Useful results on further graph theoretic applications are widely discussed in [19-21]. Research on degree and connection-based Zagreb indices of the network is astonishing nowadays. Fruitful results of such newly defined degree based topological invariants of the M-polynomial, tadepol graph are discussed in [22] and [23]. Computation of entropy measures and valency-based indices of networks are discussed in [24] and [25]. The results of connection based such indices of networks are given in [26-28].
A loop (or a fixed point) in a graph is a vertex that is adjacent to itself, and it is called an isolated vertex if it is not adjacent to any other vertex. The vertices will form a cycle of length if is adjacent to is adjacent to , and so on till is adjacent to . A maximal connected subgraph is termed as a component. The number of vertices adjacent to a vertex is called its degree. A graph is complete if all vertices are adjacent to the rest of all vertices. A graph is termed as bipartite if its set of vertices can be partitioned into two disjoint sets such that any two vertices in a set are not adjacent to each other. A graph is regular if all vertices have same degree. A graph is said to be planner if it can be drawn on a plane such that no two edges intersect each other except the end points. A graph is termed as Hamiltonian if it has a cycle through all vertices and visits each vertex exactly one time. While a graph is Eulerian if each of its vertex has an even degree. The chromatic number is the smallest number of colors that can be assigned to its vertices such that no two same colors are adjacent or no two adjacent vertices have same color and the minimum number of colors such that no two adjacent edges have same color. Lastly, the order of a maximal complete subgraph is called a clique of that graph. Now, we recall a few well-known definitions and results from number theory which will be used in the sequel to make this paper self-contained. The following definitions can be found in [7].
Definition 1.1. [4] Arithmetic functions are those functions, which are defined for all positive integers, such as Divisor function d(n), Euler Phi function ϕ(n), Tau Function τ(n), Sigma function σ(n) and Anti- Euler function ϕ' etc.
Definition 1.2. [4] Divisor function d(n) is the set of those numbers which are less then or equal to n and which divides n. For example, for =10,d(n)={1,2,5,10}
Definition 1.3. [2] Divisor Euler function graph G=(V,E) is a graph in which set of nodes are based on divisor function and set of edges is based on Euler phi function and any two nodes are adjacent if these are co-prime to each other.
Definition 1.4. [2] Divisor-not prime function graph is a graph in which set of nodes is based on divisor function and any two nodes are adjacent if these are not prime to each other. It is also termed as divisor anti Euler function graph.
Definition 1.5. [4] Divisor Euler function graph denoted by ϕ(n) is a graph in which the number of integers from the set {1,2,…,n-1} are relatively prime to n, i.e., ϕ(n)=1.
Definition 1.6. [4] The number of integers from the set {1,2,…,n-1} which are not relatively prime to n is the function ϕ'(n).ϕ'(n) denotes the numbers that are less than or equal to n and non-prime to n. Since ϕ(n)=n-1 for n be any prime but ϕ'(n)=1, for n=5,ϕ'(n)=1, and ϕ'(8)=4, and these numbers are 2,4,6 and 8 as these are all non-prime to n, i.e., (8,20)≠1,
Theorem 1.1. [4] For any integer n,ϕ(n)=n-1 if and only if n is prime. So, ϕ' (n)=1.
Theorem 1.2. [4] If n is any prime, then ϕ(nk )=n(k-1) (n-1),k≥1.
Theorem 1.3. [4] If m and n are any two co-prime integers, then ϕ(mn)=ϕ(m)ϕ(n).
Definition 1.7. Divisor anti Euler function graph (DAEFG) labeled as G(d(ϕ'(n)) with V={di:di∣n} and E={di dj:gcd(di,dj )≠1,∀di,dj∈V}. The DAEFG for n=8 and n=12 are depicted in Fig. 1.
Figure 1. DAEFG for n=8 and n=12
Corollary 2.1. G(d(ϕ'(n)) has exactly 2 components
Corollary 2.2. deg(v(1))=0.
Corollary 2.3. The largest of any vertex d in DAEFG is τ(n)-2.
Proof: The proof is simple. Since node 1 is isolated which clearly depicts that no other node can have an edge with node 1. So, there are total τ(n)-1 nodes in the connected part of graph. As by definition graph is simple so there is no loop. So, there are τ(n)-2 total number of possible edges incident with node n. Hence, it is the only node with the largest degree which is τ(n)-2. Since SAEFG is a simple graph so there is no loop at any vertex in particular there is no loop at vertex n itself. Since there are τ(n) possible vertices of DAFTG. Also, each di≠1 for each i is adjacent to n (possibly). These di are τ(n)-2 in number (excluding 1 and n), so d must have degree τ(n)-2.
Theorem 2.1 DAEFG is connected and 1 is the only isolated vertex in it. Proof: Let d1,d2,……,d_n all the possible divisors of any positive integer n, where d_n=n. Since 1 divides each integer, then a∈V. By definition (1,di )=1, So 1 cannot join any of the node which means that node 1 is isolated. Now, its only need to show that G is connected. Since each di divide n and which is not co prime to n i.e., (di,n)≥1. So, clearly there is an edge between each di to n. Hence, G is connected. Proof. The proof is simple. Since, the node 1 is isolated which clearly depicts that no other node can have an edge with node 1. So, there are total τ(n)-1 nodes in the connected part of graph. As by definition graph is simple so there is no loop. So, there are τ(n)-2 total number of possible edges incident with node n. Hence, it is the only node with the largest degree which is τ(n)-2. Since, SAEFG is a simple graph so there is no loop at any vertex in particular there is no loop at vertex n itself. Since there are τ(n) possible vertices of DAFTG. Also, each di≠1 for each i is adjacent to n (possibly). These di are τ(n)-2 in no. (excluding 1 and n ), so d must have degree τ(n)-2.
Theorem 2.2.G is always complete for n=2k
Proof: Since, {1,2,22,23,…,2k } be the set of all possible nodes. As deg(1)=0 so node 1 is not adjacent with any other node. By definition of τ there are k+1 total possible divisors. By excluding node 1 there are k total possible nodes. Since node 2 is even and each node is of the power of 2 which is again an even number so each node is adjacent to the node 2k which is the required n. Since the graph is simple so there is neither a loop nor a multi-edge. As each node is adjacent to every other node except itself and the node 1. Hence there are k-1 total possible edges for each node, which is the property of a complete graph by definition.
Lemma 2.1. The graph G is bipartite for n be the product of two distinct primes.
Proof: The proof can be viewed using its definition. For n=pq then V= {1,p,q,pq} be the set of nodes. Since, node 1 is isolated and we take the set of nodes excluding node 1 for the connected part of graph. So, the set of nodes can be split into two disjoint sets as U and V such that U={p,q} and V={pq} with vertex 1 as isolated. As (p,pq)≥1 and (q,pq)≥1 but (p,q)=1, so there are edges as p-pq and q-pq, where there is no edge between p and q.
Corollary 2.4. There does not exist any cycle for G for n=2k.
Theorem 2.3. Let G be a DAEFG and for n=pk qk,k≥2, then ere exist a cycle of length τ(pk qk )-1.
Proof: We will prove this by using increasing powers of these distinct primes. For n=p2 q2, by definition of DAEFG, 1,p,p2,q,q2,pq,p2 q,pq2,p2 q2 are the vertices of G. Since, τ(n)=9,(1,pi )=1, It is easy to note that the set {p,p2,q,q2,pq,p2 q,pq2,p2 q2 } are the only vertices which can contribute a cycle as these vertices are not relatively prime to each other.
(p,p2 ),(p2,pq),(pq,p2 q),(p2 q,pq2 ),(pq2,q),(q,q2 ),@(q2,p2 q2 ),(p2 q2,p) )≈C_8⋅
In this way, the powers of n can be taken up to k times. Also, there is no other possible edge with 1 as isolated node. Hence, we have a cycle of length τ(pk qk )-1.
Theorem 2.4. There exists a cycle of length τ(pk qk rk )-1 in G for =pk qk rk k≥2.
Proof: The proof is a simple consequence Corollary 2.2.
Theorem 2.5. There exist a cycle of length τ(Π(p_(ki)(kr)-1)┤ in for G for n= p1kr p2kr p3kr………..prkr where p1 < p2 < p3 … pr. (Generalized)
Proof. The proof is obvious.
Proof. The proof is obvious.
Definition 2.1. A subgraph H of G is called is called so it is itself a divisor anti-Euler function graph.
Example 2.1. Let G(d(ϕ' (16)) be a DAEFG with vertex set V={1,2,4,8,16}, then H(d(ϕ' (8) with vertex set V ={1,2,4,8} is a sub-graph of G. Also, both H1 and H2 are both DAEFG's.
Remark 2.1.It is obvious that each H is itself G.
Theorem 2.6G is regular for n=2k, irregular otherwise
Proof: Let n=2k for G then by definition of G,V={1,2,22,23,…,2k } be the set of nodes. Also, (1,2i )=1 which gives that 1 is not adjacent with any of the nodes among the set of nodes, i.e., 1 is isolated. Since, 2 is even and each of its power is again even i.e., (2i,2j )≥1 also 2k is again even, which gives that each node is adjacent to every other node which yield that G is a complete graph. Also, degree of each node is same in the connected component of G. By using the result of completeness G is also regular for n=2k. Let G be DAEFG, to show that G is regular, each of its vertices should have the same degree.
Theorem 2.7. G is planar except for n=2k,k≥5.
Figure 2. DAEFSG for n=8 and n=16
Theorem 2.8. G is not Eulerian for any n
Proof: For n≥3, (i) if n=p,τ(n)=2, and D(n)={1,p}. Using definition there is no edge between node 1 and the p which gives a null graph. (ii) Secondly, if it is not prime then it is a composite number, which can be even or odd. (i)Suppose that it is even then, τ(n)=2" " m i.e deg(1)=0 which shows that node 1 is not adjacent with any of the nodes so the max possible degree of other nodes can be deg(di )=τ(n)-1∀di∈d(n), which is not even, which contradicts the necessity condition for elerianity of a graph to have even degree, which gives that G is not eulerian. (ii)On the other hand suppose that n is odd, then there are following possibilities. (i) If τ(n)= even using above statement, the result if obvious. (ii) But, if τ(n)=odd, we have all nodes of degree odd in number and no such trail passing via all edges, which is the required result.
Theorem 2.9. G is Hamiltonian for all n=p1k1 p1k2 p1(k3……….prkr for p1 p2 p3 …
Proof. We will prove this result by definition. For any simple G with more than 3 noes deg(di )+deg(dj )≥n for every pair of non linked nodes di and dj then G is Hamiltonian. Now, for k=2, we have n=p2 q2 d(n)={1,p,p2,q,q2,pq,pq,pq2,p2 q2 }, τ(n)=p, Also deg(1)=0, so other remaining 8 vertices constitutes the graph DAEFG, so deg(p)+deg(q)=10≥n, since p and q are disjoint vertices, i.e (p,q)=1. Hence, is the result. For k=3, we have n=p3 q3, then by definition of DAEFG 1,p,p2,p3,q,q2,q3,pq,p2 q,p3 q,pq2,pq3,p2 q2,p2 q3,p3 q2,p3 q3, are the vertices. Hence τ(n)=16. and {p,p2,p3,q,q2,q3,pq,p2 q,p3 q,pq2,pq3,p2 q2,p2 q3,p3 q2,p3 q3 } be the nodes that contribute in the construction of DAEFG. Using Dirac theorem the result is again true. It is clear that the result seems true for any of distinct primes with generalized powers up to r, which is the required result. Secondly, if n=pk andτ(n)= even also deg(1)=0andτ(n)-{1} nodes form complete graph, which is nowhere Hamiltonian.
Remark 2.2. G(p) is always a null graph.
Corollary 2.5.L(G) is connected.
Theorem 2.10. G is τ(n)-{1} for n=pk.
Proof: Since, G be a DAEFG and using its definition Let G be DAEFG, then by definition of D(n)={1,p,p2,p3,…,pk } be the set of nodes, and τ(n)=k+1. As node is not adjacent with any node i.e., gcd(1,pi )=1. So, in order to color connected part of graph, we need least number of colors to assign to its nodes. For this, if we 1 to node p,2 to node p2 as (p,p2 )>1,3 to node p3, up to son on color _n to node pk. There are exactly k colors required to color the set of nodes as gcd(pi,pj )≥1, which is the required result.
Corollary 2.6. Proof that χ(G(pk)=τ(n)-1.
Proof: The proof is a simple consequence of previous theorem that is colorable for as exactly colors are needed to color its set of nodes. Also, it the least number of possible such coloring.
Theorem 2.11. G is τ(n)-{1}-colorable for any n=p1(k1) p2(k2 ) p3(k3 )………..p_rkr for p1 Proof: Since all primes are relatively prime among each other i.e., (pi,pi )=1 so, they all can be granted with the same color. But it is essential to see that deg(p,p^(ki ) )≥1. In order to grant separate colors to the adjacent nodes, we need r colors as they r in power. Node 1 is in the other part of graph so it can be given among any of the granted color. Also, |D(n)|=|τ(n)| then, τ(n)-{1} nodes are in the connected part of G. So, χ(G)=τ(n)-(r+1). Corollary 2.7. χ(G)=2 for n=p1 p2.for . Proof: It can be shown easily via definition i.e., τ(n)=4. Also, (p1,p2 )=1. By Lemma 2.6 depicts that G≈Kq for n=p1 p2. Also, χ(Kq )=2 which is the required result. Proof. By using the definition of G,D(n)={1,p}. Also, gcd(1,p)=1 and G≈N. In this case, exactly one color is sufficient to give both of the nodes in order to color G. Theorem 2.12. χ' (G)=k for n=2k . Proof: Since, the graph has exactly 2 components with 1 as isolated and 1,p,pk are the τ possible divisors of n, Since, τ(n)-{1} vertices constitutes Kq with even cardinality. As all prime powers are not relatively prime to each other so they are adjacent via edges, so there is no other option but to assign them with a different color. By assigning distinct color to each edge, τ(n)-{1} colors are needed, which is the required result. Corollary 2.8. χ'(G))=2 for n=p1 p2. Proof: As proved earlier in Lemma 2.6 i.e., G≈Kq for n=p1 p2. Using definition of Kq, then its max degree δ then χ' (G)=δ. As D(n)={1,p1,p2,p1 p2 } be the set of nodes and using definition of DAEFG any two nodes are adjacent to each other if gcd(u,v)>1. Then, node (p1 p2 ) is the only node with the max degree which is exactly 2. So, χ' (G)=2. Proposition 2.27. χ'(G)=χ(L(G)). Proof: Since, χ' be the least possible coloring assigned to edges and L(G) is constructed using edges of G using nodes and χ is the least possible coloring assigned to nodes. Thus, it can be easily seen that χ' (G)=χ(L(G)). Proposition 2.28.For n=2k,D(n)={1,2,22,23,⋯,2k } and 1 be the isolated node. Using definition of clique, we need a subset of D(n) for all 2 nodes meet themselves. As gcd(2,pi )=1, there exist a graph on τ(n)-1,p no. of nodes. So, in this way the largest possible clique can be τ(n)-2. For a particular case the graph of DAEFG for n=36 is shown below Remark 2.3. Here are some useful results regarding DAEFG (i) D(G)=1 with least dominating set 1. (ii) deg(1)=0 isolated node. (iii) deg_max(v)= τ(n)-1 (iv) O(G)=2 iff n=p>2. (iv) degmax(v)=0 iff n=p (viii) g(G)=3 Figure 3. CCC(i), for i=1 In this work, we have studied the structure of Divisor Anti Euler Function graph DAEFG. We computed its order, degree of nodes, number of components, length of cycle, its subgraphs and other graph theoretic properties. Furthermore, we found chromatic number, chromatic index, Hamiltonicity, Eulerianity, regularity and bipartiteness. In future, we find DAEFG for any above discussed graph theoretic properties for arbitrary n.3. CONCLUSION
REFERENCES