Algebraic connectivity and fractional metric dimension of graphs.
Loading...
Date
2021-12-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
UMT Lahore
Abstract
Let G = (V (G), E(G)) be a graph having V (G) = {vi : 1 ≤ i ≤ n} and E(G) ⊆ V (G) × V (G) as the sets of vertices and edges respectively. A graph Gc is called complement of a graph G with vertex-set V (Gc) = V (G) and edge-set E(Gc) = {uv : u, v ∈ V (G), uv /∈ E(G)}. The number of first neighbors of v ∈ V (G) is defined as degree of the vertex v and it is denoted by d(v) or dG(v). For any two vertices x, y ∈ V (G) the distance (d(x, y)) is the length of shortest path between them. The adjacency matrix (A-matrix) of a graph G of order n is defined as A(G) = [ai,j ]n×n such that ai,j = 1 if vi is adjacent to vj and ai,j = 0 otherwise. The degree matrix (D-matrix) of G is defined by D(G) = [ai,j ]n×n such that ai,i = d(vi) and zero otherwise. The Laplacian matrix (L-matrix) of the graph G is denoted as L(G) and defined as L(G) = D(G) − A(G) where, D(G) and A(G) are degree and adjacency matrices of graph G respectively. For 1 ≤ i ≤ n, the eigenvalues μi = μi(G) and eigenvectors Zi = Zi(G) of L-matrix (L(G)) are the L-eigenvalues and the L-eigenvectors of G respectively. The second smallest eigenvalue of the Laplacian matrix of a graph is known as an algebraic connectivity. It is used as a parameter to measure the connectivity of a graph i.e. how well a graph is connected.
Furthermore, any two vertices x, y ∈ V (G) of a simple connected graph G are said to be resolved or distinguished by a vertex z ∈ V (G) if d(x, z) ≠ d(y, z). A set S ⊆ V (G) is called a resolving set of G if each pair of vertices of G is resolved by some vertex in S. A minimum resolving set is known as metric basis and its cardinality is called as metric dimension of the graph G that is denoted by dim(G). For a pair (u, v) of vertices of G, the resolving neighborhood set of G is defined as R(u, v) = {w ∈ V (G) : d(w, u) ≠ d(w, v)}. A resolving function is a real valued function g : V (G) → [0, 1] such that g(R(u, v)) ≥ 1 for each resolving neighborhood of distinct pair of vertices of G, where g(R(u, v)) = ∑ x∈R(u,v) g(x). A resolving function g is called minimal, if there exists a function f : V (G) → [0, 1] such that f ≤ g and f (v) ≠ g(v) for at least one v ∈ V is not a resolving function of G.