Nordhauss Gaddum Type Results for Total Resolving Number of Graphs and Their Edge Cycle Graphs

Author(s): N Shunmugapriya

Abstract:

Let G = (V, E) be a simple connected graph. The distance between two vertices u and v of a connected graph G is the length of the shortest u − v path in G and is denoted by d(u, v). A vertex of degree one in a graph G is called a pendant vertex. The vertex that is adjacent to a pendent vertex is called a support vertex. Let p denote the number of pendant vertices of G and s denote the number of support vertices of G. A vertex of degree at least 3 in a graph G is called a major vertex of G. Any end-vertex u of G is said to be a terminal vertex of a major vertex v of G if d(u, v) < d(u, w) for every other major vertex w of G. The terminal degree ter(v) of a major vertex v is the number of terminal vertices of v. A major vertex v of G is an exterior major vertex of G if it has positive terminal degree. Let σ(G) be the sum of the terminal degrees of the major vertices of G and ex(G) be the number of exterior major vertices of G. Let θ(G) be the number of exterior major vertices of G with terminal degree at least two. An ordered subset W of V is said to be a resolving set of G if every vertex is uniquely determined by its vector of distances to the vertices in W. The minimum cardinality of a resolving set is called the resolving number of G and is denoted by r(G). Total resolving number as the minimum cardinality taken over all resolving sets in which ⟨W ⟩ has no isolates and it is denoted by tr(G). An edge cycle graph of a graph G is the graph G(Ck) formed from one copy of G and |E(G)| copies of Pk, where the ends of the ith edge are identified with the ends of ith copy of Pk. In this dissertation, we obtain the bounds of the sum of total resolving number of graphs and their edge cycle graphs and characterize the extremal graphs.

Keywords: Resolving number, total resolving number, edge cycle graph

Pages: 151-155      |       11 View       |       1 Download