 Open Access
 Total Downloads : 380
 Authors : Nagesh H M, R Chandrasekhar
 Paper ID : IJERTV2IS50504
 Volume & Issue : Volume 02, Issue 05 (May 2013)
 Published (First Online): 21052013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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), Bangalore560 100.
2 R Chandrasekhar
Department of MCA, PES Institute of Technology, Banashankari III Stage, Hosakerehalli, Bangalore560 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 nonouterplanar and Eulerian.
Keywords: Line graph; Regular Binary Tree; Planar; Outerplanar; Minimally non outerplanar; Inner Vertex Number i(G).

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 nonouterplanar 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;

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.

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 (2p3) 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 qvertices
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 nonempty 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., onelevel
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 nonouterplanar.
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 nonEulerian.
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
is a nonempty path.
Conversely, suppose T is onelevel 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 nonouterplanar.
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:

Harary.F, Converging and packing in graphsI, Annals of New York Academy of Science, 175(1970), 198205.

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

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 116123.

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

Kulli. V.R, A characterization of pathos, The Mathematical Education 9(1975), 3233.

Harary.F, Graph Theory, AddisonWesley, Reading, Mass (1969).
Proof: Suppose T is
K1,2 . Then by
Theorem [4], PAL(RT) is an outerplanar, a