Ratio Mathematica Volume 41, 2021, pp. 207-213 On the traversability of near common neighborhood graph of a graph Keerthi G. Mirajkar * Anuradha V. Deshpande† Abstract The near common neighborhood graph of a graph G, denoted by ncn(G) is defined as the graph on the same vertices of G, two ver- tices are adjacent in ncn(G), if there is at least one vertex in G not adjacent to both the vertices. In this research paper, the conditions for ncn(G) to be disconnected are discussed and characterization for graph ncn(G) to be hamiltonian and eulerian are obtained. Keywords: Near common neighborhood graph; Hamiltonian graph; Eulerian graph. 2020 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 July 9, 2021. Accepted on November 23, 2021. Published on December 31, 2021. doi: 10.23755/rm.v41i0.626 . ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY licence agreement. 207 Keerthi G. Mirajkar, Anuradha V. Deshpande 1 Introduction Let G be a graph. The near common neighborhood graph of G denoted by ncn(G) is a graph with the same vertices as G in which two vertices u and v are adjacent if there exists at least one vertex w ∈ V (G) not adjacent to both of u and v [Al- Kenani et al., 2016]. A cycle in a graph G that contains every vertex of G is called spanning cycle of G. Thus a hamiltonian cycle of G is a spanning cycle of G. A hamiltonian graph is a graph that contains a hamiltonian cycle. An euler trail in a graph G is a trail that contains every edge of that graph. An euler tour is a closed euler trail. An eulerian graph is a graph that has an euler tour. The graphs cosiderered in this paper are simple, undirected and connected with vertex set vi ∈ V (G), i = 1, 2, 3, ...,n. Let deg(vi) be the degree of vertices of G. Basic terminologies are referred from [Harary, 1969]. The common neighborhood graph (congraph) of G [Zadeh et al., 2014] which is exactly the opposite of near common neighborhood is denoted by con(G) is a graph with vertex set, in which two vertices are adjacent if and only if they have at least one common neighbor in the graph G. Here the common neighborhood of some composite graphs are computed and also the relation between hamiltonicity of graph G and con(G) is investigated. [Hamzeh et al., 2018] computed the con- graphs of some composite graphs and also results have been calculated for graph valued functions. [Sedghi et al., 2020] obtained the characteristics of congraphs under graph operations and relations between Cayley graphs and its congraphs. [Al-Kenani et al., 2016] studied near common neighborhood of a graph and obtained results for paths, cycles and complete graphs. Motivated by the results on [Zadeh et al., 2014], [Hamzeh et al., 2018] and [Sedghi et al., 2020], in this paper, the conditions for ncn(G) to be disconnected are discussed and also the- orems stating necessary and sufficient conditions for a graph ncn(G) to possess hamiltonian and eulerian cycle are studied. 2 Prelimnaries Below mentioned some important results are used through out the paper for prov- ing the theorems. Proposition 2.1. [Al-Kenani et al., 2016] For any path Pn, ncn(Pn) =   Kn, if n = 2, 3 2K2, if n = 4 Kn, if n ≥ 7. 208 On the traversability of near common neighborhood graph of a graph Proposition 2.2. [Al-Kenani et al., 2016] For any path Cn, ncn(Cn) =   Kn, if n = 3, 4 C5, if n = 5 Kn, if n ≥ 7. Proposition 2.3. [Al-Kenani et al., 2016]. For any complete graph Kn and totally disconnected graph Kn, we have 1.ncn(Kn) = Kn 2.ncn(Kn) = Kn,n ≥ 3 Theorem 2.1. [Singh, 2010]. Let G be a simple graph with p ≥ 3 and δ ≥ p/2. Then G is Hamiltonian. Theorem 2.2. [Singh, 2010] A nonempty connected graph is Eulerian if and only if it has no vertices of odd degree. Remark 2.1. [Singh, 2010] The complete graph Kp, for p ≥ 3, is always Hamil- tonian. 3 Results Theorem 3.1. If G is a graph with n vertices, then ncn(G) is disconnected if any one of the following conditions holds 1. G is Pn,Cn, n ≤ 4 2. G is Kn, n ≥ 3 3. G has ∆(G) = n− 1 4. G is a graph with two complete graphs connected by bridge 5. G is Kn •Pt, n ≥ 3 , t ≤ 3 Proof. The proof of the theorem is constructed by considering the following cases. Case 1. Suppose G=Pn or Cn, n ≤ 4. We consider the following two subcases. Subcase 1.1. Suppose G=Pn , n ≤ 4. If n = 2, 3, 4, then by the proposition 2.1, ncn(G) is disconnected. Subcase 1.2. Suppose G=Cn , n ≤ 4. If n = 3, 4, then from the proposition 2.2, ncn(G) is disconnected. Case 2. Suppose G=Kn, n ≥ 3. Then from the proposition 2.3, ncn(G) is disconnected. Case 3. Let G be a graph with vertex set V (G) = {vi|i ∈ N} and ∆(G) = n−1. Near common neighbourhood graph ncn(G) is a graph with same vertices vi as 209 Keerthi G. Mirajkar, Anuradha V. Deshpande G. The vertices vi and vj, j = 1, 2, 3, ...,n,i 6= j of ncn(G) are adjacent if there is at least one vertex w ∈ V (G) not adjacent to both vi and vj. Since ∆(G) = n− 1 in G ( that is vi is adjacent to all other vertices of G), there does not exists any nonadjacent vertex for vi and thus vi cannot be connected to any vertex of ncn(G). This results ncn(G) into disconnected. Case 4. Let G be a graph with two complete graphs Km and Kn connected by bridge. Let vi ∈ V (G), i = 1, 2, 3, ...,m be the vertex set of Km and vj ∈ V (G), j = m + 1,m + 2,m + 3, ...,n be the vertex set of Kn, where m and n are the vertices of bridge. As G consists of two complete graphs, vertices vi of Km and vj of Kn are respec- tively mutually adjacent. Nonadjacent vertices for all the vertices vi ∈ Km exists in Kn and for vj ∈ Kn exists in Km. Thus the vertices vi of Km and vj of Kn are mutually connected in ncn(G). This produces the disconnected graph with two components. Further, the end points of bridge are also mutually adjacent to all the vertices of Km and Kn respectively. Hence nonadjacent vertex does not exists for end points of bridge. This produces the graph ncn(G) into disconnected. Case 5. Let G be a Kn •Pt, n ≥ 3 and t ≤ 3. ncn(G) has the same vertices as G. Two vertices of ncn(G) are adjacent if there is at least one vertex w ∈ V (G) not adjacent to both the vertices. Let vi, i = 1, 2, 3, ...,n,n + 1,n + 2 be the vertex set of Kn •Pt .The vertices of Kn are v1,v2,v3, ...,vn and vertices of Pt are vn,vn+1,vn+2. The vertex vn is the common vertex which connects Kn and Pt. We consider the following subcases. Subcase 5.1 Suppose t = 2 that is Pt is path with two vertices, then G = Kn•P2. Since ∆(G) = n − 1, there exists at least one vertex which is adjacent to all the other vertices of G. From theorem 3.1 (Case 3), ncn(G) is disconnected. Subcase 5.2 Suppose t = 3 that is t = n,n + 1,n + 2. In G, all the pairs of vertices of Kn have the nonadjacent vertex as vn+2 and can be mutually connected in ncn(G). Also the vertices of Pt, vn+1 and vn+2 have the nonadjacent vertices in Kn and can be connected in ncn(G). As there does not exist any nonadjacent vertices for the pair of common vertex n and the vertices of Pt in G, they cannot be connected in ncn(G). This produces the the graph ncn(G) with two components. Thus ncn(G) is disconnected. 2. Theorem 3.2. For any graph G, ncn(G) is hamiltonian if and only if 1. G contains all the vertices of deg(vi) < n − 1 except for C4 • P2 and G is a graph with two complete graphs connected by bridge. 2. G = Pn or Cn, n ≥ 5. 3. G is Kn •Pt, n ≥ 3, t ≥ 4. Proof. Let G be graph with vertex set V (G). Suppose ncn(G) is hamiltonian. 210 On the traversability of near common neighborhood graph of a graph In light of the above theorem 3.1 that ncn(G) is disconnected if G is Pn,Cn, n ≤ 4, Kn, n ≥ 3, G has ∆(G) = n− 1, G is a graph with two complete graphs connected by bridge and G is Kn •Pt, n ≥ 3, t ≤ 3. Now we consider the graphs for which ncn(G) is connected. Case 1. Suppose G contains all the vertices of deg(vi) < n− 1. Let G be a graph vi ∈ V (G) vertices with degree(vi) < n− 1 (vi is not adjacent to all the vertices) and ncn(G) be the graph with same set of vertices as G. As deg(vi) < n− 1 in G, there exists at least one nonadjacent vertex for any pair of vertices of G. Hence by definition of ncn(G), those vertices in ncn(G) can be connected which produces connected ncn(G) graph. Further, since for each pair of vertices of G there exists a nonadjacent vertex, ncn(G) contains a cycle and δ ≥ n/2. From the theorem 2.1 ncn(G) is hamilto- nian. Next suppose G = C4 • P2. Let vi, i = 1, 2, 3, 4, 5 be the vertex set of C4 • P2 with one common vertex between C4 and P2. Among the four vertices of C4 of G, three vertices (except the common vertex) can be connected mutually adjacent as they have nonadjacent vertex (not common vertex) in P2. Similarly, a vertex of P2 which is not common can be connected with only three vertices of C4 in ncn(G) as there exists a nonadjacent vertex for these each pair of vertices. Whereas the common vertex can be connected only with a vertex of P2 in ncn(G) which is not common, since there exists a nonadjacent vertex in C4 for this pair and there does not exist nonadjacent vertex for the pair of vertices with C4. This results ncn(G) into connected graph with one pendent vertex and conse- quently does not contain hamiltonian cycle. Thus, ncn(C4 •P2) is connected but not hamiltonian. Case 2. Suppose G is Pn or Cn, n ≥ 5. Let G be a Pn or Cn, n ≥ 5. From the propositions 2.1 and 2.2, ncn(Pn) and ncn(Cn), n = 5, 6 are connected which contains a cycle and δ ≥ n/2. For n ≥ 7, ncn(G) is Kn. From the theorem 2.1 and remark 2.1, ncn(G) is hamiltonian. Case 3. Suppose G is Kn •Pt, n ≥ 3, t ≥ 4. Let G be a Kn •Pt,n ≥ 3, t ≥ 4, where n is the number of vertices of Kn and t is the number of vertices of Pt. Let vi ∈ V (G), i = 1, 2, 3, ...,n be the vertex set of Kn and vj ∈ V (G), j = n,n + 1,n + 2, ..., t be the vertex set of Pt, where n is the common ver- tex of Kn and Pt. As there is increase in the number of vertices (path length) in Pt of G, there exists a nonadjacent vertex for each pair of vertices of Kn and vertices of Pt, which pro- duces connected graph ncn(G) with cycles and also δ ≥ n/2. From the theorem 2.1, ncn(G) is hamiltonian. Converse is obvious. 211 Keerthi G. Mirajkar, Anuradha V. Deshpande 2 Theorem 3.3. For any graph G, ncn(G) is eulerian if only if G is 1. Pn,n ≥ 7. 2. Kn •Pt, n ≥ 3, t ≥ 5. 3. G = Cn, n = 5, 6. Proof. Let G is a graph with vertex set vi ∈ G, i = 1, 2, 3, ...,n. Suppose ncn(G) is eulerian, then degree of each vi of ncn(G) is even. From the theorems 3.1 and 3.2, ncn(G) is disconnected if G is Pn,Cn, n ≤ 4, Kn, n ≥ 3, G has ∆(G) = n−1, G is a graph with two complete graphs connected by bridge, G is Kn •Pt, n ≥ 3 , t ≤ 3 and is connected only if G contains all the vertices of deg(vi) < n− 1 , G = Pn or Cn, n ≥ 5 and G is Kn •Pt, n ≥ 3, t ≥ 4. From the proposition 2.1, ncn(G = Pn) is Kn with even degree; n ≥ 7, where n = 2s + 1, s = 2, 3, 4, .... From the proposition 2.2, ncn(G = Cn), n = 5, 6 is Kn of even degree. From the theorem 3.2, ncn(G = Kn •Pt) is Kn with even degree; n ≥ 3, t ≥ 5, where n = 2s + 1, s = 1, 2, 3, .... Hence from the theorem 2.2, ncn(G) is eulerian. Conversely, ncn(G) is a graph with same vertices as G. From theorem 3.1, ncn(G) is disconnected if G is Pn,Cn; n ≤ 4, Kn; n ≥ 3, G has ∆(G) = n − 1, G is a graph with two complete graphs connected by bridge and G is Kn •Pt; n ≥ 3, t ≤ 3 in all other cases it is connected. We consider the following cases. Case 1. Suppose ncn(G) is Kn, n = 1, 2, 3, ...,n, then from the theorem 3.2, if ncn(G) is connected and it is Kn for G = Pn,Cn, n ≥ 5 and Kn • Pt; n ≥ 3, t ≥ 5. Subcase 1.1 Suppose G = Pn or Cn, then from the propositions 2.1 and 2.2, ncn(G) is Kn, n ≥ 7. The degree of each vertex of Kn is even and n = 2s + 1, s = 1, 2, 3, ...,n. From theorem 2.2, ncn(G) is eulerian. Subcase 1.2. Suppose G = Kn •Pt, n ≥ 3, t ≥ 5, then from the theorem 3.2, if ncn(G) is connected and it is Kn for n ≥ 3, t ≥ 5. The degree of Kn is even if n is odd. From the theorem 2.2, ncn(G) is eulerian. Case 2. Suppose G = Cn, n = 5, 6. Subcase 2.1 Suppose G = Cn, n = 5, then from the proposition 2.2, ncn(G) is C5 or 2-regular graph. From the theorem 2.2 ncn(G) is eulerian. Subcase 2.2 Suppose G = Cn, n = 6, then from the proposition 2.2, ncn(G) is 2-regular graph. Hence from the theorem 2.2, ncn(G) is eulerian. Case 3. Suppose G = Kn •Pt, n ≥ 3, t ≥ 5. From the theorem 3.2, if ncn(G) is connected and it is Kn for n ≥ 3, t ≥ 5. The degree of Kn is even if n is odd. From the theorem 2.2, ncn(G) is eulerian. 212 On the traversability of near common neighborhood graph of a graph 4 Conclusions In this paper the study on near common neighborhood graph of a graph is ex- tended and various general conditions for which ncn(G) to be disconnected are discussed. It is disconnected for the graphs Pn,Cn; n ≤ 4, Kn; n ≥ 3, G has ∆(G) = n− 1, G is a graph with two complete graphs connected by bridge and G is Kn • Pt; n ≥ 3 , t ≤ 3 in all other cases it is connected. We have also ob- tained the necessary and sufficient condition for ncn(G) to possess hamiltonian and eulerian cycles. It contains hamiltonian cycle whenever it is connected except for C4 •P2. It contains eulerian cycle if ncn(G) is Kn with odd vertices and G is Cn, n = 5, 6. References A.N Al-Kenani, A. Alwardi, and O.A. Al-Attas. On the near-common neighbor- hood graph of a graph. International Journal of Computer Applications, 146 (1):1–4, 2016. A. Hamzeh, A. Iranmanesh, S.H. Zadeh, M.A. Hosseinzadeh, and I. Gutman. On common neighborhood graphs ii. Iranian Journal of Mathematical Chemistry, 9(1):37–46, 2018. F. Harary. Graph Theory. Addison-Wesley Mass, Reading, New York, 1969. S. Sedghi, D.W. Lee, and N. Shobe. Characteristics of common neighborhood graph under graph operations and on cayley graphs. Iranian Journal of Mathe- matical Sciences and Informatics, 15(2):13–20, 2020. G.S. Singh. Graph Theory. PHI Learning Private Limited, New York, 2010. S.H Zadeh, A. Iranmanesh, A. Hamzeh, and M.A Hosseinzadeh. On the common neighborhood graphs. Electronic Notes in Discrete Mathematics, 45:51–56, 2014. 213