International J.Math. Combin. Vol.1(2018), 127-137 Equal Degree Graphs of Simple Graphs T.Chalapathi (DepartmentofMathematics,SreeVidyanikethanEng.College,Tirupati-517502,AndhraPradesh,India) R.V M S S Kiran Kumar (DepartmentofMathematics,S.V.University,Tirupati-517502,AndhraPradesh,India) [email protected],[email protected] Abstract: This paper introduces equal degree graphs of simple existed graphs. These graphs exhibited some properties which are co-related with the older one. We characterize graphs for which their equal degree graphs are connected, completed, disconnected but not totally disconnected. We also obtain several properties of equal degree graphs and spec- ify which graphs are isomorphic to equal degree graphs and complement of equal degree graphs. Furthermore, the relation between equal degree graphs and degree Prime graphs is determined. Key Words: Parameters of the graph, simple graphs, equal degree graphs, degree prime graphs, degree graph isomorphism, Smarandachely k-degree graph, Smarandachely degree graph. AMS(2010): 05C25. §1. Introduction The evaluations of new graphs are involving sets of objects and binary relations among them. Sotheconstructionandpreparationofgraphsvariesauthortoauthor,andthusitisdifficultto pin point its formulation to a single source. Thus the graphs discovered many times, and each discovery being independent of the other. For this reason, there are various types of graphs each with its own definition. Many authors, starting from 2003, the parameters vertex degree and degree sequence of graphs were used again in Graph theory, and severaltypes of graphs have been introduced. In this sequel we have introduced equal degree graphs of various simple graphs and characterized their properties. For any finite group G, the definition and notation of degree graph of a simple group was introduced by Lewis and white [5]. This graph is defined as follows: Let G be a finite group and let cd(G) be the set of irreducible character degrees of G. Then the degree graph △ (G) is the graph whose set of vertices is set of primes that divide degrees in cd(G), with an edge between p and q if pq divides a for some a cd(G). ∈ 1ReceivedSeptember 25,2017,Accepted March6,2018. 128 T.ChalapathiandR.VMSSKiranKumar In[6],theauthorsintroducedthedegreepatternofafinite groupGanddenotedbyD(G), where D(G) = (deg(p ),deg(p ), ,deg(p )), here p < p < < p are distinct primes in 1 2 k 1 2 k ··· ··· prime decomposition of n. Further, the authors S.F.Kapur, Albert and Curtiss [7] introduced thenotationD(G)fordegreesetsofconnectedgraphs,trees,plannerandouterplannergraphs. According to these authors, the notation D(G) is a degree set of degrees of vertices of G. The authors Manoussakis, Patil and Sankar [8] was proved that for any finite non empty set S of non negative integers, there exist a disconnected graph G such that D(G) = S, and also the minimum order of such a graph is determined. There are several ways to produce new graphs from the existing graphs in Graph theory. Recently the authors M.Sattanathan and R.Kala [1] introduced a special way to produce the degree prime graph DP(G) for any finite simple undirected graph G. The PD(G) of a graph G having the same vertex set of G and two vertices are adjacent in PD(G) if and only if their unequal degrees are relatively prime in G. By the motivation of these degree prime graphs, we construct and study the equal degree graphs of simple graphs with usual notation D(G). We suspect that these graphs will be used to solve many computational problems in computer engineering and applied sciences. Throughout this paper, G and D(G) represent finite simple undirected graphs having withoutloopsandwithoutmultipleedgesofsameorder. WehaveintroduceddegreegraphD(G) of G, which is defined as a graph with same vertex set as G and two vertices of G are adjacent in D(G) if and only if their degrees are equal in G. In this paper we studied interrelations between G and D(G), and hence we obtain several properties and their consequences of D(G) withillustrationsandexamples. FurtherwecharacterizeGforwhichD(G)eitherisconnected, disconnected, totally disconnected or complete. §2. Basic Definitions and Notations In this section we consider basic definitions and their graph theoretical notations. Throughout thetext,weconsiderGisanabstractgraphstructurewhichisafiniteundirectedgraphwithout loops and multiple edges. We representG as G=G(V,E) with vertex set V =V(G) and edge set E =E(G). We are only going to deal with finite graphs, so we define V =n to the order | | of G and E = m to be the size of G where n and m are called graph parameters. Further if | | there is an edge e in G between the vertices u and v, we briefly write e=uv or e=(u,v) and say edge e joins the vertices u and v. A vertex is said to be isolatedif it is not adjacent to any other vertex. The complement of a graph G(V,E) is the graph Gc(V,Ec) having the same vertex set as G, and its edge set Ec is the complement of E, that is, uv is an edge of Gc if and only if uv is not an edge of G. A complete graph of order n is denoted by K . A graph of order n with no n edgesinanemptygraphandisdenotedbyN =Kc whichisomorphicto totallydisconnected. n n A path of length n is denoted by P . A cycle of length n(n > 3) is a cycle of length n and is n denoted by C . n We now turn to graphs whose vertex sets can be partitioned in special ways. A graph G is a partite graph if V(G) can be partitioned into subsets, called partite sets. A graph G is EqualDegreeGraphsofSimpleGraphs 129 a k partite graph if V(G) can be partitioned into k subsets V ,V , ,V (partite sets) such 1 2 k − ··· that uv is an edge of G if u and v belongs to different partite sets. In addition, if every two vertices in different partite sets are joined by an edge, then G is a complete k partite graph. − If V =n for 16i6k, then we denote this complete k partite graph by K . Thus | i| i − n1,n2,···,nk (1) K =K ; 1,1, ,1 ∼ n ··· (2) K is a complete bipartite; n,n (3) K is a Star; 1,n (4) K is a complete bipartite. n1,n2 In a graph G, the degree of a vertex u is the number of edges of G which are incident to u and denoted by d(u), deg(u) or deg (u). A graph is regular if all its vertices are of the G same degree and r regular if all of its vertices are of degree r. A 3 regular graph is a cubic − − graph Q . If d ,1 6 i 6 n, be the degree of the vertices v of a graph G then the sequence 8 i i d(G) =(d ,d , ,d ) is the degree sequence of G. Usually, we order the vertices so that the 1 2 n ··· degree sequence is monotonically increasing, that is, δ(G)=d d d = (G). Also 1 2 n ≤ ≤···≤ △ two graphs with the same degree sequence are said to be degree equivalent. We need the following results for preparing equal degree graphs. Theorem 2.1([2]) The sum of the degrees of graphs is even, being twice the number of edges. Theorem 2.2([2]) In any graph there is an even number of vertices of odd degree. Theorem 2.3([2]) If d ,d , ,d is the degree sequence of some graph, then, necessarily 1 2 n ··· ni=1di is even, and 0≤di ≤n−1 for 1≤i≤n. But converse is not true. P Theorem 2.5([2]) Let G be a graph of order n 2, then d(G) contains at least two numbers ≥ are same. rn Theorem 2.6([2]) Let G be a r-regular graph of order n. Then E(G) = . | | 2 Theorem 2.7([3]) Let G be a r-regular graph of order n. Then Gc is (n r 1)-regular graph − − of order n. Theorem 2.8([3]) A graph is 1 regular if and only if it is of even order and is the disjoint − ′ union of some K s. 2 If n = 1, then G is called trivial graph, otherwise G is called non-trivial graph. In this paper we consider non-trivial graphs only. For further details and notations we refer [4]. §3. Equal Degree Graphs We havealreadymentionedthatthe bestknownparametersofa graphareorderandsize. But anotherparameterofagraphis degreeofa vertexwhichis ameaningfulto havea termforthe number of edges meeting at a vertex. By using this parameter we define equal degree graphas follows. 130 T.ChalapathiandR.VMSSKiranKumar Definition 3.1 Let G be a simple graph with vertex set V = 1,2, ,n ,n > 1, Then the { ··· } equal degree graph of G is D(G) having the same vertex set as G and two vertices u,v V are ∈ adjacent in D(G) if and only if deg (u)=deg (v). G G Generally, we know Smarandachely k-degree graphs D G of a graph G in which vertices k u,v V are adjacent if and only if deg (u) deg (v) =k for integers k ∆(G) δ(G) and G G ∈ | − | ≤ − Smarandachely degree graph SG in which u,v are adjacent if deg (u) deg (v) 1. Clearly, G G | − |≥ D G=DG. The definition of equal degree graphs should be noted that the following. 0 1. D(G) is a non-trivial graph; 2. D(G) has at least one edge; 3. D(G) is also a simple undirected graph having without multiple edges. The following Fig.1 shows that simple graphs and their equal degree graphs of order 4. Fig.1 Graphs and their equal degree graphs We now characterize graphs G for which D(G) is either regular or not. The following propositions are immediate. Proposition 3.2 For any graph G, the graph D(G) is never a 0 regular graph. − Proof Suppose D(G) is a 0 regular graph. Then its degree sequence is d(D(G)) = − (0,0, ,0) for any graph G. This shows that D(G) is isomorphic to empty graph, and thus ··· D(G) is a trivialgraph, whichis a contradictionto the definition ofequal degree graphs. Thus the result follows. 2 EqualDegreeGraphsofSimpleGraphs 131 Remark 3.3 (i) D(G) is 1-regular if and only if D(G) is a graph of order 2. (ii) D(G) is 1-regular if and only if G is a graph of order 4 and d(G)=(0,0,1,1) or (2,2,3,3). Proposition 3.4 For any graph G of order n > 4, D(G) is never 1 regular. In particular, − D(G) is never 2,3, ,(n 2)-regular. ··· − Proof SupposeGisagraphwithsizen>4. WeshowthatD(G)isnot1 regular. Assume − that D(G) is 1 regular. Then the degree sequence of G is d(D(G))=(1,1, ,1)(n times). − ··· even, if n is even (1+1+ +1)(n times)= ··· odd, if n is odd   Case 1. If n is odd, then 1+1+ +1(n times) is odd, which contradicts to the Theorem ··· 2.2. So in this case the result is not true. Case 2. If n is even, then 1+1+ +1(n times) is odd, which is impossible because the ··· graph D(G) does not contain an even number of vertices of same odd degree. From the above cases our assumption is not true, and hence D(G) is never 1 regular for − any graph G of order n>4. 2 Remark 3.5 SimilarlywecanshowthatD(G)isnever2-regular,3-regular, ,(n 2)-regular ··· − but it should be (n 1)-regular. − Theorem 3.6(Fundamental Theorem) For any graph G of order n, the degree graph D(G) is either complete or disconnected but not totally disconnected. Proof Suppose D(G) is totally disconnected. Then obviously D(G) is isomorphic to N . n But by the definition of degree graph, D(G) is never isomorphic to N . Hence D(G) is not n totally disconnected. NowweprovethatD(G)iseithercompleteordisconnected. SupposeD(G)isdisconnected. Thenthereisnothingtoprove. IfpossibleassumethatD(G)isconnected,thentheProposition 3.4 and Remark 3.5 shows that D(G) is (n 1)-regular,and hence D(G) is complete. − 2 §4. Complete Equal Degree Graphs In this section we are going to prove that the equal degree graphs are complete. Further we characterize graphs G for which D(G) is complete and also we show that G=D(G). ∼ Proposition 4.1 The degree graph of regular graph is complete. Proof Let V be a vertex set of r-regular graph G. Then the degree sequence of G is d(G)=(r,r, ,r), that is, d(i)=r for each 1 i n. We show that D(G) is complete. For ··· ≤ ≤ this let i,j V, i = j, then deg(i) = r and deg(j) = r. Therefore, deg(i) = deg(i), for all ∈ 6 i=j in V(G). Thus i and j are adjacent in D(G). This shows that every two distinct pair of 6 132 T.ChalapathiandR.VMSSKiranKumar vertices is joined by an edge in D(G). Hence D(G) is complete. 2 This proposition has a number of useful consequences. Corollary 4.2 Let G be a connected graph of order n > 4. Then D(G) is either complete or disconnected. Proof The proof is divided into cases following. Case 1. Suppose G is a connected regular graph of order n > 4. Then, by the Proposition 4.1, D(G) is complete. Case 2. Suppose G is a connected but not regular. Then the degree sequence of G contains at least two distinct positive integers, say s and t. That is, if u,v G, then deg(u) = deg(u) ∈ 6 implies u is not adjacent to v in D(G). Hence D(G) is disconnected. 2 Corollary 4.3 For each n>1, we have (i) D(K )=K ; n n (ii) D(C )=K ; n n (iii) D(N )=K ; n n (iv) D(K )=K ; n,n 2n (v) D(Q )=K . 8 8 Proof (i) The complete graph K is (n 1)-regular,and thus D(K )=K . n n n − (ii) For each n 3, the cycle C is 2-regular. Hence D(C )=K . n n n ≥ (iii) For each, the empty graph N is 0-regular graph. Hence D(N )=K . n n n (iv) Since the completed bipartite graph K is n-regular and the order of K is 2n. n,n n,n Thus D(K )=K . n,n 2n (v) Q is 3-regular of order 8, and thus D(Q )=K . 8 8 8 2 Corollary 4.4 Let Gc be the complement of r-regular graph G of order n, then D(G) = D(Gc)=K . ∼ n Proof We deduces this consequence from the Theorem 2.6 and Proposition 4.1 as follows. We know thatG is r-regulargraphoforder n if andonly if Gc is (n r 1)-regulargraph − − of same order n. Thus the Proposition 4.1 shows that D(G)=K if and only if D(Gc)=K . ∼ n ∼ n Hence D(G)=D(Gc)=K . ∼ n 2 Corollary 4.5 Let G be any graph of order n. For fixed m Z, if there exists an integer n ∈ such that deg(v)=mn for each vertex v of G. Then, D(G)=K . n Proof Obviously follows from Proposition4.1,since G is mn-regular graph of order n. We now characterize the graphs G which attain bounds for E(D(G)). We know that | | n(n 1) 0 E(G) − ≤| |≤ 2 EqualDegreeGraphsofSimpleGraphs 133 for any simple graph G of order n 1. But the following result specifies that the bounds for ≥ E(D(G)). | | 2 n(n 1) Theorem 4.6 If G is any graph of order n>1, then 0< E(G) − . | |≤ 2 Proof From the definition of equal degree graphs, V(G) = V(D(G)) = n, and n > 1. | | | | For any non-trivial graph G, we have deg u (n 1) for each u V(G). This is also true in G ≤ − ∈ D(G), that is, deg u (n 1) for each u V(D(G)). From Theorem2.1 we have D(G) ≤ − ∈ n(n 1) 2E(D(G)) = deg(u) 2E(D(G)) 6n(n 1) E(D(G)) 6 − . | | ⇒ | | − ⇒| | 2 d∈VX(D(G)) It is one extreme of the required inequality. At the other extreme, a degree graph D(G) may possess at least one edge at all. That is, E(D(G)) =0. Hence | |6 n(n 1) 0< E(G) − . | |≤ 2 2 Remark 4.7 The above inequality says that the following two specifications for D(G): (1) D(G) or D(Gc) has at least one edge or at most n edges; 2 (2) D(G) is never totally disconnected. In particular, D(G) ≇ N for each G of order (cid:0) (cid:1) n n>1. Corollary 4.8 Let G be a r-regular graph of order n>1. Then rn n E(G) = and E(D(G)) = . | | 2 | | 2 (cid:18) (cid:19) Proposition 4.9 Let G be a graph of order n. Then E(G) = E(D(G)) if and only if G and | | | | D(G) are (r 1)-regular graphs. − Proof Let G be a r-regular graph of order n>1. By the Corollary 4.7, rn n E(G) = and E(D(G)) = . | | 2 | | 2 (cid:18) (cid:19) Therefore, rn n rn n(n 2) E(G) = E(D(G)) = = − =n 1 G | | | |⇔ 2 2 ⇔ 2 2 ⇔ − ⇔ (cid:18) (cid:19) is (n 1)-regular,and hence D(G) is also (n 1)-regular. − − 2 Proposition 4.10 If Gc is a complement of G, then D(Gc)=D(G). Proof Let Gc be the complement of a graph G of order n > 1. Then the following cases arise on the regularity of G. 134 T.ChalapathiandR.VMSSKiranKumar Case 1. Suppose G is a regular graph. Then the result obviously follows from Proposition 4.1. Case 2. Suppose G is not a regular graph. We show that D(Gc)=D(G). If possible assume that D(Gc)=D(G), then the following three subcases arise. 6 Subcase 2.1 If V(D(Gc))=V(D(G)) then obviously V(Gc)=V(G), which is a contra- 6 6 diction to the fact that V(Gc)=V(G). Subcase 2.2 If E(D(Gc))=E(D(G)), then V(D(Gc))+V(D(G))= n(n−1). This shows 6 2 that either D(G) or D(Gc) has at most n(n−1) edges, which is a contradiction to the fact that 4 D(G) or D(Gc) has at most n(n−1) edges. 2 Subcase 2.3 IfV(D(Gc))=V(D(G)), E(D(Gc))=E(D(G)), thentriviallyitisnottrue 6 6 from cases 2.1 and 2.2. From the above three subcases 2.1, 2.2 and 2.3, we conclude that D(Gc) = D(G) is not 6 true. Hence D(Gc)=D(G). 2 Remark 4.11 The converseofthe aboveresultisnottrue. Forexample,D(N )=D(Nc) but n n N =Nc. n 6 n Theorem 4.12 Let G and G be same regular graphs of order n. Then D(G )=D(G ). But 1 2 1 2 converse is not true. Proof Suppose G and G be regulargraphsofsame order n>1. By the Proposition4.1, 1 2 D(G ) = K and D(G ) = K , and thus D(G ) = D(G ). But converse of this result is not 1 ∼ n 2 ∼ n 1 2 true. This illustrates the Figure 2. Consider the graphs G and G on four vertices and their 1 2 degree graphs. 2 Fig.2 Graphs G , G , D(G ) and D(G ). 1 2 1 2 Theorem 4.13 Let G and G be graphs of same order n>1 such that d(G )=d(G ). Then 1 2 1 2 D(G )=D(G ). But converse is not true. 1 2 Proof Suppose G and G be non-regular degree equivalent graphs of same order n > 1. 1 2 Then their degree sequences are equal. That is, d(G ) = d(G ) = (d ,d , ,d ) where 1 1 1 2 n ··· d 6d 6 6 d , 06 d 6n 1 for each 16 i6n. By the definition of degree graphs, G 1 2 n i 1 ··· − and G (G =G ) are both realize same degree graph, that is, D(G )=D(G ). 2 1 2 1 2 6 EqualDegreeGraphsofSimpleGraphs 135 Converse of the Theorem 4.13 is not true, in general. For the degree sequences d(G ) = 1 (2,2,2,2) and d(G )=(3,2,3,2), we have D(G )=D(G ) implies that d(G )=d(G ). 2 1 2 1 2 6 2 Theorem 4.14 If G and G are two graphs such that G = G , then D(G ) = D(G ). But 1 2 1 ∼ 2 1 ∼ 2 the converse is not true. Proof Suppose G =G . Then there exists anisomorphismϕ fromG ontoG . We show 1 ∼ 2 1 2 that D(G )=D(G ). For this let (u,v) E(D(G )), then by the definition of degree graphs, 1 ∼ 2 ∈ 1 deg u=deg v deg ϕ(u)=deg ϕ(v) (ϕ(u),ϕ(v)) E(D(G )) D(G )=D(G ). G1 G1 ⇒ G2 G2 ⇒ ∈ 2 ⇒ 1 ∼ 2 But converse of this result is not true. For example, D(N )=D(C ) but N ≇C . 4 ∼ 4 4 4 2 §5. Disconnected Equal Degree Graphs In this section we characterize the graphs G for which D(G) is disconnected. Theorem 5.1 Let G be a graph of order n+k. Then D(G)=K N where n is the number ∼ n∪ k of vertices of same degree and k is the number vertices of unequal degree. Proof Let V(G) =n+k.ThenV canbepartitionedintotwosubsetsS andS suchthat 1 2 | | S = u ,u , ,u and S = v ,v , ,v where deg u = deg u for all 1 6 i = j 6 n 1 1 2 n 2 1 2 k G i G j { ··· } { ··· } 6 and deg v = deg v for all 1 6 i = j 6 k. By the definition of Degree graphs, < S >= K G i 6 G j 6 1 ∼ n and <S >=N . Hence D(G)=K N . 2 ∼ k ∼ n∪ k 2 This theorem gives the following consequences. Corollary 5.2 D(P )=<S > <S > where <S >=K and <S >=K . n 1 ∪ 2 1 ∼ 2 2 ∼ n−2 Proof Let v and v be the internal and external vertices of the path P : v e v e v 1 n+1 n 1 1 2 2 3 v e v . Then the vertex set V = V(P ) can be partitioned two disjoint sets S and S n n n+1 n 1 2 ··· such that S = v ,v and S = v ,v , ,v . 1 1 n+1 2 1 2 n { } { ··· } Case 1. In this case deg v = deg v = deg v for j = 2,3,..,n. This shows that there G 1 G n+1 G j 6 exists only one edge between v and v in S , and which are not adjacent to the vertices in 1 n+1 1 S . Thus the degree graph of S is an induced sub graph <S > which is isomorphic to K . 2 1 1 2 Case 2. Suppose v ,v S for every i = j. Then deg v = deg v = 2 = 1 = deg v = i j 2 G i G j G 1 ∈ 6 6 deg v for each i=j such that 26i,j 6n. Thus the degree graphof S is also an induced G n+1 2 6 subgraph <S > which is isomorphic to K . 2 n 2 − Case 3. Suppose u S and v S . Then there is no edge between u and v in the equal 1 2 ∈ ∈ degree graph whose vertex set is V =S S since deg u=1=2=deg v. 1 2 G G ∪ 6 From the cases 1, 2 and 3 we conclude that D(P ) is disconnected with two disjoint n components <S > and <S >. 1 2 2 The proofs of the following consequences are obvious. Corollary 5.3 The following results on D(G) are true: 136 T.ChalapathiandR.VMSSKiranKumar (1) D(K )=K K ; 1,n 1 n 1 ∪ − (2) D(K )=K K K ; n1,n2,···,nk n1 ∪ n2 ∪···∪ nk (3) D(W )=K K . n 1 n 1 ∪ − Corollary 5.4 Let G be a graph of order p+q. Then D(G)=K K where p is the number p q ∪ of vertices of same degree and q is the number of vertices of another same degree. Corollary 5.5 Let T be a tree of order n +n +n . Then D(T) = K K K where 1 2 3 n1 ∪ n2 ∪ n3 n is the number of pendent vertices, n is the number of non-pendent vertices of same degree 1 2 and n is another non-pendent vertex of another same degree. 3 Theorem 5.6 Let D be a connected Euler graph. Then D(G) is either complete or disjoint union of complete components. Proof Consider the two cases on the regularity and non-regularity of a connected Euler graph G. Case 1. Let G be a regular graph. The Proposition4.1 shows that D(G) is complete. Case 2. Let G be a non- regular graph of order n +n + +n . Then n is the number 1 2 k 1 ··· of vertices of degree 2, n is the number of vertices of degree 4, and so on n is the number of 2 k vertices of degree 2k. The Theorem 5.1 shows that D(G) is isomorphic to the disjoint union of complete components K ,K , ,K . Hence D(G)=K K K . n1 n2 ··· nk n1 ∪ n2 ∪···∪ nk 2 Example 5.7 For each n>3, the cycle C is a regular Euler graph, and thus D(C )=K . n n n Example 5.8([3]) The graphs D and M are the Davids and Mohammeds graphs of order 12 16 12 and 16 respectively, which are non-regular Euler graphs, and their Degree graphs D(D )= 6 ′ ′ K K and D(M )=K K , which are disconnected graphs. 6∪ 6 11 4∪ 7 Theorem 5.9 Let G be a simple graph of order n > 4. Then D(D(G)) = D(G) G is ∼ ⇔ r-regular graph. Proof For any simple graph G of order n > 4, we have G is r-regular D(G) = K , ⇔ ∼ n by the Proposition 4.1 D(D(G)) = D(K ) D(D(G)) = K (since D(K ) = K ) ⇔ ∼ n ⇔ ∼ n n n ⇔ D(D(G))=D(G). ∼ 2 §6. Relation Between D(G) and DP(G) In [1], the authors M. Sattanathan and R. Kala introduced Degree prime graphs and studied their characterizations. According to these authorsDP(G) is a graphwhose vertex setis same as V(G) and u,v V(G) are adjacent in DP(G) if and only if ∈ deg u=deg v, gcd(deg u, deg v)=1. G G G G 6 Inthispaper,wearegoingtostudytherelationbetweenD(G)andDP(G). Fundamentally we observe that the following: