/compile/output.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 13, No. 5, 2020, 1300-1305 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Special Issue Dedicated to Professor Hari M. Srivastava On the Occasion of his 80th Birthday On plick graphs with point-outercoarseness number one V. Lokesha1, Sunilkumar M. Hosamani2,∗, Shobha V. Patil3 1 Department of Studies in Mathematics VSK University, Bellary, Karnataka, India 2 Department of Mathematics, Rani Channamma University, Belagavi, Karnataka, India 3 Department of Mathematics, KLE’s Dr. M. S. Sheshgiri College of Engineering and Technology Belagavi, Karnataka, India Abstract. The plick graph P (G) of a graph G is obtained from the line graph by adding a new vertex corresponding to each block of the original graph and joining this vertex to the vertices of the line graph which correspond to the edges of the block of the original graph. The point outer-coarseness is the maximum number of vertex-disjoint nonouterplanar subgraphs of G. In this paper, we obtain a necessary and sufficient conditions for the plick graph P (G) to have point- outercoarseness number one. 2020 Mathematics Subject Classifications: 05C99 Key Words and Phrases: Plick graph, Edge-disjoint, Nonplanar, Coarseness, Outercoarseness 1. Introduction By a graph we mean a finite, undirected graph without loops or multiple edges. Let V (G), E(G) and L(G) denote the vertex set, edge set and line graph of a graph respectively. The all undefined terminology will conform with that in Harary [4]. For a real number x, ⌊x⌋ denotes the greatest integer not exceeding x and ⌈x⌉ is the least integer not less than x. Two graphs are said to be homeomorphic if both can be obtained from the same graph by inserting new points of degree two into its lines. Kuratowski [8] has characterized planar graphs as those graphs which contain no subgraphs homeomorphic to K5 or K3,3. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v13i5.3716 Email addresses: v.lokesha@gmail.com (V. Lokesha), sunilkumar.rcu@gmail.com (S. M. Hosamani), shobhap49@gmail.com (S. V. Patil) https://www.ejpam.com 1300 c© 2020 EJPAM All rights reserved. V. Lokesha, S. M. Hosamani, S. V. Patil / Eur. J. Pure Appl. Math, 13 (5) (2020), 1300-1305 1301 Chartrand, Gellar and Hedetniemi [2] introduced the point-partition number denoted by πn(G) for each positive integer n. The point-partition number πn(G) is defined as the maximum number of subsets into which the point set of G can be partitioned so that each set induces a graph which contains a subgraph homeomorphic to either Kn+1 or K⌊n+2 2 ⌋,⌈n+2 2 ⌉. This general parameter πn(G) is defined for n=1,2,3 and 4. π1(G) is the line independence number. π2(G) is the maximum number of point-disjoint subgraphs of G, such that each subgraph is not a forest. This is also the maximum number of point-disjoint cycles contained in G and for this reason we refer π2(G) as the point-cycle multiplicity. π3(G) is the maximum number of point-disjoint nonouterplanar subgraphs of G and is called point-outercoarseness number of G. π4(G) is the maximum number of point-disjoint nonplanar subgraphs of G and is called the point coarseness of G and denoted by ξ ′ (G). A point and a line are said to cover each other if they are incident. A set of points which cover all the lines is a point cover of G while a set of lines which cover all the points is a line cover. The smallest number of points in any point cover of G is called its point covering number and is denoted by α0(G) or α0. Similarly α1(G) or α1 is the minimum number of lines in any line cover of G and is called its line covering number. A point cover (line cover) is called minimum if it contains α0(α1) elements. A graph G+ is the endedge graph of a graph G if G+ is obtained from G by adjoining an endedge uiu ′ i at each point ui of G. The plick graph P (G) of a graph G is obtained from the graph by adding a new point corresponding to each block of the original graph and joining this point to the points of the line graph which correspond to the lines of the block of the original graph. For n ≥ 2, Pn(G)=P (Pn−1(G)) where P 1(G)=P (G) is the nth iterated plick graph. In Figure1, a graph and its plick graph P (G) are shown. b b b b b b bb b b G: P(G): Figure 1. If G is a planar graph, then the inner vertex number i(G) of G is the minimum number of vertices not belonging to the boundary of the exterior region in any embedding of G in V. Lokesha, S. M. Hosamani, S. V. Patil / Eur. J. Pure Appl. Math, 13 (5) (2020), 1300-1305 1302 the plane[6]. Note: Since the definitions of point-outercoarseness number one and minimally nonouter- planar are isomorphic, therefore the aim of this paper is to characterize all nth plick graphs with point-outercoarseness is one. 2. Preliminary Results The following will be useful in the proof of our results. Remark 1. For any graph G, L(G) is a subgraph of P (G). Theorem 1. [6] The plick graph P (G) of a graph G is planar if and only if G satisfies the following conditions: (i) ∆(G) ≤ 4 (ii) every block of G is either a cycle or K2. Theorem 2. [6] A graph G has a planar plick graph if and only if it has no subgraph homeomorphic to K1,5 or K4 − x, where x is any line of K4. Theorem 3. [6] A graph G is a cycle if and only if plick graph P (G) is a wheel. Theorem 4. [6] The plick graph P (G) of a graph G is minimally nonouterplanar if and only if it satisfies the following conditions: (i) ∆(G) ≤ 3 and (ii) G is unicyclic. Theorem 5. Let G be any connected graph. π3(P (G)) = 1 if and only if G has one of the following properties: (i) ∆(G) ≤ 3 and (ii) G is unicyclic. Proof. Since the definitions of point-outercoarseness number one and minimally nonouter- planar are isomorphic, the proof of the theorem is analogous to the proof of the Theorem 4. 3. Main Results Before we establish the first result, we prove the following Lemma. Lemma 1. P (G) is unicyclic if and only if there exist a unique vertex of ∆(G) = 3 in G. V. Lokesha, S. M. Hosamani, S. V. Patil / Eur. J. Pure Appl. Math, 13 (5) (2020), 1300-1305 1303 Proof. Suppose P (G) is unicyclic. We consider the following cases. Case 1. Let ∆(G) ≤ 2. If ∆(G) = 1, then G is K2. Consequently P (G) is K2,a contradiction. If ∆(G) = 2 then G is a path or a cycle. If G is a path, then clearly P (G) is a tree, a contradiction.If G is a cycle Cn; ∀n ≥ 3, then by Theorem 3, P (G) is a wheel, a contradiction. Case 2. Suppose ∆(G) = 4. Clearly K1,4 is a subgraph of G and by Remark 1, P (G) contains K4 as an induced subgraph, a contradiction. Hence ∆(G) ≤ 3. Suppose G has two or more than two vertices of degree 3. Then by Theorem 1, P (G) is planar and there exist at least two blocks which are cycles C3 as induced subgraphs for P (G), a contradiction. Hence there exists a unique vertex of ∆(G) = 3. The converse is obvious. Corollary 1. P (G) is a tree if and only if G is a path Pn;n ≥ 2. Theorem 6. For any connected graph G, π3(P 2(G)) = 1 if and only if G is a tree with ∆(G) ≤ 3 and contains a unique vertex of degree 3. Proof. Suppose π3(P 2(G)) = 1. The plick graph P (G) satisfies the hypothesis of Theorem 5. Clearly ∆(G) ≤ 3 and unicyclic.If ∆(G) = 3 and is unicyclic, then there exist exactly one vertex of degree 3 in G and G does not contain any cycle as an induced subgraph. Suppose G contains a cycle, then by Theorem 3, P (G) contains a wheel, a contradiction to the hypothesis. Therefore G must be a tree. By Lemma 1, there exists a unique vertex of ∆(G) = 3. Conversely, suppose G is a tree. We consider the following cases depending on ∆(G). Case 1. If ∆(G) = 1 , then G = K2. Consequently P (G) = K2 and P 2(G) = K2, a contradiction to our assumption. Case 2. If ∆(G) = 2, then G is either a cycle or a path. If G is a cycle, then by Theorem 3, P (G) is a wheel, a contradiction. If G is a path, then by Corollary 1, P (G) is a tree with ∆(G) = 3 and every block of P (G) is K2. By Theorem 1, P 2(G) is planar with an induced subgraph of C3, a contradiction. Case 3. Suppose G has exactly two vertices of degree 3. Then by Theorem 1, P (G) is planar and there exist exactly two cycles C3 as induced subgraphs of P (G). By Theorem 3, in P 2(G) there exist exactly two wheels of length four W4 that is K4 as an induced subgraph, a contradiction. Hence, there exist exactly one vertex one vertex of degree 3 in G. Theorem 7. There is only one graph P4 whose third plick graph P 3(G) has point- outer- coarseness number 1. V. Lokesha, S. M. Hosamani, S. V. Patil / Eur. J. Pure Appl. Math, 13 (5) (2020), 1300-1305 1304 Proof. Suppose π3(P 3(G)) = 1 for a connected graph G. Then P 2 is planar and satisfies the hypothesis of Theorem 5. Clearly ∆(P 2(G)) ≤ 3 and P 2(G) is unicyclic. By Lemma 1, P (G) has a unique vertex of ∆(P (G)) = 3. Hence P (G) is a tree. By Corollary 1, G is a path. Assume G 6= P4. Then immediately G is either Pn;n ≤ 3 or Pn;n ≥ 5. If G = Pn;n ≤ 3 then π3(P 3(G)) = 0, a contradiction. If G = Pn;n ≥ 5, then P 2(G) contains at least two edge disjoint induced subgraphs of C3. By Theorem 3, P 3(G) will contain two copies of complete graph K4, a contradiction. If G = P4, then P (G) is P+ 3 with ∆(P+ 3 ) = 3. Therefore by Lemma 1, P 2(G) will be unicyclic. By Theorem 3, P 3(G) will contain K4. Hence π3(P 3(G)) = 1. Theorem 8. There is only one graph P3 whose fourth plick graph P 4(G) has point- outercoarseness number 1. Proof. The proof is similar to Theorem 7. Theorem 9. For n ≥ 5, there is no graph whose nth plick graph Pn(G) has point- outercoarseness number 1. Proof. Assume π3(P 4(G)) = 1. Then P 3(G) must satisfy the hypothesis of Theorem 5. Clearly ∆(P 3(G)) ≤ 3 and is unicyclic or a tree or a path. Thus there does not exist any graph whose nth;n ≥ 5 plick graph have point-outercoarseness one. Acknowledgements The authors are thankful to anonymous referees for their useful suggestions to the improvement of the paper. References [1]. B Basavanagoud , K Mirajakar. On plick graphs with coarseness number one. Math Comput Sci, 5:7-10, 2011. [2]. G Chartrand , D Geller , S Hedetniemi. Graphs with forbidden Subgraphs. J Comb Theory, 10:12-41, 1971. [3]. G Chartrand, H Kronk, C E Wall. The point-arboricity of graphs. Israel J Math, 6:168-175, 1968. [4]. F Harary. Graph Theory. Addison-Wesely Reading Mass 1969. [5]. J Mitchem. The point-outercoarseness of n-partite graphs. Compositio Mathematica 26:101-110, 1973. [6]. V R Kulli, B Basavanagoud. Characterization of Planar Plick Graphs. Discussiones Mathematicae Graph Theory 24:41-45, 2004. [7]. V R Kulli. On minimally nonouterplanar graphs. Proceedings of the Indian National Science Academy 41A:275-280, 1975. V. Lokesha, S. M. Hosamani, S. V. Patil / Eur. J. Pure Appl. Math, 13 (5) (2020), 1300-1305 1305 [8]. K.Kuratowski. Sur le probleme des courbes gauches en topologie. Fund.Math, 15:271- 283,1930. [9]. H P Patil, U Rengarasu. The vertex-coarseness of iterated line graphs. Graph Theory and its Applications(Eds) S Arumugam et al., Tata McGraw-Hill Publishing Company Limited New-Delhi 109-120, 1996.