Original Article

, Volume: 15( 3)

# Total Pathos Edge Semi Entire Block Graph

- *Correspondence:
- Venkanagouda M Goudar , Department of Mathematics, Sri Siddhartha Institute of Technology, Tumkur, Karnataka, India,
**Tel:**9448579479;**E-mail:**[email protected]

**Received:** May 12, 2017; **Accepted:** June 21, 2017; **Published:** June 26, 2017

**Citation:** Venkanagouda M Goudar and Jagadeesh N. Total Pathos Edge Semi Entire Block Graph. Int J Chem Sci. 2017;15(3):151.

### Abstract

In this paper, we introduce the concept of total pathos edge semi entire block graph of a tree. We obtain some properties of this graph. We study the characterization of graphs whose total pathos edge semi entire block graphs are always nonplanar, crossing number one, Eulerian and Hamiltonian.

### Keywords

Block graph; Edge Semientire graph; Inner vertex number; Line graph

### Introduction

Let G (p,q) be a connected graph with vertex set V=p and the edge set E=q. If e=uv is in E (G), then the vertices u and v are adjacent. For the graph theoretical notation, we follow in [1,2].

In [3] Venkanagouda et al. introduced the graph valued function, the pathos edge semi entire block graph of a tree T. The block graph B (G) of a graph G was introduced in [2]. Further the path graph P (T) of a tree was studied in [3].

The following theorems will be used in the sequel.

**Theorem 1 [6]. **If G is a (p, q) graph whose vertices have degree d_{i} then L (G) has q vertices and qL edges where

**Theorem 2 [6].** The line graph L (G) of a graph G has crossing number one if and only if G is planar and 1 or 2 holds:

1. The maximum degree d (G) is 4 and there is unique non-cut vertex of degree 4.

2. The maximum degree d (G) is 5, every vertex of degree 4 is a cut vertex and there is a unique vertex of degree 5 and has at most 3 edges in any block.

**Theorem 3 [2]. **A connected graph G is isomorphic to its line graph if and only if it is a cycle [4].

**Theorem 4 [6].** The line graph L (G) of a graph is planar if and only if G is planar, Δ ≤ 4 and if deg v=4 for a vertex v of G, then v is a cut vertex.

**Theorem 5 [1]. **A graph is planar if and only if it has no subgraph homeomorphic to K_{5} or K_{3,3}.

**Theorem 6 [9].** For any planar graph G, edge semi entire block graph E_{b} (G) whose vertices have degree d_{i} has (q+r+b) vertices and

edges, where r the number of regions, b be the number of blocks, q_{j} the number of edges in a block b_{j}, b_{k} be the blockdegree of a cut vertex C_{k} and q_{r} be the number of edges lies on the region r_{1}.

**Theorem 7 [3].** For any planar graph G, pathos edge semi entire block graph PEb (G) whose vertices have degree d_{i} has (2q+k+1) vertices and edges, where r be the number of regions, b the number of blocks, q_{j} the number of edges lies in a block b_{j}, b_{k} be the block degree of a cut vertex C_{k} and q_{r} be the number of edges lies in the region r_{1}.

**Theorem 8 [1]. **A connected graph G is eulerian if and only if each vertex in G has even degree [5].

**Theorem 9 [2].** A nontrivial graph is bipartite if and only if all its cycles are even.

**Theorem 10 [3].** For any tree T, the pathos edge semi entire block graph PE_{b} (T) is planar if and only if T is a star graph K_{1, n}, for n ≥ 3.

### Total Pathos Edge Semi Entire Block Graph

In this section, we define the total pathos edge semi entire block graph of a tree.

**Definition 2.1** The total pathos edge semi entire block graph of a tree T denoted by T_{Pe} (T) is the graph whose vertex set is the collection of edges, blocks, regions and path of pathos of T in which two vertices of T_{Pe} (T) are adjacent if both are the edges of T which are adjacent or both are blocks of T which are adjacent or one is a block and other is an edge e of T and e lies on it, or one is a region and other is an edge e of T and edge e lies on the region or one is a path of pathos of T and other is an edge e of T in which e lies on the path or both are the path of paths p_{i} and p_{j} of T and both p_{i} and p_{j} have a common cut vertex. In **Figure 1**, a graph G and its total pathos edge semi entire block graph are shown [6].

We begin with the following direct results.

**Remark 1. **For any tree T,

**Remark 2. **For any graph G, Tpe (G)=PE_{b} (T)U P (T)

**Remark 3.** For any edge e_{i} in T with edge degree n, the degree of the vertex e’_{i} which corresponds to e_{i} in T_{Pe} (T) is always n+1.

### Results

**Theorem 11.** Let T be a tree, the total pathos edge semi entire block graph T_{Pe} (T) is always non-separable.

**Proof.** Consider T be a tree and let e_{i} for all i?T be the edges of T. In a Tree T, every edge becomes a block. Let b_{1}=e_{1}, b_{2}=e_{2}. b_{m}=e_{m} be the blocks, r_{1} be the only one region in T and p_{1}, p_{2}. p_{k} be the pathos of T. By the definition of L (T), the vertices e_{1}, e_{2}. e_{m} of L (T) form a sub graph without cut vertex. Also in T_{Pe} (T), the vertex formed from the region called the region vertex is adjacent to e_{i} for all i=1,2. m, to form a nonseparable graph. Since there are m blocks which are K_{2}, we have each b_{i} is adjacent to e_{i} for all i.

Further T contains some pendent pathos, these correspond to the pathos vertices p_{i} and each p_{i} is adjacent to only one vertex e_{j} such that e_{j} becomes a cut vertex. Also in a tree, at least two paths are always adjacent then T_{Pe} (T) is non-separable [7].

**Theorem 12.** If T (p, q) is a connected graph whose vertices have degree d_{i} and if the number of blocks to which the edge e_{i} belongs in T is b_{i}, then the total pathos edge semi entire block graph T_{Pe} (T) has 2q+k+1 vertices and edges, where q_{j} be the number of edges in each block b_{j}and bk be the block degree of a cut vertex c_{k}.

**Proof.** By Remark 1, Thus, the number of vertices in T_{Pe} (T) equals the number of vertices of of PE_{b} (T). By theorem 7, V[PE_{b} (T)]=2q+k+1.

Further by Remark 2, the number of edges in T_{Pe} (T) is same as the number of edges in PE_{b} (T) and the number of edges P(T).

By theorem 7, the number of edges in PE_{b} (T) is . Also, the number of edges in a path graph P(T) is Hence the number of edges

**Theorem 13.** For any tree T, T_{Pe} (T) is non-complete graph.

**Proof. **By definition of T_{Pe} (T), there is no adjacency between the regions and blocks. In T_{Pe} (T) there is no edge between the region vertex and block vertex. Hence T_{Pe} (T) is non-complete graph.

**Theorem 14.** For any tree T, the total pathos edge semi entire block graph T_{Pe} (T) is not a bipartite graph.

**Proof.** In a tree other than path contains at least one vertex v of T such that degree of v ≥ 3. Let e1, e2, e3 be the edges incident to v. By the definition of T_{Pe} (T), the edges incident with v, form a cycle C_{3} in T_{Pe} (T). By Theorem 9, T_{Pe} (T) is not bipartite graph.

**Theorem 15.** For any tree T, T_{Pe} (T) ? PE_{b} (T) if and only if T is a path.

**Proof.** Let T be a path. By definition, T_{Pe} (T), PE_{b} (T) have the same number of vertices. Since T is a path and the pathos graph of a path has no edges, it implies by definitions that T_{Pe} (T) and PE_{b} (T) are isomorphic.

Conversely suppose T_{Pe} (T) ? PE_{b} (T) and T is non-trivial connected tree. We now prove that T is a path. We assume that T has at least one vertex v such that degree of v ≥ 3. By remark 2, the number of edges in T_{Pe} (T) is the sum of the number of edges PE_{b} (T) and the number of edges in P (T). Hence the number of edges in PE_{b} (T) is less than the number of edges in T_{Pe} (T). Thus T_{Pe} (T) ? PE_{b} (T), a contradiction. Thus, T is a path.

**Theorem 16. **For any tree T, total pathos edge semi entire block graph T_{Pe} (T) is always nonplanar.

**Proof.** Let T be a connected tree and be a star K_{1, n}, for n ≤ 3. By Theorem 10, PE_{b} (T) is planar. Let e_{1}=b_{1}, e_{2}=b_{2}, and e_{3}=b_{3} be the edges which are also blocks, r_{1} be the region and p_{1}, p_{2} be the path of pathos of T. In T_{Pe} (T), the vertices e_{1}, e_{2}, e_{3} and r_{1} form a complete graph K_{4}. The block vertices b_{1}, b_{2}, b_{3} form a complete graph K_{3} and the edges between p_{1} and p_{2} must crosses the edges already drawn and hence T_{Pe} (T) is nonplanar.

If T=K_{1, n}, n ≥ 4, by the Theorem 10, PE_{b} (T) is nonplanar and hence T_{Pe} (T) is nonplanar.

**Theorem 17.** For any tree T, the total pathos edge semi entire block graph T_{Pe} (T) has crossing number one if and only if T is K_{1, 3}.

**Proof. **Suppose T_{Pe} (T) has crossing number one, clearly T_{Pe} (T) is nonplanar. By Theorem 16, we have T=K_{1, n}, n ≥ 4. Assume that T=K_{1, n} for n=4. By the definition of L (T), L (K_{1,4})=K_{4}. Since every edge of T lies on only one region r_{1} so in T_{Pe} (T), all vertices of K_{4} are adjacent to the region vertex r_{1} to form K5, clearly it has crossing number one. Further in a tree T, each edge is a block and all blocks b_{1}, b_{2}, b_{3} and b_{4} are adjacent to each other. By the definition of T_{Pe} (T), all four block vertices form K_{4} as sub graph, clearly the inner vertex b_{i} is adjacent to the edge e_{i} which corresponds to e’i in T_{Pe} (T) which form another one crossing number. Hence T_{Pe} (T) has crossing number at least two, a contradiction [9,10].

Proving conversely, show that K_{5} is a subgraph which has crossing number one. By the definition of line graph, L (K_{1,3})=K_{3} and all edges lies on only one region. In T_{Pe} (T), the region vertex r_{1} is adjacent to all vertices which corresponds to the edges of T and it form a complete graph K_{4} . Further each edge is a block and all blocks form K_{3} as a sub graph. Also, the pathos vertices p1 adjacent is e_{1} and e_{2}, p_{2} is adjacent to e_{3} and these pathos vertices are adjacent to each other and it form crossing number one. Hence, Cr [ T_{Pe} (T)]=1.

**Theorem 18.** For any tree T, the total pathos edge semientire block graph T_{Pe} (T) is Eulerian if and only if T is a star K_{1, 4n+2} for n ≥ 1.

**Proof.** Suppose T_{Pe} (T) is Eulerian. We consider the following cases.

**Case 1.** Assume that T be any non-star tree T, we have the following sub cases.

**Sub case 1.1.** Let u, v ?T such that degree (u)=3 and degree (v)=2. Let e_{1}, e_{2}, e_{3} be the edges incident to u and e_{3}, e_{4} be the edges incident to v. Clearly edge degree of an edge e_{1} is 4. By the Remark 3, the corresponding vertex in T_{Pe} (T) have degree 5, which is odd. By Theorem 8, T_{Pe} (T) is noneulerian, a contradiction.

**Sub case 1.2. ** Assume that T contain an edge have edge degree of every edge is even, which is possible only when the total number of edges of T will be odd. By definition of TPe (T), the deg (ri) becomes odd. By Theorem 8, TPe (T) is noneulerian, a contradiction.

**Case 2. **Assume that T=K1, p where p ≠ 4n+2. We have the following subcases.

**Sub case 2.1. **We assume that T=K_{1}, 3n+1 n=1.2. k. By case 1, each edge of K_{1}, _{3} have edge degree 4, by Theorem 2, the corresponding vertices in T_{Pe} (T) have edge degree odd, which is odd. By the Theorem 8, T_{Pe} (T) is noneulerian, a contradiction.

**Sub case 2.2.** Assume that T=K_{1,4}. By case 1, each edge e_{i} in T have edge degree odd. By the Remark 3, the corresponding vertices e1 in T_{Pe} (T) have even degree. The region vertex r’_{i} is adjacent to all four vertices v^{1}_{i} , i=1, 2, 3, 4 which form a graph with all vertices of even degree. In T, there are two paths of pathos p1 and p2 and each pathos contains two edges. In T_{Pe} (T), both pathos vertices adjacent to form graph with both p_{1} and p_{2} have odd degree. By Theorem 8, T_{Pe} (T) is noneulerian, a contradiction.

Conversely suppose T=K_{1, 4p+2} for p=1,2. n. In a tree T, every edge e_{i} have odd degree, by Remark 3, the vertices corresponds to e_{i} of T in T_{Pe} (T) becomes even degree. Further the total number of edges of T is even, then the region vertex in T_{Pe} (T) becomes even degree. Also, each edge is a block e_{i} =b_{i} for all i, each block b_{i} adjacent to remaining blocks and e_{i} adjacent to b_{i} to form even degree. Lastly the pathos vertices which are adjacent to even number of edges and each pathos are adjacent to remaining 2n path of pathos. Then in T_{Pe} (T), every vertex is of even degree. Hence T_{Pe} (T) is Eulerian.

**Theorem 19.** For any tree T, T_{Pe} (T) is Hamiltonian.

**Proof.** Suppose T be a tree. We consider the following cases.

**Case 1. **Let T be a star K_{1, n}, n is odd with vertices u_{1}, u_{2}u_{3}.... u_{n}u_{n+k} such that degree of u_{1}=n and let b_{1}, b_{2} . . .b_{m} be the number of blocks, ri be the regions, the number of paths of pathos are and T contains only one region. By the definition of T_{Pe} (T), V[T_{Pe} (T)]={e_{1}, e_{2}, e_{3} . . . . . .e_{n}, b_{1}, b_{2}, . . . . . b_{n-1}} Then there exist a cycle containing the vertices of T_{Pe} (T) as p_{1},p_{2}, p_{3},…p_{k},e_{5},e_{k},b_{k}b_{k-1},. . . b_{1},e_{1},e_{3}… r.e_{2} p_{1} and it includes all the vertices of T_{Pe} (T). Hence it is a Hamiltonian cycle.

**Case 2. **Let T=K_{1,n}, n>2 and is even. Then the number of path of pathos is Let V [T_{Pe} (T)]={e_{1},e_{2} . . . .e_{n}, b_{1},b_{2}. . . b_{n-1}} U {p_{1}, p_{2} . . . . . . } U r_{1} then there exist a cycle which contains the vertices of T_{Pe} (T) as p_{1}, p_{2},…e_{k} b_{k}, b_{k-1}, . . . b_{1},e_{1},…r.,e_{2} p_{1} and is a Hamilton cycle. Hence T_{Pe} (T) is Hamiltonian.

**Case 3.** Suppose T is neither a path nor a star, then T contains at least two vertices of degree >2. Let e_{1}, e_{2}. . . . .e_{n} be the edges of T such that e_{1}=b_{1}, e_{2}=b_{2}. . . . . e_{n}=b_{n} be the blocks. Then V [T_{Pe} (T)]={e_{1}, e_{2} . . . e_{n}, b_{1}, b_{2}. . . .b_{n}} {p_{1}, p_{2} . . . . .p_{i}}r_{1} where T has p_{i} pathos vertices for i > 1 and each pathos vertex is adjacent to the edge of T, where the corresponding pathos lie on the edges of T. Then there exist a cycle C which contains all the vertices of T_{Pe} (T) as p1, e_{1}b_{1}e_{2}p_{2}e_{3}. . . . . . . . . r_{1} en p_{1}. Hence T_{Pe} (T) is a Hamiltonian. Clearly T_{Pe} (T) is a Hamiltonian.

**Case 4.** Suppose T is a path. Let u_{1}, u_{2}u_{3}. . . . . u_{n} be a path. The vertex set V [T_{Pe} (T)]={e_{1},e_{2} . . . .e_{n}, b_{1},b_{2}. . . b_{n-1}} U {p_{1}} U r_{1} . Clearly there exist a cycle which contains the vertices of T_{Pe} (T) as p_{1},…e_{k} b_{k}, b_{k-1}, . . . b_{1},e_{1},…r.,e_{2} p_{1} and is a Hamilton cycle. Hence T_{Pe} (T) is Hamiltonian.

### Conclusion

In this paper, we defined the total pathos edge semi entire block graph of a tree. We characterized the graphs whose total pathos edge semi entire block graphs are planar, Hamiltonian and have crossing number one.

### References

- Harary F. Annals of New York. Academy of Sciences. 1977;175:198.
- Harary F.Graph Theory. Addison-Wesley Reading Mass. 1969;72:107.
- Jagadeesh N,Venkanagouda M Goudar.Pathos edge semientire block graph. J Com Math Sci.2015;6:395-402.
- Kulli VR. On minimally nonouterplanar graphs, proceedings of the Indian National Science Academy. 1975;41.
- Kulli VR,Akka DG. J Math Sci.1980;14:585-8.
- Sedlacek J. Some properties of interchange graphs. The Graphs and the applications. Academic press, New York. 1962.
- Stanton RG, Cowan DD, James LO. Proceedings of the Louisiana Conference on Combinatorics. Graph Theory and Computation. 1970;pp:112.
- Goudar VM. On Pathos vertex, semientire graph of a tree.IntJApp Math Res. 2012;11:666-70.
- Goudar VM,Jagadeesh N. Edge semientire block graph.Int J Com App.2014;89:42-4.
- MaralabhaviYB, Muddebihal,Goudar VM. On Pathos edge semientire graph of a tree.In the Far East J App Math.2007;27:85-91.