Ratio Mathematica Volume 38, 2020, pp. 329-339 On the planarity of line Mycielskian graph of a graph Keerthi G. Mirajkar* Anuradha V. Deshpande† Abstract The line Mycielskian graph of a graph G, denoted by Lµ(G) is defined as the graph obtained from L(G) by adding q + 1 new vertices E ′ = e ′ i : 1 ≤ i ≤ q and e, then for 1 ≤ i ≤ q, joining e ′ i to the neighbours of ei and to e. The vertex e is called the root of Lµ(G). This research paper deals with the characterization of planarity of line Mycielskian Graph Lµ(G) of a graph. Further, we also obtain the characteriza- tion on outerplanar, maximal planar, maximal outerplanar, minimally nonouterplanar and 1-planar of Lµ(G). Keywords: Planar graph, Outerplanar, Maximal planar, Maximal out- erplanar, Minimally nonouterplanar and 1-planar. 2010 AMS subject classifications: 05C07, 05C10, 05C38, 05C60, 05C76. 1 *Department of Mathematics, Karnatak University’s Karnatak Arts College, Dharwad - 580001, Karnataka, INDIA; keerthi.mirajkar@gmail.com †Department of Mathematics, Karnatak University’s Karnatak Arts College, Dharwad - 580001, Karnataka, INDIA; anudesh08@gmail.com. 1Received on April 30th, 2020. Accepted on June 19th, 2020. Published on June 30th, 2020. doi: 10.23755/rm.v38i0.506. ISSN: 1592-7415. eISSN: 2282-8214. ©Keerthi G. Mirajkar et al. This paper is published under the CC-BY licence agreement. 329 Keerthi G. Mirajkar, Anuradha V. Deshpande 1 Introduction All graphs considered in this paper are finite, undirected and without loops. The phraseologies are referred from [Harary, 1969]. The graph G is said to be embedded in a surface S when its vertices are represented by points in S and each edge by a curve joining corresponding points in S, in such a way that no curve intersects itself and two curves intersect each other only at a common vertex. A graph G is said to be planar if it can be embedded in the plane. A plane representation of a planar graph divides the plane into number of plane areas called regions or faces. The regions enclosed by the planar graph are called interior faces of the graph. The region surrounding the planar graph is called the exterior face of the graph. A planar graph G is called maximal planar if the addition of any edge to G creates a nonplanar graph. A maximal planar graph is a planar graph in which every face (including the exterior face) is bounded by a triangle [Dillencourt, 1991]. A planar graph is called outerplanar if it can be embedded in the plane so that all its points lie on the same face. An outerplanar graph is called maximal outerplanar if no line can be added without losing outerplanarity. The inner vertex number i(G) of a planar graph G is the minimum number of vertices not belonging to the boundary of the exterior region in any embed- ding of G in the plane. A graph G is said to be k - minimally nonouterplanar if i(G) = k,k ≥ 1. An 1-minimally nonouterplnar graph is called minimally nonouterplanar [Kulli and Basavanagoud, 2004]. Two graphs are said to be homeomorphic if one graph can be obtained from the other by insertion of vertex of degree two into its edges or by the merger of adjacent edges, where the incident vertex is of degree two. Crossing number cr(G) of a graph G is the minimum number of crossings (of its edges) among the drawings of G in the plane. [Ringel, 1965] introduced the concept of 1-planarity. A graph G is called 1-planar if it can be drawn in the plane so that all or any edge is crossed by at most one other edge. The line Mycielskian graph of a graph G, denoted by Lµ(G) is defined as the graph obtained from L(G) by adding q + 1 new vertices E ′ = e ′ i : 1 ≤ i ≤ q and e, then for 1 ≤ i ≤ q, joining e′i to the neighbours of ei and to e. The vertex e is called the root of Lµ(G) [Mirajkar and Mathad, 2019]. 330 On the planarity of line Mycielskian graph of a graph Figure 1. C3, K1,3 and their line Mycielskian graphs Lµ(C1,3) and Lµ(K1,3) Motivated by the the research work [Mirajkar and Mathad, 2019], the present problem is initiated. Further it is extended with the objective of obtaining the characterization results on planarity, outerplanar, maximal planar, maximal outer- planar, minimal nonouterplanar and 1-planar of Lµ(G). 2 Prelimnaries The following important theorems and remark are used for proving further results. Theorem 2.1. [Kuratowski, 1930] A graph is planar if and only if it has no sub- graph homeomorphic to K5 or K3,3. Theorem 2.2. [Harary, 1969] A graph is outerplanar if and only if it has no subgraph homeomorphic to K4 or K2,3 except K4 − x. Theorem 2.3. [Czap and Hudák, 2012] The complete graph Kα1 , α1 ≤ 6 is 1- planar. Theorem 2.4. [Mirajkar et al., 2019] The line Mycielskian graph Lµ(G) of a graph G is disconnected iff G = K2. Remark 2.1. [Mirajkar and Mathad, 2019] L(G) is subgraph of Lµ(G). 331 Keerthi G. Mirajkar, Anuradha V. Deshpande 3 Results Theorem 3.1. The line Mycielskian graph Lµ(G) is planar if and only if the graph G is Cn, n = 3 or C3. Proof. Suppose Lµ(G) is planar and G = Cn. We consider the following cases. Case 1. Suppose n = 5, then G = C5. L(C5) is C5 and by remark 2.1, L(G) is subgraph of Lµ(G). The construction of Lµ(G) with five newly introduced vertices e ′ 1,e ′ 2,e ′ 3, e ′ 4 and e ′ 5 corresponding to vertices of L(C5) and root vertex e produces five mutually adjacent vertices with degree four which is a subgraph homeomorphic to K5. By theorm 2.1, a contradiction. Case 2. Suppose n = 4, then G = C4. L(C4) is C4 and by remark 2.1, L(G) is subgraph of Lµ(G). Here Lµ(G) is constructed by introducing new vertices e ′ 1,e ′ 2,e ′ 3, and e ′ 4 cor- responding to the vertices e1,e2,e3, and e4 of L(C4) and root vertex e. Newly introduced vertices are connected with the vertices e1,e2,e3 and e4 of C4 in such a way that the, e ′ 1 and e ′ 3 are adjacent to the two opposite vertices e2 and e4 and e ′ 2 and e ′ 4 are adjacent to e1 and e3. Root vertex e is connected to e ′ 1,e ′ 2,e ′ 3, e ′ 4. This construction produces the five mutually adjacent vertices with degree four and thus contains a subgraph homeomorphic to K5, a contradiction (From theorem 2.1). Case 3. Suppose n = 3, then G = C3. L(C3) is C3 by remark 2.1, L(G) is subgraph of Lµ(G). To construct line Mycielskian graph Lµ(G), three new vertices e ′ 1,e ′ 2 and e ′ 3 corresponding to the edges of G and root vertex e are intro- duced. The edges between the vertices are drawn in such a way that the newly introduced vertices e ′ 1,e ′ 2 and e ′ 3 are adjacent to the corresponding adjacent edges of e1,e2 and e3 of G respectively. The root vertex e joins the vertices e ′ 1,e ′ 2 and e ′ 3 such that no crossing of edges occur as shown in Figure 1. This implies that line graph Lµ(G) is planar for G = C3. From the above cases, it is observed that Lµ(G), for all G = Cn, n ≥ 4, contains a subgraph homeomorphic to K5, a contradiction. Thus Lµ(G) is planar only if G is Cn, n = 3. Conversely, Suppose G = C3, then the construction of Lµ(G) as discussed in above case 3 which results into planar graph. Theorem 3.2. The line Mycielskian graph Lµ(G) is planar if and only if the graph G is a path graph Pn, n ≥ 3. Proof. Suppose Lµ(G) is planar and G = Pn. 332 On the planarity of line Mycielskian graph of a graph We consider the following cases. Case 1. Suppose n = 2, then G = P2, then from theorem 2.4, Lµ(G) is disconnected graph, a contradiction. Case 2. Suppose G = Pn,n ≥ 3. By remark 2.1, L(G) is subgraph of Lµ(G). L(Pn) is Pn−1. Figure 2. P5 and its line Mycielskian graph Lµ(P5) For the construction of Lµ(G), new vertices e ′ 1,e ′ 2,.., e ′ n−1 corresponding to edges of G and root vertex e are introduced. In Lµ(G), the edges between the vertices are connected in such a way that, the newly introduced vertices e ′ 1 and e ′ n−1 are adjacent to e2 and en−2 of L(G) respectively and the other vertices e ′ 2,e ′ 3,.. , e ′ n−2 are adjacent to two vertices ei−1 and ei+1, i = 2, 3, .., (n − 2). The root vertex e is adjacent to the vertices e ′ 1,e ′ 2,.., e ′ n−1. All the faces are polygons without any crossings as shown in Figure 2. i.e., Lµ(G) is planar. It is clear from the above two cases that Lµ(G) is planar only for G = Pn,n ≥ 3. Conversely, Suppose G = Pn, n ≥ 3. Then the construction of Lµ(G) results into planar graph (as discussed above). Theorem 3.3. The line Mycielskian graph Lµ(G) of a graph G is planar if and only if one of the follwing conditions hold (i) ∆(G) = 2, except for Cn, n ≥ 4 (ii) G = K1,3 Proof. Suppose Lµ(G) of G is planar. We discuss the following cases based on the maximum degree of G. 333 Keerthi G. Mirajkar, Anuradha V. Deshpande Case 1. Suppose G is a graph with ∆(G) = 5. By remark 2.1, L(G) is subgraph of Lµ(G). Then the line Mycielskian graph Lµ(G) contains K5 as its subgraph. By Theorem 2.1, Lµ(G) is nonplanar, a contradiction. Case 2. Next suppose G is a graph with ∆(G) = 4. By remark 2.1, L(G) is subgraph of Lµ(G) and contains K4 as its subgraph. Lµ(G) is obtained by intro- ducing new vertices e ′ 1,e ′ 2,e ′ 3 and e ′ 4 corresponding to the edges of subgraph K4 of L(G) and root vertex e by the definition. Vertices of K4 and newly introduced ver- tices are connected. The edge from root vertex e is drawn in such a way that it is adjacent to the vertices e ′ 1,e ′ 2,e ′ 3 and e ′ 4. This construction produces subgraph K4 with each vertex degree ≥ 4. One of the newly introduced vertices of is Lµ(G) is adjacent to the three vertices of K4 with path length 1. It is also adjacent to the remaining one vertex of K4 with path length 2. This produces the subgraph homeomorphic to K5, a contradiction. Case 3. Suppose ∆(G) = 3, G contains K1,3 as its subgraph. By remark 2.1, L(G) is subgraph of Lµ(G). Since L(K1,3) is C3, the construction of Lµ(K1,3) is same as Lµ(C3) as shown in Figure 1. From theorem 3.1, Lµ(C3) is planar. Thus Lµ(K1,3) is also planar. Further in the construction of Lµ(K1,3), presence of additional edge in K1,3 to any vertex leads to increase in the number of vertices and edges (2 vertices and 3 edges) in Lµ(G) and thus contains K4. On constructing Lµ(G), newly introduced vertices, root vertex and vertices of K4 produces five mutually adjacent vertices with degree 4 which is a subgraph homeomorphic to K5. By theorem 2.1, Lµ(G) is nonplanar, a contradiction. Case 4. Suppose ∆(G) = 2, Obiviously G is either path graph Pn or cycle Cn. By theorem 3.1 and theorem 3.2, Lµ(Cn), n = 3 and Lµ(Pn), n ≥ 3 are planar. From all the above cases, it is noted that, Lµ(G) contains subgraph homeo- morphic to K5 for ∆(G) ≥ 3, a contradiction and is planar only for ∆(G) = 2. Converse is obivious. Theorem 3.4. The line Mycielskian graph Lµ(G) is outerplanar if and only if G is P3. Proof. Suppose Lµ(G) is outerplanar. Then Lµ(G) is planar. By theorems 3.1, 3.2 and 3.3, Lµ(G) is planar only for the graphs C3,K1,3 and Pn, n ≥ 3. Suppose G=C3 or K1,3. From theorem 3.1 and Figure 1, Lµ(G) contains a sub- graph homeomorphic to K2,3. From theorem 2.2, Lµ(G) is not outerplanar, a contradiction. Assume G = P4. line graph of P4 is P3. By remark 2.1, L(G) is subgraph of Lµ(G). On constructing Lµ(G) with newly introduced vertices and root vertex (as explained in case 2 of theroem 3.2) forms a subgraph homeomorphic to K2,3. By theorem 2.2 Lµ(P4) is not outerplanar. Which is contradiction. i.e., G cannot be P4. 334 On the planarity of line Mycielskian graph of a graph Similarly, for higher values of n i.e., for G = P4, n ≥ 5, the same construction (case 2 of theorem 3.2) repeates and generates a subgraph with every four vertices of Lµ(G) which is homeomorphic to K2,3, a contradiction. Next assume G = P3. Line graph of P3 is P2 and by remark 2.1, L(G) is subgraph of Lµ(G). Lµ(G) is constructed by introducing root vertex e and new vertices e ′ 1 and e ′ 2 corresponding to the edges of e1 and e2 of G respectively. The edges from new vertices are drawn in such a way that e ′ 1 is adjacent to e2 and e ′ 2 to e1 which forms C5, as shown in Figure 3, which is outerplanar. Therefore, G = P3. By observing the above cases , it can be stated that Lµ(G) for G = Pn, n ≥ 4 contains subgraph homeomorphic to K2,3, a contradiction and hence is outerplanar only for G = Pn, n = 3. Figure 3. P3 and its line Mycielskian graph Lµ(P3) Conversely, suppose G = P3. From theorem 3.2, Lµ(G) is planar for G=Pn, n ≥ 3. i.e., Lµ(P3) produces C5 and is planar (as discussed above ). Clearly which is outerplanar. Theorem 3.5. The line Mycielskian graph Lµ(G) is maximal planar if and only if G is C3 or K1,3 or Pn, n ≥ 4. Proof. Suppose Lµ(G) is maximal planar, then it is planar. From theorem 3.1, theorem 3.2 and theorem 3.3, Lµ(G) is planar if G is C3 or K1,3 or Pn, n ≥ 4 . Suppose G is C3 or K1,3. On the construction of Lµ(C3) or Lµ(K1,3) as shown in Figure 1, it can be observed that, three of its interior faces are triangles and by the definition of homeomorphic graph, the other two faces can be triangularised by merging adjacent edges if the incident vertex is of degree two. i.e., Lµ(G) has triangulation plane. Lµ(G) is maximal planar. 335 Keerthi G. Mirajkar, Anuradha V. Deshpande Suppose G is Pn, n ≥ 3. From theorem 3.2, Lµ(G) is planar. We consider the following cases. Suppose G = P3. From theorem 3.4, the construction of Lµ(P3) forms C5 and does not contain any triangle faces as shown in Figure 3. Thus Lµ(P3) is not maximal planar, a contradiction. Next, suppose G = Pn, n ≥ 4. The construction of Lµ(G) contains some of its interior faces as C4’s and some as C5’s. By definition of homeomorphic graph, all the faces can be triangularised by merging the adjacent edges. Thus Lµ(G) has triangulation plane and is maximal planar for G = Pn, n ≥ 4. Conversely, suppose G = C3 or K1,3 or Pn, n ≥ 4. From theorem 3.1, theorem 3.3 and theorem 3.2, Lµ(G) is planar. Let us first consider G = C3 or K1,3. Three interior faces of Lµ(G) are triangles and two faces are C4’s and by the definition of homeomorphic graph, they can be triangularized by merging adjacent edges. i.e., Lµ(G) has triangulation plane. Hence, Lµ(G) is maximal planar. Next suppose G = Pn, n ≥ 4. From Figure 2, all the faces of Lµ(G) can be triangularized by merging adjacent edges and thus Lµ(G) has triangulation plane and it is maximal planar. 2 Theorem 3.6. For any graph G, The line Mycielskian graph Lµ(G) of a graph G is not maximal outerplanar. Proof. Suppose Lµ(G) is maximal outerplanar, then it is outerplanar. From theorem 3.4, Lµ(G) is outerplanar only for G = P3. From Figure 3, it is obvious that addition of an edge between any two non-adjacent vertices does not violate the property of planarity, a contradiction. 2 Theorem 3.7. For any graph G, the line Mycielskian graph Lµ(G) of a graph G is not minimally nonouterplanar. Proof. Suppose Lµ(G) is minimally nonouterplanar, then Lµ(G) is planar. From theorem 3.1, theorem 3.2 and theorem 3.3, Lµ(G) is planar only if G is Cn, n = 3 or Pn, n ≥ 3 or K1,3. We consider the following three cases. Case 1. Suppose G = Cn, n = 3 or G = K1,3. From Figure 1, Lµ(G) contains at least three points belong to interior region, a contradiction. Case 2. Suppose G = Pn, n ≥ 3. Subcase 2.1 Suppose n = 3 then G = P3. From Figure 3, in Lµ(G) all the points belong to exterior region. No point belong to interior region, a contradic- tion. 336 On the planarity of line Mycielskian graph of a graph Subcase 2.2. Suppose G = Pn, n ≥ 4, then Lµ(G) is constructed with newly introduced vertices e ′ 1,e ′ 2,.., e ′ n−1 corresponding to edges of G and root vertex e (construction explained in case 2 of theorem 3.2).This construction generates subgraph with every four vertices of Lµ(G) which is homeomorphic to K2,3. This process continues for the successive value of n in G and thus Lµ(G) contains more than one subgraph homeomorphic to K2,3, a contradiction. In either cases, Lµ(G) is not minimally nonouterplanar. 2 Theorem 3.8. If the graph G is a cycle Cn, n ≥ 4, then line Mycielskian graph Lµ(G) is 1-planar with n crossings . Proof. Let G be Cn, n ≥ 4. By remark 2.1, L(G) is subgraph of Lµ(G). From theorem 3.1, Lµ(Cn), n ≥ 4 is nonplanar. Here Lµ(G) is constructed by introducing new vertices e ′ 1,e ′ 2,e ′ 3, e ′ 4,.., e ′ n and root vertex e. Root vertex, newly introduced vertices and vertices of L(Cn) are connected as explained in the theorem 3.1. This construction produces the five mutually adjacent vertices with degree ≥ 4 and thus contains a subgraph homeomorphic to K5. From theorem 2.3, Lµ(G) is 1-planar. Figure 4. C4 and its line Mycielskian graph Lµ(C4) In Lµ(G), every crossing arises from the edges drawn between the vertices L(Cn) and newly introduced vertices. Each newly introduced vertex is adjacent with two vertices of L(Cn) and each crosing occurs from the two adjacent vertices of L(Cn). As there are n vertices in L(Cn), the number of crossings are n. 2 337 Keerthi G. Mirajkar, Anuradha V. Deshpande Theorem 3.9. If G is K1,3•K2, then the line Mycielskian graph Lµ(G) is 1-planar with crossing number 1. Proof . Let G be K1,3 • K2. By remark 2.1, L(G) is subgraph of Lµ(G). From theorem 3.3, Lµ(K1,3) is planar. But inclusion of K2 to K1,3 increases number of vertices and edges in Lµ(G) for which the construction is explained in theorem 3.3 case 3. This construction produces five mutually adjacent vertices with degree 4. Thus Lµ(G) contains a subgraph homeomorphic to K5. From theorem 2.3, Lµ(G) is 1-planar. Figure 5. K1,3 • K2 and its line Mycielskian graph Lµ((K1,3 • K2) In graph G = K1,3 • K2) shown in Figure 5, the number of edges are four. Since only one vertex e3 of G is adjacent to three edges, in Lµ(G) the degree of newly introduced vertex corresponding to this edge is four as shown in Figure 5, where as the degree of other newly introduced vertices e ′ 1,e ′ 2, and e ′ 4 is ≤ 3. Thus, this results the graph Lµ(G) to have only one crossing from the edges drawn between the root vertex e and newly introduced vertices e ′ 2,e ′ 3 and e ′ 4. 338 On the planarity of line Mycielskian graph of a graph 4 Conclusion In this research paper we obtained the characterization results on planarity, outerplanar, maximal planar, maximal outerplanar, minimal nonouterplanar and 1-planar of line Mycielskian graph Lµ(G). The results revealed that Lµ(G) is planar only for the graphs C3, Pn,n ≥ 3, K1,3 and maximal planar if G is C3, Pn,n ≥ 4 and K1,3. It is outerplanar only if G= P3.There is no existance of any graph whose Lµ(G) is maximal outerplanar and not minimally nonouterplanar. Further we also obtained Lµ(G) for 1-planar when G= Cn, n ≥ 4 and (K1,3 •K2) with n crossings and 1 crossing respectively. Future line of this research can be extended to study some more properties of planarity such as crossing numbers, genus, thickness and coarseness of line Mycielskian graph of a graph. References J. Czap and D. Hudák. 1-planarity of complete multipartite graphs. Discrete Applied Mathematics, 160(4-5):505–512, 2012. M. B Dillencourt. An upper bound on the shortness exponent of 1-tough, maximal planar graphs. Discrete mathematics, 90(1):93–97, 1991. F Harary. Graph theory, addison-wesley, reading, mass. 1969. V Kulli and B Basavanagoud. Characterizations of planar plick graphs. Discus- siones Mathematicae Graph Theory, 24(1):41–45, 2004. C. Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathematicae, 15(1):271–283, 1930. K. G. Mirajkar and Veena Mathad. The line mycielskian graph of a graph. In- ternational Journal of Research and Analytical Reviews(IJRAR), 6(1):277–280, 2019. K. G. Mirajkar, Veena Mathad, and Pooja B. Miscellaneous properties of line mycielskian graph of a graph. International Journal of Research and Analytical Reviews(IJRAR), 14(29):4552–4556, 2019. G. Ringel. Ein sechsfarbenproblem auf der kugel. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 29, pages 107– 117. Springer, 1965. 339