2025
Permanent URI for this collection
Browse
Browsing 2025 by Author "Imtiaz Ali"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item Dominant and fault-tolerant metric dimensions of graphs(UMT Lahore, 2025-07-04) Imtiaz AliA graph represented by G = (V(G), E(G)) is a collection of vertices V(G) and edges E(G). The distance between any two vertices u, v of a graph G is represented as d(u, v) and is equal to the number of edges of the shortest path connecting u and v. For an ordered set U= {u1 , u2, u3, ⋯⋯ ,uk} ⊆ V(G) and a vertex v ∈ V(G), the representations of v with respect to U are the ordered k-tuple r(v/U) = {d(v , u1) , d(v , u2), d(v , u3), ⋯⋯ ,d(v , uk)}. The set U ⊆ V(G) of a graph G is a resolving set if for all u, v ∈ V(G), then r(u/U) ≠ r(v/U). A metric basis is a resolving set with minimum vertices. The cardinality of a metric basis is called the metric dimension. A set U ⊆ V(G) is a fault-tolerant resolving set if U\v is again a resolving set for each v ∈ U. A fault-tolerant resolving set is called a fault tolerant metric basis if it carries minimum vertices. The cardinality of a fault tolerant metric basis is called fault-tolerant metric dimension. The notation t ~ u implies tu ∈ E(G). The set U ⊆ V(G) is a dominant set if for every vertex t ∈ V(G)\U, there exists a vertex u ∈ U such that there is an edge between t and u means t ~ u. In 2020, the authors combined the dominant set with the resolving set and developed the idea of the dominant metric dimension in graph theory. A resolving set U ⊆ V(G) which is also a dominant set is called the dominant resolving set. A dominant metric basis is a dominant resolving set that contains the minimum vertices. The cardinality of a dominant metric basis is called dominant metric dimension of G. In graph theory metric dimension is a key research area because of its various applications like sensor networking, operation research problems, linear optimization problems, drug discoveries, robot navigation, classification of chemical compounds, source localization, comparing the interconnected networks, detecting network motifs, embedding biological sequence data and in image processing. Dominant and fault tolerant metric dimension problem is just like an optimization problem in which we have to obtain the best solution from all the possible solutions. Now a days, whole industry is changing into automation industry. The need of automatic machines is increasing day by day. As in a restaurant robots are working on the places of waiters. In order to minimize our cost and energy, we need a locating set such that minimum number of automatic machines can move or communicate with each other in a network. Dominant and fault tolerant metric dimension of a graph provide us locating sets, which are helpful for automatic machines. The contradiction method, also known as proof by contradiction, indirect proof, is a common mathematical proof technique that establishes the truth of a statement by assuming the opposite of the statement and showing that the assumption leads to a contradiction. Mathematical induction is a method for proving that a mathematical statement is true for all natural numbers. In order to compute the dominant and fault-tolerant metric dimension of graphs, authors use contradiction and mathematical induction methods. In this thesis, we also use these methods to compute dominant and fault-tolerant metric dimension of graphs. In this research work, we obtain minimum dominant resolving sets of few connected graphs such as wheel, anti-web wheel, gear graphs, generalized anti-web wheel and generalized anti-web gear graphs. We also study the dominant metric dimension of aforesaid graphs. Furthermore, we obtain the fault-tolerant metric dimension of generalized anti-web wheel and generalized anti-web gear graphs. We also study the boundedness of aforementioned connected graphs. Moreover, we classify non bipartite graphs whose metric and dominant metric dimensions are equal. Upon introducing the metric dimension a distance-based parameter, the concept of fault-tolerant metric dimension appeared in the literature. For the dominant metric dimension of graphs introduced by the authors, a fault-tolerant parameter is needed. In this research, we introduce the concept of fault-tolerant dominant metric dimension of graphs and initiate research related to its mathematical properties. We compare fault-tolerant resolving sets with fault-tolerant dominant resolving sets. We present a method to obtain the aforesaid dimension of graphs and expressions for a family of wheel-related graphs.