![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The aim of this paper was to generate nanotopological structure on the power set of vertices of simple digraphs using new definition neighbourhood of vertices on out linked of digraphs. Based on the neighbourhood we define the approximations of the subgraphs of a graph. A new nanotopological graph reduction to symbolic circuit analysis is developed in this paper. By means of structural equivalence on nanotopology induced by graph we have framed an algorithm for detecting patent infringement suit.
Public Interest Statement
Lellis Thivagar introduced nanotopological space with respect to a subset X of an universe which is defined in terms of lower and upper approximations of X. The elements of a nanotopological space are called the nano-open sets. But certain nanoterms are satisfied simply to mean “very small”. It originates from the Greek word “Nanos” which means “Dwarf” in its modern scientific sense, an order to magnititude—one billionth of something. Nanocar is an example. The topology recommended here is named so because of its size, since it has atmost five elements in it. The purpose of the present work was to put a starting point for the nanotopological graph theory. We hope these new results will further assist to comprehend the concept of nanotopological space in various applied fields.
1. Introduction
The theory of nanotopology proposed by Lellis Thivagar and Richard (Citation2013a, Citationb), is an extension of set theory for the study of intelligent systems characterized by in sufficient and incomplete information. The purpose of the present work was to put a starting point for the nanotopological graph theory. Most real-life situations need some sort of approximation to fit mathematical models. The beauty of using nanotopology in approximation is achieved via approximation for qualitative subgraphs without coding or using assumption. We believe that nanotopological graph structure will be an important base for modification of knowledge extraction of processing. In this section, we define graphical isomorphism (Diestel, Diestel (Citation2010); Jensen & Shen, Citation2007) is a related task for deciding when two graphs with different specifications are structurally equivalent, that is whether they have the same pattern of connections. Nanohomeomorphism (Bonikowski, Bryniarski, & Wybraniec, Citation1998) between two nanotopological spaces are said to be topologically equivalent. Here, we are formalizing the structural equivalence of basic circuit of the chips from the graphs and their corresponding nanotopologies generated by them.
2. Preliminaries
This section represents a review of some fundamental notions related to nanotopology and graph theory.
Definition 2.1
(Lellis Thivagar & Richard, Citation2013a, Citationb) Let be an universe.
be an equivalence relation on
and
where
.
satisfies the following axioms:
(i) |
| ||||
(ii) | The union of elements of any sub collection of | ||||
(iii) | The intersection of the elements of any finite sub collection of |
Definition 2.2
(Bonikowski et al., Citation1998; Diestel, Diestel (Citation2010)) A graph G is an ordered pair of disjoint sets (V, E), where V is nonempty and E is a subset of unordered pairs of V. The vertices and edges of a graph G are the elements of V=V(G) and E=E(G), respectively. We say that a graph G is finite (resp. infinite) if the set V(G) is finite (resp.finite). The degree of a vertex is the number of edge in a graph contains a vertex u, then u is called an isolated point and so the degree of u is zero (Lellis Thivagar & Richard, Citation2013a, Citationb). An edge which has the same vertex to ends is called a loop and the edge with distinct ends is called a link (Jensen & Shen, Citation2007).
Definition 2.3
(Bonikowski et al., Citation1998; Diestel, Diestel (Citation2010)) A graph is simple if it has no loops and no two of its links join the same pair of vertices. A graph which has no edge called a null graph. A graph which has no vertices is called a empty graph (Jensen & Shen, Citation2007; Lellis Thivagar & Richard, Citation2013a, Citationb).
Definition 2.4
(Deseor & Kuh, Citation2009; Diestel, Diestel (Citation2010)) If G[V, E] is a directed graph and , then:
(i) | u is invertex of v if | ||||
(ii) | u is outvertex of v if | ||||
(iii) | The indegree of a vertex ’v’ is the number of vertices ’u’ such that | ||||
(iv) | The outdegree of a vertex ’v’ is the number of vertices ’u’ such that |
Throughout this paper the word graph means direct simple graph.
3. Approximations via neighbourhood
In this section, we will define lower and upper approximation of subgraph H of a graph G[V, E]. Some properties of these concepts are studied.
Definition 3.1
Let G(V,E) be a graph, . Then we define the neighbourhood of ’v’ as follows,
.
Definition 3.2
Let G(V,E) be a graph, H is a subgraph of G and N(v) be neighbourhood of v in V. Then we define
(i) | The lower approximation operation as follows: | ||||
(ii) | The upper approximation operation as follows: | ||||
(iii) | The boundary region is defined as |
Definition 3.3
Let G be a graph, N(v) be neighbourhood of v in V and H be a subgraph of G, forms a topolgy on V(G) called the nanotopology on V(G) with respect to V(H). We call
as the nanotopological space induced by a graph.
Example 3.4
Consider Figure .
Then and
and H be a subgraph of G, where
, then
. Therefore, the nanotopology induced by the graph is
and let H be a subgraph of G, where
then
. Therefore, the nanotopology induced by the graph is
Theorem 3.5
Let G[V, E] be a graph, H is a subgraph of G, then:
(i) | |||||
(ii) | |||||
(iii) |
|
Theorem 3.6
Let G[V, E] be a graph, H and K are two subgraphs of a graph G, then
(a) | If | ||||
(b) | |||||
(c) | |||||
(d) | |||||
(e) |
Proof
(a) | Let | ||||
(b) | Since | ||||
(c) | Since | ||||
(d) | Since | ||||
(e) | Since |
Example 3.7
Consider Figure
Then and
. Table shows the nanotopology of any subgraph H of a subgraph of G.
Table 1. Nanotopology for the possible subgraphs of G
Remark 3.8
Let G[V, E] be a graph, H and K are two subgraphs of G. Then from the examples 3.7 we can see some perception as follows:
(i) |
| ||||
(ii) |
| ||||
(iii) |
| ||||
(iv) |
| ||||
(v) |
| ||||
(vi) |
| ||||
(vii) |
| ||||
(viii) |
| ||||
(ix) |
| ||||
(x) |
|
Theorem 3.9
Let G[V,E], H is a subgraph of G, then
Proof
Let there exists a
such that
therefore
Now, since , then
implies,
Theorem 3.10
Let G[V,E], H is a subgraph of G, then
(i) | |||||
(ii) |
Proof
(i) | Let | ||||
(ii) | we know that |
4. Formalizing structural equivalence
Here we are formalizing the structural equivalence for the graphs and their corresponding nanotopologies generated by them.
Remark 4.1
In this section we define graphical isomorphism is a related task for deciding when two graphs with different specifications are structurally equivalent, that is whether they have the same pattern of connections. Nanohomeomorphism between two nanotopological spaces are said to be topologically equivalent. Here we are formalizing the structural equivalence for the graphs and their corresponding nanotopologies generated by them.
Definition 4.2
(Hsu & Lin, Citation2008) Two digraphs G and H are isomorphic if there is an isomorphism f between their underlying graphs that preserves the direction of each edge. That is, e is directed from u to v if and only if f(e) is directed from f(u) to f(v).
Definition 4.3
(Hsu & Lin, Citation2008) Two digraphs Cand D are isomorphic if D can be obtained by relabelling the vertices of C, that is, if there is a bijection between the vertices of C and those of D, such that the arcs joining each pair of vertices in C agree in both number and direction with the arcs joining the corresponding pair of vertices in D.
Definition 4.4
Let and
be nanotopological spaces, then the mapping
is said to be a nanocontinuous on
if the inverse image of every nano-open set in
is nano-open in
.
Definition 4.5
Let and
be a nanotopological spaces, then the mapping
is said to be a nanohomeomorphism if
(i) | f is 1–1 and onto | ||||
(ii) | f is nanocontinuous | ||||
(iii) | f is nano-open |
Example 4.6
Let G = [V,E] and G’= [V’,E’] be two isomorphic graphs, where V= , E =
, V’ =
and E’ =
.
Then there exists a function such that
. Let H be any subgraph of G and V(H) =
. Then the nanotopology generated by vertices of V(H) and V(f(H)) are
and
. Then the function
is a homeomorphism (Figure ).
Theorem 4.7
Let G = [V,E] and G’ = [V’,E’] be any two isomorphic graphs then there exists a homeomorphism for every subgraph H of G.
Proof
Since G and G’ are isomorphic by defn. there is an isomorphism between their uderlying graphs that preserves the direction of each edge and also N(x) = N(f(x))
. Suppose
and
be the nanotopological space generated by V(H) and f(V(H)). Since f is a bijection clearly, it follows that
is 1–1 and onto.
(i) | To prove that | ||||
(ii) | To prove that |
5. Computer chip intellectual property rights
Based on the structural equivalence of graphs and the corresponding nanotopology induced by them, we have made an attempt to check whether the chip produced by a company have striking operational similarity produced by the another company.
Suppose that not long after Corporation develops and markets a computer chip, it happens that the Corporation
markets a chip with striking operational similarities. If Corporation
could prove that Corporation
’s circuit is merely a rearrangement of the Corporation
circuitry that is the circuitries are isomorphic], they might have the basis for a patent infringement suit.
Algorithm to detect patent infringement suit: Step1: Given the electrical circuit of the chips manufactured by two companies. An electrical network is an interconnection of electrical network elements such as resistances, capacitances, inductances, voltage and current sources, etc., We also assign reference direction by a directed edge results in the directed graph representing the network.
Step2: Convert the electrical circuits and
into graphs
and
.
Step3: Check whether and
are isomorphic, and their corresponding nanotopologies induced from their vertices are homeomorphic.
Step4: If and
then the corresponding circuitries have striking operational similarities, and the company
can claim on the basis for a patent infringement suit.
Step5: Otherwise, we can conclude that both the chip produced are entirely different.
Step1: Consider the following basic circuit of the chip manufactured by two companies Corporation and Corporation
. Using the above algorithm we can prove whether these two circuits have functional similarities via nanotopology induced by the vertices of its subgraphs (Figure ).
Step2: The graphs are good pictorial representations of circuits and capture all their structural characteristics. Transform the basic circuit and
of the chip produced by Corporation
and Corporation
into graphs
and
, respectively (Figure ).
Step3: From the following graph we define a function such that f(1) = b, f(2) = a, f(3) = c, f(4) = d and clearly f is an isomorphism. Since
can be obtained by relabelling the vertices of
, that is, f is a bijection between the vertices of
and those of
, such that the arcs joining each pair of vertices in
agree in both number and direction with the arcs joining the corresponding pair of vertices in
.
Then we also have to check is a homeomorphism for every subgraph H of G.
Since f is a bijection clearly, it follows that is 1–1 and onto.
(i) | To prove that |
Then the function is a homeomorphism. This holds for every subgraph H of
(Table ).
Table 2. Nanotopolgy for V(H) and f(V(H))
Step4: From the above process, we can conclude that the graph of the circuits and their corresponding nanotopologies generated by the vertices of the subgraphs are homeomorphic.
Step5: Thus we can characterize that the chips manufactured by Corporation is just a rearrangement of Corporation
and also they have striking operational similarities and Corporation
can also claim for his patent infringement suit.
Observation: Using the above structural equivalence technique we can check whether two circuits are equivalent and we can also extend our theory in many industrial products for patent infringement suit.
6. Conclusion
The purpose of the present work was to put a starting point for the application of nanotopology via graph theory. We believe that nanotopological graph structure will be an important base for modification of knowledge extraction and processing.
Additional information
Funding
Notes on contributors
M. Lellis Thivagar
M. Lellis Thivagar has published 210 research publications both in National and International journals to his credit. In his collaborative work, he has joined hands with intellectuals of high reputed persons internationally. He serves as a referee for 12 peer-reviewed international journals. At present he is the professor & chair person, School Of Mathematics, Madurai Kamaraj University.
Paul Manuel
Paul Manuel has published 114 research publications both in National and International journals to his credit. He is expertise in Graph Algorithms, Combinatorial chemistry and Grid computing and also reviewer of many prestigious professional bodies. Currently he is an Professor, Department of Information sciences, Kuwait University, Kuwait.
V. Sutha Devi
V. Sutha Devi is a research scholar of Mathematics under the guidance of M. Lellis Thivagar at the School of Mathematics, Madurai Kamaraj University, Madurai. She had 9 years of working experience as Assistant Professor of Mathematics. She has attended and presented two papers in international conferences. Four of her research papers are published/accepted in the reputed international peer-reviewed journals.
References
- Bonikowski, Z., Bryniarski, E., & Wybraniec, U. (1998). Extensions and intentions in the rough set theory. Information Sciences, 107, 149–167.
- Deseor, C. A., & Kuh, E. S. (2009). Basic circuit theory. Berkeley, CA: Tata McGraw-Hill.
- Diestel, R. (2010). Graph theory II. Heidelberg: Springer-Verlag IV.
- Jensen, R., & Shen, Q. (2007). Fuzzy-rough sets assisted attribute selection. IEEE Transactions on Fuzzy System, 15, 73–89.
- Lellis Thivagar, M., & Richard, C. (2013a). On nano forms of weakly open sets. International Journal of Mathematics and Statistics, 1, 31–37. Retrieved from www.ijmsi.org [version 0.11e0111031037].
- Lellis Thivagar, M., & Richard, C. (2013b). On nano continuity. Journal of Mathematical Theory and Modelling, 3, 32–37.
- Hsu, L. H., & Lin, C. K. (2008). Graph theory and interconnection networks. CRC Press.