On Pathos Adjacency Line Graph Of A Regular Binary Tree

On Pathos Adjacency Line Graph Of A Regular Binary Tree

1 Nagesh H M

Department of Science & Humanities, PES Institute of Technology (Bangalore South Campus), Bangalore-560 100.

2 R Chandrasekhar

Department of MCA, PES Institute of Technology, Banashankari III Stage, Hosakerehalli, Bangalore-560 085.

Abstract

In this communication, the concept of Pathos Adjacency Line Graph PAL(RT) of a Regular Binary tree T is introduced. Its study is concentrated only on trees. We decompose PAL(RT) into an edge disjoint complete bipartite subgraphs and then give the reconstruction of T. We also present a characterization of those graphs whose PAL(RT) are planar, outerplanar, maximal outerplanar, minimally non-outerplanar and Eulerian.

Keywords: Line graph; Regular Binary Tree; Planar; Outerplanar; Minimally non- outerplanar; Inner Vertex Number i(G).

1. Introduction:

   The line graph of a graph G, denoted by L(G), is the graph whose vertices are the edges of G with two vertices of L(G) are adjacent whenever the corresponding edges of G are adjacent. The concept of pathos of a graph G was introduced by Harary [1], as a collection of minimum number of edge disjoint open paths whose union is G. The path number of a graph G is the number of paths in pathos. A Regular binary tree T is a binary tree in which the following conditions hold: a) There is exactly one

   vertex of degree two, namely the root, b) All vertices other than root have degree one or three [2]. The order (size) of T is the number of vertices (edges) in it. The path number of T is equal to , where 2 is the number of odd degree vertices of T. The edge degree of an edge uv of T is the sum of the degrees of u, v [3]. A graph G is planar if it can be drawn in the plane in such a way that any intersection of two distinct edges occurs only at a vertex of the graphs. A graph G is called outerplanar if G has an embedding in the plane in such a way that each vertex bounds the infinite face. An outerplanar graph G is maximal outerplanar if no edge can be added without losing its outer planarity. If G is a planar graph,

   then the inner vertex number iGof a graph G is

   the minimum number of vertices not belonging to the boundary of the exterior region in any embedding of G in the plane. A graph G is said to

   be minimally non-outerplanar if iG = 1[4].

   The Graph Valued function is defined as follows:

   The pathos adjacency line graph PAL(RT) of a regular binary tree T is defined as a graph in which;

   1. V(PAL(RT)) is the union of the set of edges and path of pathos of T in which two vertices are adjacent if and only if the corresponding edges of

      T are adjacent and edge lies on the corresponding path Pi of pathos.

   2. With reference to root r of T, the pathos vertex Pm vi ,v j is adjacent to Pn vk , vl in

Theorem [C] [6]: Every maximal outerplanar graph G with p vertices has (2p-3) edges.

Theorem [D] [6]: If G is a (p, q) graph whose

PALRT if and only if the pathos Pm and Pn

vertices have degree di , then L(G) has q-vertices

have the common vertex vc in T such that there

1 p 2

exists an edge between vi and vl through vc .

and qL edges, where qL q di .

2

2

i1

r

a P1 b

c P2 d e P3 f

Figure 1. Regular Binary Tree T

P1

PAL(RT) Decomposition and Reconstruction of T:

We recall a complete bipartite graph is a bipartite graph (i.e., a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent) such that every pair of vertices in the two sets are adjacent.

We have the following cases.

Case 1: Here we decompose L(T) of PAL(RT) into an edge disjoint complete bipartite subgraphs as follows. Let {v1, v2 ,…….v, n } are the vertices of

subgraph L(T) of PAL(RT). Then two vertices

vi , v j vi v j are adjacent in PAL(RT)

decomposition if they are adjacent in L(T) such that they do not form a cycle in L(T) and the edge

a forming a cycle in L(T) is taken as a separate

c component in decomposition.

P2

b Case 2: The pathos vertex corresponding to the pathos of T and vertices corresponding to edges of T are adjacent in PAL(RT) decomposition if

f they are adjacent in PAL(RT).

d e

Case 3: Two pathos vertices Pi , Pj (Pi Pj) corresponding to the pathos of T are adjacent in PAL(RT) decomposition if they are adjacent in PAL(RT). Hence, PAL(RT) consists of mutually

P3 edge disjoint complete bipartite subgraphs.

Figure 2. PAL(RT)

Conversely, let T ' be the graph of the

type which is described above. We can construct

the regular binary tree T which has pathos adjacency line graph as follows.

T ' as its

We need the following results to prove further results:

Theorem [A] [2]: A connected graph G is

We first consider the line graph L(T)

decomposition of PAL(RT). Let the vertices

{v1',v2 ',…….v, n '} of L(T) decomposition are the

Eulerian if and only if each vertex in G has an

edges in T. Then if two vertices vi ', v j 'vi ' v j '

even degree. are adjacent in decomposition, then the

Theorem [B] [5]: A graph G is a non-empty path

corresponding edges vi ', v j ' are adjacent in T.

if and only if it is a connected graph with

We finally consider PAL(RT) decomposition

p components

L ' s having vertices corresponding

p 2 vertices and

di 2 4 p 6 0.

i

to the pathos and

edges of T. Then, draw the

i1

pathos in T along each of the pendant vertices corresponding to edges of T in decomposition components. Hence, we have the following theorem.

1 p 2

2

2

Theorem 1: PAL(RT) is the pathos adjacency line graph of some regular binary tree

qPAL RT q di

i1

• q

P'1

T if and only if PAL(RT) can be partitioned into mutually edge disjoint complete bipartite subgraphs.

qPAL RT

p

p

1

1

2

2

di 2 P'1.

i1

a c b

Theorem 3: For any regular binary tree T, PAL(RT) is always planar.

Proof: We have the following cases.

b c d d e f

Case 1: Suppose T is

K1,2 . i.e., one-level

e P1 P2

regular binary tree T. Then by definition,

PAL(RT) is K3 which is a planar.

Case 2: Consider T with at least (2n 1)

vertices, n 3. i.e., level of T is at least two.

Then, there exists exactly one block as K2 and

remaining (n 1) number of blocks as K3 in L(T).

f a b c d

P3 P1 P1

e f P2 P3

Figure 3. Decomposition of PAL(RT)

In the following theorem, we obtain the number of vertices and edges in PAL(RT).

Theorem 2: If G is a (p, q) graph, where the vertices have degree di, then its PAL(RT) has

1 p 2

Also, T has exactly (2n 1) , n 2 number of path of pathos. The edges joining these blocks from the pathos vertices are adjacent to at most two vertices of each block of L(T). This gives a planar

PAL(RT).

Theorem 4: Pathos adjacency line graph PAL(RT) of a regular binary tree T is an outerplanar if and only if T is a star graph K1,2 .

Proof: Suppose PAL(RT) is an outerplanar. Assume that T has a vertex of degree

3. Then, T consists of exactly four vertices of odddegree. By definition, each block of L(T) is either K2 or K3. The number of path of pathos in T is two. The edges joining these blocks from the pathos vertices are adjacent to at most two vertices of each block of L(T). The adjacency of pathos vertices gives PAL(RT) in which

iPALRT 0, a contradiction.

Conversely, suppose T is a star

( q + k) vertices and

qPAL RT 2 di

P'1 ,

graph K1,2 .Then, by definition it forms K3 in

where k is being path number number of pathos in T.

i1

and

P' is the

PAL(RT), which is an outerplanar.

Theorem 5: Pathos adjacency line graph

Proof: By the definition, the number of

vertices in PALRT is (q + k). The number of

PAL(RT) of a regular binary tree T is maximal outerplanar if and only T is one- level regular

edges in PALRT is the sum of edges in L(G),

binary tree.

the number of edges lies on the path P' of the

Proof: Suppose PAL(RT) is maximal

pathos of G which is q and the number of adjacency of the pathos of G which is P 1.

Hence, by Theorem [D] we have,

outerplanar. Then, PAL(RT) is connected. Hence, T is connected. Let T be connected regular binary tree with p = 3 vertices, q = 2 edges and the path number k = 1. Then, PAL(RT) has (q + k) vertices. A regular binary tree with three vertices is a path P3. Also, the number of path of pathos

in T is exactly one,

P'1 0. Hence, by Theorem

contradiction. Since the maximum degree of a

1 p vertex in T is three, T has

2n 1 vertices,

n 3.

[2],

qPAL RT

di 2 .

Then, by definition of L(T), there exists exactly

2 i1

one block as K2 and remaining

(n 1)

number of

blocks as K3. Also, T has exactly 2n 1 , n 2

Since, PAL(RT) is maximal outerplanar, by Theorem[C], it has 2q k 3edges.

number of path of pathos. The edges joining these blocks from the pathos vertices are adjacent to at most two vertices of each block of L(T). The

1 p 2

adjacency of pathos vertices gives PAL(RT) such

2

2

di

2q k 3

that iPAL(RT ) 2, a contradiction. Hence

i1

PAL(RT) is not minimally non-outerplanar.

1 p 2

PAL(

Theorem 7: Pathos adjacency line graph

2

2

di

i1

p

2p 1 k 3 , for a tree, q = p – 1

and

RT) of a regular binary tree T is Eulerian if only if the order of T is exactly three.

Proof: Suppose PAL(RT) is Eulerian.

di 2 4p 1 k 6

i1

p

Assume that the order of T is at least 5. Then, there exists exactly one block as K2 and at least one block as K3 in L(T). Also, T has at least two path of pathos. The edges joining these blocks

i1

di 2 4 p 4k 10.

from the pathos vertices are adjacent to at most two vertices of each block of L(T). Hence the even degree vertices of K3 in PAL(RT) will be

For a tree which is a path, path number k = 1.

incremented by one. By Theorem [A], PAL(RT)

is non-Eulerian.

p

p

di 2

i1

4 p 41 10

Conversely, suppose that the order of T is exactly three. Then, by definition it forms K2 in L(T). The number of path of pathos in T is

exactly one. The edges joining K2 from the

p 2 pathos vertex forms K3 in PAL(RT). By Theorem

di i1

• 4 p 6 0. Hence, by Theorem [B], G

[A], PAL(RT) is Eulerian.

is a non-empty path.

Conversely, suppose T is one-level regular binary tree. Then, by definition, it forms K3 in PAL(RT), which is a maximal outerplanar. Hence, PAL(RT) is maximal outerplanar.

a b

a b

P1

P1

T PAL(RT)

Figure 4.

Theorem 6: For any regular binary tree T, pathos adjacency line graph PAL(RT) is not minimally non-outerplanar.

Conclusion: The pathos adjacency line graph is presented to and characterized for a regular binary tree T. Since the pathos vertices are adjacent in PAL(RT), it is always a block. It is interesting to apply this concept to certain classes of trees.

References:

1. Harary.F, Converging and packing in graphs-I, Annals of New York Academy of Science, 175(1970), 198-205.

2. Geir Agnarsson, Raymond Greenlaw, Graph Theory: Modelling, Applications and algorithms, Pearson Prestice Hall.

3. M.H.Muddebihal, B R Gudagudi and R.Chandrasekhar, On pathos line graph of a tree, National Academy of Science Letters, Vol.24, No.5- 12(2001), p 116-123.

4. Kulli.V.R, On minimally non outerplanar graphs, Proc. Indian Nat. Sci. Acad.41 (1975), 276- 280.

5. Kulli. V.R, A characterization of pathos, The Mathematical Education 9(1975), 32-33.

6. Harary.F, Graph Theory, Addison-Wesley, Reading, Mass (1969).

Proof: Suppose T is

K1,2 . Then by

Theorem [4], PAL(RT) is an outerplanar, a