Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
2 results
Search Results
Item On strong (weak) independent sets and vertex coverings of a graph(2007) Kamath, S.S.; Bhat, R.S.A vertex v in a graph G = (V, E) is strong (weak) if deg (v) ? deg (u)(deg (v) ? deg (u)) for every u adjacent to v in G. A set S ? V is said to be strong (weak) if every vertex in S is a strong (weak) vertex in G. A strong (weak) set which is independent is called a strong independent set [SIS] (weak independent set [WIS]). The strong (weak) independence numbers ? = s ? (G) (w ? = w ? (G)) is the maximum cardinality of an SIS (WIS). For an edge x = uv, v strongly covers the edge x if deg (v) ? deg (u) in G. Then u weakly covers x. A set S ? V is a strong vertex cover [SVC] (weak vertex cover [WVC]) if every edge in G is strongly (weakly) covered by some vertex in S. The strong (weak) vertex covering numbers ? = s ? (G)(w ? = w ? (G)) is the minimum cardinality of an SVC (WVC). In this paper, we investigate some relationships among these four new parameters. For any graph G without isolated vertices, we show that the following inequality chains hold: s ? ? ? ? s ? ? w ? and s ? ? w ? ? ? ? w ?. Analogous to Gallai's theorem, we prove s ? + w ? = p and w ? + s ? = p. Further, we show that s ? ? p - ? and w ? ? p - ? and find a necessary and sufficient condition to attain the upper bound, characterizing the graphs which attain these bounds. Several Nordhaus-Gaddum-type results and a Vizing-type result are also established. © 2006.Item Graph energy centrality: a new centrality measurement based on graph energy to analyse social networks(Inderscience Publishers, 2022) Mahadevi, S.; Kamath, S.S.; Shetty D, P.D.Critical node identification, one of the key issues in social network analysis, is addressed in this article with the development of a new centrality metric termed graph energy centrality (GEC). The fundamental idea underlying this GEC measure is to give each vertex a centrality value based on the graph energy that results from vertex elimination. We show that the GEC of each vertex is asymptotically equal to two for cycle graphs and exactly equal to two for complete graphs. We further demonstrate that star graphs can be ranked using only two GEC values, whereas path graphs can be ranked using a maximum of ⌈n+12 ⌉ values. The proposed algorithm takes O(n3) time complexity to rank all vertices; hence an optimised algorithm is also being proposed considering only a few classes of graphs. The proposed algorithm ranks the nodes based on the collaborative measure of eigenvalues. © 2022 Inderscience Enterprises Ltd.. All rights reserved.