Browsing by Author "Muhammad Kamran Aslam"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Fractional metric dimensions and antimagic valuations of graphs
    (UMT Lahore, 2022-10-21) Muhammad Kamran Aslam
    Let G(V (G), E(G)) be a simple, finite and undirected graph with vertex set V (G) and edge set E(G) ⊆ V (G) × V (G), where |V (G)| and |E(G)| are called order and size of the graph G respectively. A valuation of a graph is a bijection that maps its elements vertices, edges or both to real numbers. A valuation is called total if its domain is both the set of vertices and edges. Thus, a valuation λ : V (G) ∪ E(G) → {1, 2, 3, . . . , |V (G)| + |E(G)|} is called an edge magic total valuation if the edge-weight λ(x) + λ(xy) + λ(y) = c for each edge xy ∈ E(G), where c is some constant. For an edge-magic total valuation, if we assign the smallest labels to the vertices then it is called a super edge magic total valuation. More generally, a total valuation is called an ( ̄a, d)-edge antimagic total valuation if each edge-weight forms an arithmetic progression with initial term ̄a and common difference d. Finally, an ( ̄a, d)-edge antimagic total valuation is called a super ( ̄a, d)-edge antimagic total if the smallest labels are awarded to the vertices of G. The work of valuation has its roots in the work of Kotzig and Rosa (1970). Enomoto et al. (1998) proposed the conjecture that every tree is super ( ̄a, d)-edge antimagic total graph with d = 0. Lee and Shan (2002) gave the verification of the aforementioned conjecture for trees with at most 17 vertices using computer aid. Suppose that W = {w1, w2, w3, . . . , wk} ⊆ V (G), then a k-tuple metric form of s ∈ V (G) with respect to W is represented by r(s|W) = (d(s, w1), d(s, w2), d(s, w3), . . . , d(s, wk)). The set W becomes a resolving set if each pair of distinct nodes of G has distinct metric form. The resolving set with the minimum number of elements forms the metric basis for G and its cardinality is called the metric dimension of G. A vertex c is said to resolve a pair of vertices {s, t} if d(s, c) 6 = d(t, c). A resolving neighbourhood set for a pair of vertices {s, t} ⊆ V (G) (R{s, t}) is a set comprising of all the vertices that resolve the pair {s, t} i.e R{s, t} = {c ∈ V (G)|d(c, s) 6 = d(c, t)}. A function μ : V (G) → [0, 1] is called resolving function if for each resolving neighbourhood set R{s, t}, μ(R{s, t}) = ∑ c∈R{s,t} μ(c) ≥ 1. A resolving function μ is called minimal resolving function if for any function γ : V (G) → [0, 1] such that γ ≤ μ and μ(c) 6 = γ(c) for at least one c ∈ G that is not the resolving function of G. The fractional metric dimension of a graph G is defined as f dim(G) = ζ, where ζ = min{|μ| : μ is minimal resolving function of G}. The bases of fractional metric dimension can be found in the locating sets introduced by Slater (1975). Armugam and Mathew (2012) gave the formal definition of fractional metric dimension. Feng et al. (2014) evaluated the bound of fractional metric dimension of regular and vertex transitive graphs. In the former part of the thesis, we have verified the conjecture of Enomoto et al. for the subclasses of tree namely subdivided caterpillars. We have also found the bounds of minimum and maximum values of edge weight ̄a for the same subclasses for super ( ̄a, d)-edge antimagic total valuation. By constructing different illustrations and examples we have constructed its valuations scheme for d = 0, 1, 2. Moreover, we have also formed the algorithm for the proposed valuation scheme. In the later part of this thesis, we have done three main theoretical developments regarding the fractional metric dimensions of connected graphs. The first development is the bounds of fractional metric dimension for the class of connected graphs that includes non-regular and non-vertex transitive graphs. The second development is the classifications of graphs with fractional metric dimension as unity and third development is related to the improvement of the lower bound of fractional metric dimension from unity to ratio of the order of the graph and the cardinality of the maximum resolving neighbourhood set. Apart from the aforesaid developments, we have also evaluated the fractional metric dimensions of grid-like graphs, circular graphs, convex polytopes (Type I and Type II), web-related graphs and tetrahedral diamond lattice. Also this study includes the finding of results related to the local fractional metric dimension of rotationally symmetric and planar graphs, web-related graphs and convex polytopes. Moreover, the boundedness and unboundedness of all the obtained results is also computed with the condition that the order of understudy graphs approaches to infinity.