Some (r, 2, K)-regular Graphs Containing A Given Graph.

Some (r, 2, K)-regular Graphs Containing A Given Graph.

N.R.Santhi Maheswari

G.venkataswamy Naidu College, Kovilpatti – 628502. India. nrsmaths@yahoo.com.

C.Sekar

Aditanar College of Arts and Science Tiruchendur-628216.India

Sekar.acas@gmail.com

Abstract

A graph G is called (r, 2 , k ) – regular if each vertex of G is at a distance one from r vertices of G and each vertex of G is at a distance two from exactly k vertices of G. That is , if d(v) = r and d 2 (v) = k , for all v in G [9].This paper suggests a method to construct a ( m + n 1, 2, ( m n 1 ))- regular graph of order m n containing the given graph G of order n 2 as an induced sub graph, for any m 1, and this paper includes existence of some (r , 2 , k )-regular graphs

and few examples of ( 2 , k ) regular graphs.

Keywords: Distance degree regular, Induced subgraph, (d, k)-regular graphs, (2, k) – regular graphs, semi regular graphs.

MATHAMATICS SUBJECT CLASSIFICATION CODE (2010): 05C12.

1. Introduction.

   By a graph we mean a finite, simple, undirected graph. We denote the vertex set and edge set of G byV (G) and

   (G) respectively. The addition of two graphs G1 and G2 is a graph G1+G2 with V(G1+G2) = V(G1)UV(G2) and E(G1+G2) = E(G1)UE(G2) U { uv/u V(G1), v V(G2)}. The degree of a vertex v is the number of vertices adjacent to v and it is denoted by d (v). If all the vertices of a graph have the same degree r, we call that graph r-regular.

   Two vertices u and v of G are said to be connected if there is a (u, v) path in G. For a connected graph G, the distance d (u, v) between two vertices u and v is the length of a shortest (u, v) path in G. In any graph G, d (u, v) =1 if and only if u and v are adjacent. Therefore , the degree of a vertex v is the number of vertices at a distance one from v, and for d a positive integer and v a vertex of a graph G , the d th degree of v in G, denoted by d d (v) – is defined as the number of vertices at a distance d from v. Hence d1 (v) = d (v).

   A graph G is said to be distance d regular if every vertex of G has the same number of vertices at a distance d

   from it [5]. Let us call a graph (dike)-regular if every vertex of G has exactly k number of vertices at a distance d from it

   .That is, a graph G is said to be ( d, k ) – regular graph if d d ( v ) = k , for all v in G .The (1, k) regular graphs and k- regular graphs are the same. A graph G is (2, k) regular if d 2 (v) = k, for all v in G. A graph G is said to be (2, k) regular if

   d 2 (v) = k, for all v in G, where d 2 (v) – means number of vertices at a distance 2 away from v. The concept of semi regular graph was introduced and studied by Alison Northup [2]. We observe that (2, k) – Regular and k semi regular graphs are same.

   An induced sub graph of G is a sub graph H of G such that E(H) consists of all edges of G whose end points belong to V(H).In 1936, Konig [8] proved that if G is any graph ,whose largest degree is r, then there is an r-regular graph H containing G as an induced sub graph.

   The above results motivate us to suggest a method to construct , a ( m + n – 1 , 2, ( mn 1 ))- regular graph H of order mn containing given graph G of order n 2 as an induced sub graph, for any m 1. Terms not defined here are used in the sense of Harary [6] and J.A Bondy and U.S.R .Murty [4].

2. (2, k) – regular graphs

   Definition 2.1. A graph is said to be (2, k) – regular graph if each vertex of G is at a distance two away from exactly k vertices. That is, d 2 (v) = k, for all vertex in G.Note that (2, k) – regular graph may be regular or non regular.

   Examples 2.2.

   Non-regular graph which are (2, k)-regular 2.3.

   (i). Sunflower graph is the graph obtained by starting with an n 5 cycles with consecutive vertices v1 , v2 , v3 , v4 ,vn and creating new vertices w1, w2 , w3 ,wn with wi connected with vi and vi+1 (vn+1 is v1) is (2, 4)- regular. We denote this graph by SFn.

   Proof: Let the vertex set V(SFn)={v1,v2,v3,v4,vn}U{w1,w2,w3,w4,wn} and edge set E (SFn) =E(C) U {VI, wi/ (1 i n).}U {vi+1wi/ (1 i n).}U {v1wn}. Here d2 (vi) =4, d2 (we) =4, for (1 i n)}. Therefore, SFn (n 5) is (2, 4) – regular graph.

   (ii) . For any k 1, let Gk graph obtained from two disjoint copies of K1,k by adding a matching between two partite sets of size kiths graph Gk is (2, k)- regular graph order 2k +2. Graph G5 in Figure 1 is (2,5) – regular graph

   G5

   Figure 1

   Regular graphs which are (2, k) regular 2.4.

   1. Any complete m partite graph K n1, n2, n3, n4, .nm is (2, k) – regular iff n 1 = n2 = n3 = n4, = nm.

   2. Any positive integer n = m k, where m > 1and k 1 are positive integers. Then we construct complete mpartite graph

   n 1

   which is (2,

   m

   ) regular.

   We denote r-regular graphs which are (2, k)-regular by (r, 2, k)-regular graph.

3. (r, 2, k)-regular graph.

   Next, we will see some results related with (r, 2, k)-regular graph that we have already seen in [9], [10], [11], [12].

   Definition 3.1

   A graph G is called (r, 2, k)-regular if each vertex in graph G is at a distance one from exactly r-vertices and at a distance two from exactly k vertices. That is, d (v) = r and d2 (v) = k, for all v in G.

   Example 3.2.

   (3, 2, 0)-regular graph (3, 2, 3)-regular graph (3, 2, 5)-regular graph

   Figure 2.

   The following facts can be verified easily:

   Fact 1 [8] If G is (r, 2, k)-regular graph, then 0 k r (r-1).

   Fact 2 [9] for any r > 1, a graph G is (r, 2, r(r-1)-regular if G is r-regular with girth at least five.

   Fact 3 [9] for any n 5, (n 6, 8) and any r > 1, there exists a (r, 2, r (r-1))-regular graph on n x 2r-2 vertices with girth five.

   Fact 4 [10] for any odd r 3, there is no (r, 2, 1)-regular graph

   Fact 5 [10] Any (r, 2, k) – regular graph has at least k+r+1 vertices.

   Fact 6 [10] If r and k are odd, then (r, 2, k)-regular graph has at least k+r+2 vertices.

   Fact 7 [10] For any r 2 and k 1, G is a (r, 2, k)-regular graph of order r+k+1 if and only if dam (G) = 2.

   Fact 8 [10] For any r 2, there is a (r, 2, (r-1) (r-1))-regular graph on 4 x 2r-2 vertices Fact 9 [10] For r > 1, if G is a (r, 2, (r-1) (r-1))-regular graph, then G has girth four. Fact 10[11] For any r 1, there exist a (r, 2, r-1)-regular graph of order 2r.

   Fact 11[11] For any r 1, there exist a (r, 2, 2 (r-1)) – regular graph of order 4r-2.

   Fact 12[11] For any r 2 , there is a ( r , 2 , ( r – 2 ) ( r- 1 ))- regular graph on 3 x 2r-2 vertices . Fact 13[12] For any r 3 , there is a ( r , 2 , ( r – 3 ) ( r- 1 ))- regular graph on 4 x 2r-3 vertices . Result 3.3.

   For any r > 0, there exists (r, 2, r+n-1) – regular bipartite graph of order 2(r+ n), for (0 n r-1)

   Proof.

   Let r>0, let G be a bipartite graph with the vertex set V(G)={vi, ui/(1 i r+n) }and edge set E(G)= { v i u i,v i ui+j/(1 i r+n) and 1 j r-1)}.Subscripts are taken modulo r + n.This graph G is (r, 2, r+n-1) -regular bipartite graph of order 2(r+n).

   Example 3.3. Figure 3 illustrates the result 3.2, for r = 2, 3.

   When r=2.

   n = 0 n = 1.

   When r=3.

   n=0 n=1 n=2

   Figure 3

4. The (r, 2, k) – regular containing given graph as an induced sub graph.

   Konig [7] proved that if G is any graph, whose largest degree is r, then it is possible to add new points and to draw new lines joinng either two new points or a new point an existing point, so that the resulting graph H is a regular graph containing G as an induced sub graph. We now suggests a method that may be considered an analogue to Konigs theorem for (r, 2, k)) – regular graphs.

   Main theorem 4. 1

   For any m 1 , every graph G of order n 2 is an induced sub graph of ( (n+m-1) ,2, ( mn-1) )- regular graph of order 2mn.

   Proof.

   1 2 3 n r+m r + m

   Let G be a graph of order n 2 with the vertex set V (G) = {v1, v2, v3, vn}. Let G t denote a copy of G with the vertex set V( G t ) = {v t, v t, v t,v t} ,for t =1,2,3, m . Let G denote a copy of G with the vertex set V( G ) =

   2m

   {u1r, u2r , u3r,unr },for r =1,2,3,m ) .The desired graph H has the vertex set V( H ) = V (Gt ) and edge set E(H) =

   t1

   2m m n

   k

   E(Gt) {vjt uit , ujt vit /vj 1vi1V(G1),(1 j n),(j+1 i n)}

   {vk iu i+j/(1i m) and (0 j m-1}. ( Super

   t1

   t1

   k 1

   scripts are taken modulo m).The resulting graph H contains G as an induced sub graph .

   In H , for t =1,2,3,m. d ( vit )= d ( uit ) = m + n -1 and d 2 ( vit ) = d2(uit) = m n – 1, for i= 1, 2, 3,n. That is, H is

   ((m + n -1), 2, mn-1) – regular graph H of order 2mn containing any graph G of order n 2. For any graph of order n 2, there exist ((m+ n -1), 2, mn-1) – regular graph H of order 2mn containing given graph of order n 2 as an induced sub

   graph. Therefore, there are at least as many (m + n – 1), 2, m n – 1) – regular graph of order 2 m n as there are graph of order n 2.

   Example 4.2. Figure 4 illustrates theorem 4.1, for m = 2 and n = 3.

   Figure 4

   Corollary 4.3.

   Every graph G of order n 2, is an induced sub graph of (n, 2, n-1) – regular graph of order 2n.

   Proof.

   This result is the particular case of theorem 4.1, for m = 1.

   1 2 3 n 2 2 1 2 3 n

   Let G be a graph of order n 2 with vertex set V (G) = {v1, v2, v3,.vn}. Let G1 denote a copy of G with the vertex set V(G1)={v 1,v 1,v 1,v 1}.Let G denote a copy of G with the vertex set V(G )={u 1,u 1,u 1,u 1} The desired graph H

   2 2

   has the vertex set V(H) =V (Gt ) and edge set E(H)= E(Gt ) {vj1 ui1 , uj1 vi1 /vj 1vi1V(G1),(1j n),(j+1 i

   t 1 t 1

   n

   n)}

   k 1

   {vk 1u 1 }. The resulting graph H contains G as an induced sub graph.

   k

   i 2 i 2 i

   In H , d (vi1) = d (u 1) = n and d ( v 1 ) = d ( u 1 ) = n-1, for i =1,2,3,n. That is, H is (n, 2, n-1) – regular graph

   of order 2n containing given graph G of order n 2.For any graph of order n 2, there exist (n, 2, (n – 1)) – regular graph H of order 2n containing given graph of order n 2, as an induced sub graph. Therefore, there are at least as many (n, 2, (n- 1)) – regular graphs of order 2n as there are graphs of order n 2.

   Example 4.4. Graphs in Figure 5 illustrates corollary 4.3, for n=3.

   Figure 5

   Corollary 4.5.Every graph G of order n 2, is an induced sub graph of (n+1), 2, 2n-1) -regular graph of order 4n. Corollary 4.6.Every graph G of order n 2, is an induced sub graph of (n+2), 2, 3n-1) -regular graph of order 6n Summary 4.7.

   Therefore, there are at least as many ((n+m-1), 2, (m n-1)) – regular graphs of order 2mn as there are graphs of order n

   2. If m =1, 2 , 3 , 4 ,5n, then we get (n, 2, n-1), (n+1, 2, 2n-1) , (n+2, 2, 3n-1) , (n+3, 2, 4n-1), ( n+4, 2, 5n-1),(

   2n, 2 , n2-1 )- regular graphs of order 2n, 4n, 6n, 8n, 10n2n2.containing given graph G of order n 2 as an induced sub graphs.

   Theorem 4.8.

   Every graph G of order n 2 is an induced sub graph of (n+1, 2, 2n)-regular graph of order 5n.

   Proof.

   Let G be a graph of order n 2 with the vertex set V (G) = {v1, v2, v3, vn}. Let G t denote five copies of G with the

   5

   vertex set V( G t ) = {v1t, v2t, v3t,vnt} ,for t =1,2,3,4,5. The desired graph H has the vertex set V(H)=

   t1

   V(Gt),and

   5

   edgeset E(H)=

   4

   E(Gt)

   n

   {v tv t+1, v 5v 1/ v 1v 1 E(G ) (1j n),(j+1i n)}

   {v iv i+1 , v 5v 1/ (1i4)}.

   t1

   t1

   j i j i j i 1

   k k k k

   k 1

   The resulting graph H contains G as an induced sub graph. Moreover, for (1t5), In H , d(vit) = n+1, d2(vit)= 2n , for (1i n).That is, H is (n+1, 2, 2n) – regular graph with 5n vertices. For any graph G of order n 2, there exists a (n+1, 2, 2n)-regular graph H of order 5n containing given graph G as an induced sub graph. Therefore, there are at least as many (n+1, 2, 2n) – regular graph of order 5n as there are graph G of order n 2.

   Example 4.9. Figure 6 illustrates the Theorem 4.8, for n = 4 (here we take only four graphs of order 4).

   Figure 6

   Corollary 4.10 .Every graph G of order n 2 is an induced sub graph of (n+1, 2, 2n-2) – regular graph of order 3n.

   For, if we take 3 copies of G instead of taking 5 copies of G in Theorem 4.8,then there is (n+1, 2, 2n-2) – regular graph containing every graph G of order n 2.

   Example 4.11. Figure 7 illustrates the Corollary 4.10, for n = 3.

   Figure 7

   Corollary 4.12. Every graph G of order n 2 is an induced sub graph of (n+1, 2, 2n-1)-regular graph of order 4n.

   For, if we take 4 copies of G instead of taking 5 copies of G in Theorem 4.8,then there is (n+1, 2, 2n-1) – regular graph containing every graph G of order n 2.

   Example 4.13. Figure 8 illustrates the Corollary 4.12, for n = 3.

   Figure 8

   Remark 4.14 If we take 6,7,8,. copies of G instead of taking 5 copies of G in Theorem 4.8, then there is only (n+1, 2, 2n) – regular graph of order 6n, 7n, 8n

   References.

   1. Y.Alavi, Gary Chartrand, F. R. K. Chang, Paul Erdos, H. L.Graham and O.R. Oellermann – Journal of Graph Theory, Vol.11, No.2, (1987), 235-249.

   2. Alison Pechin Northup , A Study of Semi-regular Graphs, Preprint.(2002). .

   3. G. S.Bloom. J. K. Kennedy and L.V. Quintas – Distance Degree Regular Graphs in The theory and applications of Graphs, Wiley, New York, (1981) 95 – 108.

   4. J.A.Bondy and Murty U.S.R . Graph Theory with Application MacMillan , London(1979).

   5. Gary Chartrand , Paul Erdos, Ortrud R. Oellerman – How to Define an irregular graph, College Math Journal,39. ( 1998)

   6. Harary , F(1969) Graph theory , Addition Westly.

   7. D. Konig – Theoritic der Endlichen and Unendlichen Graphen,Leipizig (1936). Reprinted Chelsea, New York (1950).

   8. K.R .Parthasarathy, Basic Graph theory, TataMcGraw- Hill Publishing company Limited.New Delhi.

   9. N.R.SanthiMaheswari and C,Sekar, (r, 2, r (r-1))-regular graphs, International journal of Mathematics and Soft Computing, vol. 2.No.2 (2012), 25-33.

   10. N.R.SanthiMaheswari and C,Sekar (r, 2, (r-1) (r-1))-regular graphs, accepted for International journal of Mathematics Combinatorics vol.4. (2012).

   11. N.R.SanthiMaheswari and C, Sekar (r, 2, (r-2) (r-1))-regular graphs, (Communicated).

   12. N.R.SanthiMaheswari and C, Sekar (r, 2, (r-3) (r-1))-regular graphs, (Communicated).