# ON THE CENTRALITY OF GENERALIZED PETERSEN GRAPHS P(N,M).

Byline: Imrana Kousar, S.M.Husnine and Saima NazeerABSTRACT

The eccentricity v e of a vertex v in a connected graph G is the distance between v and a vertex farthest from v in G . The radius G rad is the minimum eccentricity of the vertices of G , whereas the diameter G the maximum eccentricity. A vertex v is a central vertex if G rad v e . The center G Cen is the subgraph induced by the central vertices of G . We call G self centered if G G Cen . In this paper, we establish that almost all member of the family of generalized Petersen graphs m n P , are self centered.

1 INTRODUCTION

Determining the diameter of a circulant graph (or any graph for that matter) is a difficult problem. However, Boesh and Wang [2] were able to determine the minimum diameter among all circulants on n vertices and having two jump sizes.

The generalized Petersen graph P(n,m) for n 3 and is a graph consisting of an inner star polygon (circulant graph) and an outer regular polygon ( Cn ) with corresponding vertices in the inner and outer polygons connected with edges. P(n,m) has 2n vertices with vertex set

Equations

It is important to know the exact location of an emergency facility such as a hospital or fire station, we minimize the of a possible emergency. In determining the location for a service facility such as a post office, power station, or employment office, we want to minimize the total travel time for all people in the district. The construction of a railroad line, pipeline, or superhighway, demands the minimization of the distance from the new structure to each of the communities to be served. Each of these situations deals with the concept of centrality [2, 4].

The distance d(u,v) between two vertices u and v in a connected graph G is the length of a shortest u - v path in G. It is known that the distance function satisfies the following properties in any connected graph G.

1. d(u,v) 0 for all u,v V(G)

2. d(u,v)=0 if and only if u=v

3. d(u,v)=d(v,u) for all u,v V(G)

4. d(u,w) d(u,v)+d(v,w) for all u,v,w V(G)

The fact that the distance d satisfies properties 1-4 means that d is a metric and (V(G),d) is a metric space [3, 4]. For a vertex v in a connected graph G, the eccentricity e(v) of v is the distance between v and a vertex farthest from v in G. The minimum eccentricity of the vertices of G is its radius and the maximum eccentricity is its diameter. They are denoted by rad(G) and diam(G), respectively. A vertex v in G is a central vertex if e(v) = rad(G). The subgraph Cen(G) induced by central vertices of G is called the center of G. If every vertex is a central vertex, then Cen(G)=G and G is called self centered. A vertex v in a connected graph G is called a peripheral vertex if e(v) = diam(G). The subgraph of G induced by its peripheral vertices is the periphery of G and is denoted by Per(G).

Now we present a lemma that will be used in our subsequent work.

Lemma 1.1. [3]

The center of the graph is the full graph if and only the radius and diameter are equal.

In this paper, we determine center and periphery for the family of generalized Petersen graphs P(n,m) for all n and 2 Center and Periphery for P(n,m) The automorphism group of a graph is a group of adjacency preserving permutations of its vertices.

The automorphism permutes the vertices of P(n,m) as r(u )=u and r(v )=v.

Also if x and y are vertices of a connected graph G and Aut(G), then d(x,y)=d( (x), (y)) [1,5].Thus to determine the eccentricity of the vertices of P(n,m), it is enough to determine the eccentricity of exactly one vertex on the inner and outer cycle.

Now we present some results regarding the centrality of members of the family of generalized Petersen graphs P(n,1) and P(n,2).

Theorem 2.1. [8]

All the members of the family of generalized Petersen graphs P(n,1) are self centered with

Equations

Theorem 2.2. [8]

All the members of the family of generalized Petersen graphs P(n,2), n 0,2(mod 4) and ngreater than 6 are self centered with

Equations

Theorem 2.3.[8]

For the family of generalized Petersen graphs P(n,2), n 1,3(mod 4), ngreater than 7, the center is a subgraph of P(n,2) induced by the vertices on the inner cycle and periphery is a subgraph of P(n,2) induced by the vertices on the outer cycle. In particular none of the graphs P(n,2) with n 1,3(mod 4), ngreater than 7 are self centered.

Now we establish that P(n,m) is self centered for the remaining values of m.

Theorem 2.4.

For generalized Petersen graph P(n,m), and m 3

Equations

REFERENCES

[1.] N.L Biggs, Algebraic Graph Theory, 2nd ed Cambridge, England: Cambridge University Press, 1993.

[2.] F. Buckley and F. Harary, Distance in Graphs, Addison Wesley, Reading MA, 1990.

[3.] Douglas B. West, Introduction to Graph Theory, Prentice Hall, 1996.

[4.] G. Chartrand and P. Zang, Introduction to Graph Theory, Tata McGraw-Hill, New Delhi, 2006.

[5.] R. Frucht, J.E. Graver and M. E. Watkins, The groups of generalized Petersen graphs, Proc. Cambridge. Philos. Soc. 70(1971),211-219.

[6.] S.M. Husnine and I. Kousar, A subfamily of generalized Petersen graphs P(n,3) with constant metric dimension, Utilitas Mathematica 81(2010),111-120.

[7.] I. Javaid, T. Rahim, and K. Ali, Families of regular graph with constant metric dimension, Utilitas Mathematica 65(2008),21-33.

[8.] I. Kousar and S. M. Husnine, On the centrality of certain graphs, World conference on 21st century Mathematics 2011.

Printer friendly Cite/link Email Feedback | |

Publication: | Science International |
---|---|

Article Type: | Report |

Date: | Jun 30, 2015 |

Words: | 1043 |

Previous Article: | ON CYCLE ANTI-SUPERMAGIC LABELLING OF ISOMORPHIC COPIES OF LADDER AND TRIANGULAR LADDER. |

Next Article: | FACE ANTIMAGIC LABELING OF GENERALIZED KCn SNAKE GRAPH. |

Topics: |