Studies on some generalizations of line graph and the power domination problem in graphs

Department of Mathematics, Cochin University of Science and Technology

Median computation in graphs using consensus strategies

Following the Majority Strategy in graphs, other consensus strategies, namely Plurality Strategy, Hill Climbing and Steepest Ascent Hill Climbing strategies on graphs are discussed as methods for the computation of median sets of pro¯les. A review of algorithms for median computation on median graphs is discussed and their time complexities are compared. Implementation of the consensus strategies on median computation in arbitrary graphs is discussed

A Study of Some Centrality Measures in Graphs

Centrality is in fact one of the fundamental notions in graph theory which has established its close connection with various other areas like Social networks, Flow networks, Facility location problems etc. Even though a plethora of centrality measures have been introduced from time to time, according to the changing demands, the term is not well defined and we can only give some common qualities that a centrality measure is expected to have. Nodes with high centrality scores are often more likely to be very powerful, indispensable, influential, easy propagators of information, significant in maintaining the cohesion of the group and are easily susceptible to anything that disseminate in the network.

Some Problems In Algebra And Topology A Study Of Fuzzy Convexity With Special Reference To Separation Properties

This thesis is a study of abstract fuzzy convexity spaces and fuzzy topology fuzzy convexity spaces No attempt seems to have been made to develop a fuzzy convexity theoryin abstract situations. The purpose of this thesis is to introduce fuzzy convexity theory in abstract situations

‘Studies on some topics in product graphs’

For routing problems in interconnection networks it is important to find the shortest containers between any two vertices, since the w-wide diameter gives the maximum communication delay when there are up to w−1 faulty nodes in a network modeled by a graph. The concept of ‘wide diameter’ was introduced by Hsu [41] to unify the concepts of diameter and The concept of ‘domination’ has attracted interest due to its wide applications in many real world situations [38]. A connected dominating set serves as a virtual backbone of a network and it is a set of vertices that helps in routing. In this thesis, we make an earnest attempt to study some of these notions in graph products. This include, the diameter variability, the diameter vulnerability, the component factors and the domination criticality.connectivity

Computing median and antimedian sets in median graphs

The median (antimedian) set of a profile π = (u1, . . . , uk) of vertices of a graphG is the set of vertices x that minimize (maximize) the remoteness i d(x,ui ). Two algorithms for median graphs G of complexity O(nidim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes

On the remoteness function in median graphs

A profile on a graph G is any nonempty multiset whose elements are vertices from G. The corresponding remoteness function associates to each vertex x 2 V.G/ the sum of distances from x to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph G whose remoteness function is maximum (antimedian set of G) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph G on n vertices and m edges, decides in O.mlog n/ time whether G is a median graph with geodetic number 2

Betweenness Centrality in Some Classes of Graphs

There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.

Studies on Fuzzy Graphs

In this thesis an attempt to develop the properties of basic concepts in fuzzy graphs such as fuzzy bridges, fuzzy cutnodes, fuzzy trees and blocks in fuzzy graphs have been made. The notion of complement of a fuzzy graph is modified and some of its properties are studied. Since the notion of complement has just been initiated, several properties of G and G available for crisp graphs can be studied for fuzzy graphs also. Mainly focused on fuzzy trees defined by Rosenfeld in [10] , several other types of fuzzy trees are defined depending on the acyclicity level of a fuzzy graph. It is observed that there are selfcentered fuzzy trees. Some operations on fuzzy graphs and prove that complement of the union two fuzzy graphs is the join of their complements and complement of the join of two fuzzy graphs is union of their complements. The study of fuzzy graphs made in this thesis is far from being complete. The wide ranging applications of graph theory and the interdisciplinary nature of fuzzy set theory, if properly blended together could pave a way for a substantial growth of fuzzy graph theory.

Clique Irreducibility of Some Iterative Classes of Graphs

In this paper, two notions, the clique irreducibility and clique vertex irreducibility are discussed. A graph G is clique irreducible if every clique in G of size at least two, has an edge which does not lie in any other clique of G and it is clique vertex irreducible if every clique in G has a vertex which does not lie in any other clique of G. It is proved that L(G) is clique irreducible if and only if every triangle in G has a vertex of degree two. The conditions for the iterations of line graph, the Gallai graphs, the anti-Gallai graphs and its iterations to be clique irreducible and clique vertex irreducible are also obtained.

On Distance Energy of Graphs

The D-eigenvalues of a graph G are the eigenvalues of its distance matrix D, and the D-energy ED(G) is the sum of the absolute values of its D-eigenvalues. Two graphs are said to be D-equienergetic if they have the same D-energy. In this note we obtain bounds for the distance spectral radius and D-energy of graphs of diameter 2. Pairs of equiregular D-equienergetic graphs of diameter 2, on p = 3t + 1 vertices are also constructed.

A Note on Energy of Some Graphs

Eigenvalue of a graph is the eigenvalue of its adjacency matrix. The energy of a graph is the sum of the absolute values of its eigenvalues. In this note we obtain analytic expressions for the energy of two classes of regular graphs.

A Note On Some Domination Parameters in Graph Products

In this paper, we study the domination number, the global dom ination number, the cographic domination number, the global co graphic domination number and the independent domination number of all the graph products which are non-complete extended p-sums (NEPS) of two graphs.