[PDF] Research Article DISTANCE IN GRAPH THEORY AND ITS

View - Download Research Article DISTANCE IN GRAPH THEORY AND ITS

Previous PDF

Next PDF

International Journal of Advanced Engineering Technology E-ISSN 0976-3945 IJAET/Vol.II/ Issue IV/October-December, 2011/147-150

Research Article

DISTANCE IN GRAPH THEORY AND ITS APPLICATION

Mahesh C. Prajapati

Address for Correspondence

Assistant Professor, Shree Saraswati Education Sansthan"s Group of Institutions,

At & Po.: Rajpur, Ta. Kadi, Dist. Mehsana

ABSTRACT

I will be define the distance partition of a finite graph and show how this partition being equitable follows from and/or implies

properties of the graph. In the process I will connect this partition to a number of fundamental ideas in graph theory and confirm

an elementary identity of strongly regular graphs.

KEYWORDS

Length of a path, Distance in graph theory, Eccentricity, Radius and Diameter of a graph, Center vertex, Center of a graph.

INTRODUCTION

We see that how a graph can be used to model the street system of a town. Of course, as a town grows in size, so too does not the graph at model it. As a reminder, we see in below figure the street system of a town T and a

Graph G

T that model it.

Town T GT: Graph modeling

Town T

For example when a town is small, it might be appropriate to rely on and pay for the services of the fire department of a neighboring city. As a town grows in to a city (and it able to affords It.), new question arise, it becomes necessary for that town to have its own fire department. Assuming that the decision has been made by the town to build its own firehouse, we now have another question: Where in the town should we build it? Let"s assume that we decide to build the firehouse at some street intersection in the town. This how much, doses not answer our question. Of course, the main reason for building the firehouse is so that all citizens of the town are protected in the event of the fire. Consequently, no location in the town should be too far from this new firehouse. We see that answering our question concerns distance in town T and there for Distance in the graph GT as well.

For this first we define distance & some basic

definitions of a Graph Theory.

Definition:- A Graph or a general Graph

A Graph (G) or a general Graph (G) consists of a nonempty finite set V (G) together with a family E(G) of unordered pairs of element (not necessarily distinct) of the set. We may write G = (V (G), E (G)). Definition:- Vertices & Edges If G = (V(G) , E(G)) is a graph then the set V(G) is said to be the vertex set of the Graph G and the member of V(G) are said to be the Vertices of the Graph. The family E (G) is said to be the age family of the graph (G) and the members of E (G) are said to be the edges of the Graph G.

Example:

Let V={1,2,3,4,5} & E = { (1,1),(1,3),(1,2),(1,2), (1,4),(2,5),(2,3),(3,4),(4,5),(5,5) } then G = (V,E) is a

Graph.

Here V(G) = V is the vertex set of G and 1,2,3,4,5 are the vertices and E(G) = E is edge family of G and (1,1), (1,3), (1,2) twise, (1,4), (2,5), (2,3), (3,4), (4,5), (5,5) are edges. This graph may be represented by the following diagram.

Definition:- A Simple Graph

A simple Graph (G) consists of a nonempty finite set V (G) together with a set E(G) of unordered pairs of distinct element of the set V(G).

We may write G = (V (G), E (G)).

Example:

Let G = (V(G),E(G)) where V = V(G) = {a, b, c, d, e, f} and E = E(G) = { ab, bc, cd, ef } then G is a simple

Graph.

International Journal of Advanced Engineering Technology E-ISSN 0976-3945 IJAET/Vol.II/ Issue IV/October-December, 2011/147-150

Definition:- A walk

A walk in a graph G is a finite sequence of edges of the form v

0v1, v1v2, v2v3. . . Vm-1vm. Also denoted by v0 →

v

1 → v2 → . . . → vm-1 → vm, in which any two

consecutive edges are adjacent or identical. Such a walk determines a sequence of vertices v

0, v1, v2, . . . , vm-1,

and v m. (Here two consecutive vertices are adjacent or identical).

Here v

0 is said to be initial vertex of the walk & vm is

said to be the terminal vertex of the walk.

Definition: - Length

The no. of edges in a walk is said to be the length of the walk. i.e. the length of the walk is the no. of term of that sequence.

Definition: - Trail

If all the edges in a walk are distinct then such a graph is said to be a Trail.

Definition: - Path

If all the vertices v

0, v1, v2. . . vm in a trail are distinct

(except possibly v

0 = vm) then such a trail is said to be a

path. Definition: - A walk or a Trail or a Path is said to be a close if initial vertex & the final vertex are identical.

Definition: - The Union of Graphs.

If G

1 = (V(G1), E(G1)) & G2 = (V(G2), E(G2)), where

V(G

1) ∩ V(G2) = х . Then their union is denoted by

G

1U G2 & it is the graph with the vertex set V(G1) U

V(G

2) & the edge family E(G1) U E(G2).

Definition: - A connected Graph

A Graph is said to be a connected graph if it can not to be expressed as the union of two Graphs.

Definition: - Distance

For two vertices u &v in a graph G, the distance from u to v is denoted by d (u, v) & defined as the length of a shortest u-v path in graph G. For connected Graph G the term distance we just defined satisfies all four of the following properties.

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

2) d (u, v) = 0 iff u = v.

3) d (u, v) = d (v,u) for all u, v € V(G) (The symmetric property).

V(G).(The triangle inequality).

If graph G is not a connected & suppose G

1 & G2 are

two graphs of G such that G = G

1 U G2 & E (G1) U E (G2).

& G1∩ G2 = х i.e. V (G

1) ∩ V (G2) = х &

E (G

1) ∩ E (G2) = х

Then d (u, v) = ∞ for u € V (G

1) & v € V (G2).

Under this distance function, the set V(G) is a metric space & it is denoted by (V(G),d ) , there are several references which we shall make to this distance function, however in this section we describe some concepts which are intimately related to distance and which are of interest in their own right.

Definition:-Eccentricity of a Vertex V in graph G The eccentricity e (v) of a vertex v of a connected graph

G is the number

Definition: - Radius of a graph G

The radius of a graph G is denoted by rad G and is defined as rad G =

Definition: - Diameter of a graph G

The diameter of a graph G is denoted by

diam G =

It follows that diam G =

Definition: - Center of graph G

A vertex v is a central vertex if e (v) = rad G.

And the center of G consists of its central vertices. The radius & diameter are related by the following inequality. consequences of the definitions since the smallest eccentricity can not exceed the largest eccentricity. In order to verify the second inequality select vertices u & v in graph G such that d (u, v) = diam G.

Further more, let w be a central vertex of G

i.e. e (w) = rad (G)

Since d is a metric on V (G).

(G)

Definition: - Adjacent vertices

Two vertices u & v of a Graph G are said to be Adjacent vertices if there exists an edge joining them. And we say that the vertices u &v are incident with the edge uv.

Theorem:-

For every two adjacent vertices u & v in a connected Proof:- Assume, without loss of generality, that e (u) ≥ e(v).

Let x be a vertex that is farthest from u.

So, d (u, x) = e (u).

By the triangle inequality,

Theorem: - Every Graph is the center of some graph. Proof:- Let G be a Graph. We shall show that G is the center of some graph. First, add two new vertices u & v to G & join them to every vertex of G but not to each other.

Next, we add two other vertices u

1 &v1, where we join

u

1 to u & join v1 to v.

International Journal of Advanced Engineering Technology E-ISSN 0976-3945 IJAET/Vol.II/ Issue IV/October-December, 2011/147-150

The resulting Graph is denoted by F.

Since e (u

1) = e (v1) = 4, e (u) = e (v) = 3, & e(x) = 2

for every vertex x in G. It shows that V (G) is the set of central vertices of F & so, Cen (F) =G Hence the proof that every graph is a center of sub graphs.

Definition: - Peripheral vertex

A vertex v in a connected Graph G is called a peripheral vertex if e (v) = diam (G). Thus in a certain cense, a peripheral vertex is opposite to a central vertex. The sub graph of G induced by peripheral vertices is the periphery. This is denoted by per (G).

Example:-

rad (H) = 2 diam (H) = 4

Question:- Is the periphery of every graph

disconnected?

Answer: - NO.

For this we take an example.

The graph F of above figure shows, each vertex of F is labeled with its eccentricity. Since diam (F) = 3, it follows that per (F) ≈ C

6, which is

connected. Definition: - Eccentric vertex If e (u) = d (u, v); where u, v € G, i.e. v is a vertex that is farthest from u. Such a vertex v is called an eccentric vertex of u. A vertex v is an eccentric vertex of the graph G if v is an eccentric vertex of some vertex of G. In other words, a vertex v is an eccentric vertex of G v is farthest from some vertex of G.

Definition: - Eccentric Graph

A connected graph G has the same eccentricity (& is there fore a peripheral vertex), then certainly every vertex of G is an eccentric vertex. A connected graph G is an eccentric graph if every vertex of G is an eccentric vertex. Every vertex of a graph can be an eccentric vertex without all the eccentricities being the same.

Example:-

A graph whose vertices in an eccentric vertex which are labeled by its eccentricity.

Definition: - Eccentric sub graph"

Let G be a connected graph. The eccentric sub graph Ecc (G) of G is a sub graph of G induced by the set of eccentric vertices of G.

Definition: - Separating Set

A separating set in a connected graph G is a set of vertices whose deletion disconnects G.

Definition: - Cut-vertex

If a separating set of G contains only one vertex v, then the vertex v is said to be a cut-vertex of G.

Definition:- Boundary vertex

A Vertex is in a connected graph G is a boundary neighbor w of v. While a vertex v is a boundary vertex of the graph G if u is a boundary vertex of some vertex of G. Note: - If v is an eccentric vertex of a vertex u in a connected graph G, then no vertex of G is farther from u than v is. In particular, if w is a neighbor of v, then d Theorem: - No cut vertex of a connected graph G is a boundary vertex of G. Proof: - Assume, to the contrary, that there exists a connected graph G and a cut-vertex v of G such that v is a boundary vertex of some vertex u in G, Let G 1 be component of G-v that contains u and let G

2 be another

component of G-v. If w is a neighbor of v that belongs to G2, then d(w ,u) = d(u,v) +1, International Journal of Advanced Engineering Technology E-ISSN 0976-3945 IJAET/Vol.II/ Issue IV/October-December, 2011/147-150 Which contradicts our assumption that v is a boundary vertex of u. Because if v is a boundary vertex if u then ≥ d(u, v). Therefore if v is a cut-vertex of a connected graph G then it is a boundary vertex of G is false.

Hence the proof.

Note: - Since no cut-vertex can be a boundary vertex, no cut-vertex can be an eccentric vertex or a peripheral vertex either. There are certain vertices, however, that must be boundary vertices.

Definition: - Interior vertex of graph G

A vertex v is an interior vertex of G if for every vertex u distinct from v, there exists a vertex w such that v lies between u and w. The interior Int (G) of G is the sub graph of G induced by interior vertices.

For Example,

For the graph G of above figure the vertices s, v & x are the interior vertices of G and so Int (G) = P

3, as

showing in above figure. We now see that the interior vertices are precisely those vertices that are not boundary vertices.

Theorem: - Let G be a connected graph, A vertex v

is a boundary vertex of G iff v is not an interior vertex of G. Proof:- Let v be a boundary vertex of G, say v is a boundary vertex of the vertex u. Assume, to the contrary, that v is an interior vertex of G. Since v is an interior vertex of G, there exists a vertex w distinct from u & v such that v lies between u & w.

Let P: u = v

1, v2, v3,..... , v = vj, vj+1, ... , vk = w be a u-

v path, Where 1< j < k. However, v j+1 € N (v) and d(u,v j+1) = d(u, v) + 1, a contradiction. For the converse, let v be a vertex that is not an interior vertex of G. Hence there exists some vertex u such that for every vertex w distinct from u & v, the vertex v does not lie between u & w. Let x € N(v),then Since v does not lie between u &x, this inequality is vertex of u.

Hence the proof.

CONCLUSION

The graph G

T of figure 1, (Which recall, model town T

is that figure) is so again in figure 3, Where in this case every vertex is labeled with its eccentricity. We ask earlier where a fire house be built so that no

location in the town is too far from fire house. We now see that an appropriate answer is for the fire house to be

built at any of the four intersection correspond to central vertices (vertices having eccentricity 4) in GT.

DISCUSSION

Here we discussed on very simple model of town But if there is any complicated model for example, suppose if there is any river passing through that town then we can also discuss here the same problem with the help of concept of bridge in graph theory and it can also be solved easily. Graph theory is very powerful, Simple & also very interesting topic to work with any physical and real life problem.

ACKNOWLEDGMENTS

I feel immensely proud to present this report consisting of mathematical logics and computing skill. This work thought me not only to be patient but also made me eager to venture into new heights of taking up logics into been possible without outside help. Hence, I would like to thanks my parents and Dr. Snehal B. Rao (Assistant professor of Applied Mathematics department in M.S. University, Baroda) for good support. Thank you all.

REFERENCE

1. Graph Theory and its Applications by Gross.JL and Yellen.J CRC Press LLC, 1998

2. Graph Theory by Diestel.R Springer-Verlag 1997

3. Introduction to Graph Theory by West.DB Prentice Hall 1996

4. Introduction to Graph Theory by R.J. Wilson Addison

Wesley Longman 1996

5. Introduction to Graph Theory by R.J. Trudeau Dover Pubns 1994

6. Graphs: An Introductory Approach by J. Wilson and J.J. Watkins John Wiley & Sons 1990

7. Graph Theory by Gould.RJ Benjamin/Cummings 1988

8. Introduction to Graph theory By Gary chartrand & Ping Zhang.

quotesdbs_dbs14.pdfusesText_20

[PDF] graph theory applications in biology

[PDF] graph theory applications in computer science

[PDF] graph theory applications in cyber security

[PDF] graph theory applications in mathematics

[PDF] graph theory applications in network security

[PDF] graph theory applications in real life

[PDF] graph theory applications pdf

[PDF] graph theory applications ppt

[PDF] graph theory discrete mathematics

[PDF] graph theory exercises and solutions

[PDF] graph theory handwritten notes pdf

[PDF] graph theory problems and solutions

[PDF] graph theory questions and answers pdf

[PDF] graph theory theorems and proofs pdf

[PDF] graph theory with applications bondy murty solutions