 Open Access
 Total Downloads : 599
 Authors : N.R.Santhi Maheswari, C.Sekar
 Paper ID : IJERTV1IS10467
 Volume & Issue : Volume 01, Issue 10 (December 2012)
 Published (First Online): 29122012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 Tiruchendur628216.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.

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 rregular.
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 rregular 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, 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.
Nonregular 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.

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

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 rregular graphs which are (2, k)regular by (r, 2, k)regular graph.


(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 rvertices 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 (r1).
Fact 2 [9] for any r > 1, a graph G is (r, 2, r(r1)regular if G is rregular 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 (r1))regular graph on n x 2r2 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, (r1) (r1))regular graph on 4 x 2r2 vertices Fact 9 [10] For r > 1, if G is a (r, 2, (r1) (r1))regular graph, then G has girth four. Fact 10[11] For any r 1, there exist a (r, 2, r1)regular graph of order 2r.
Fact 11[11] For any r 1, there exist a (r, 2, 2 (r1)) – regular graph of order 4r2.
Fact 12[11] For any r 2 , there is a ( r , 2 , ( r – 2 ) ( r 1 )) regular graph on 3 x 2r2 vertices . Fact 13[12] For any r 3 , there is a ( r , 2 , ( r – 3 ) ( r 1 )) regular graph on 4 x 2r3 vertices . Result 3.3.
For any r > 0, there exists (r, 2, r+n1) – regular bipartite graph of order 2(r+ n), for (0 n r1)
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 r1)}.Subscripts are taken modulo r + n.This graph G is (r, 2, r+n1) 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

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+m1) ,2, ( mn1) ) 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 m1}. ( 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, mn1) – 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, mn1) – 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, n1) – 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 ) = n1, for i =1,2,3,n. That is, H is (n, 2, n1) – 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, 2n1) regular graph of order 4n. Corollary 4.6.Every graph G of order n 2, is an induced sub graph of (n+2), 2, 3n1) regular graph of order 6n Summary 4.7.
Therefore, there are at least as many ((n+m1), 2, (m n1)) – 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, n1), (n+1, 2, 2n1) , (n+2, 2, 3n1) , (n+3, 2, 4n1), ( n+4, 2, 5n1),(
2n, 2 , n21 ) 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, 2n2) – 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, 2n2) – 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, 2n1)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, 2n1) – 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.

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), 235249.

Alison Pechin Northup , A Study of Semiregular Graphs, Preprint.(2002). .

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.

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

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

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

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

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

N.R.SanthiMaheswari and C,Sekar, (r, 2, r (r1))regular graphs, International journal of Mathematics and Soft Computing, vol. 2.No.2 (2012), 2533.

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

N.R.SanthiMaheswari and C, Sekar (r, 2, (r2) (r1))regular graphs, (Communicated).

N.R.SanthiMaheswari and C, Sekar (r, 2, (r3) (r1))regular graphs, (Communicated).
