megagrad

is an Indo-Slovenian Joint Research Project on Metric Graph Theory and Graph Products started in 2010. This joint project helps the researchers from India and Slovenia to collaborate and collectively contribute to the highly emerging field of Metric Graph Theory. The first contacts between the research groups in Discrete Mathematics at the University of Kerala and the University of Maribor were due to invited lectures that Professor Sandi Klavˇzar gave at the DST sponsored international instructional workshop on Convexity in Discrete Structures held in Trivandrum in 2006. The discussions there and later cooperation led to the first joint paper (Kannan B, Manoj Changat and Sandi Klavˇzar,The median function on graphs with bounded profiles, Discrete Appl. Math. 156 (2008)2882-2889.) This good experience led to the first bilateral venture which was a joint research project on Metric Graph Theory and Applications (2006-2008). The project was an eminent success. Since then the Researchers from India and Slovenia have been exchanging ideas and continuing the collaboration which is now referred as MEGAGRAD which focusses on the identified common areas of interest on “Metric Graph Theory and Graph Products”.

The International Scenario of Metric Graph Theory
The notion of distance meaning “geodesic” is a generalization of the notion of “straight line”. It is a basic concept in Geometry which plays an important role in graph theory. A graph is a pair G = (V,E), where V is a set, called set of vertices of the graph G, and E is a set of unordered pairs of vertices, called edges of the graph G. A detailed analysis of many different types of notions of distances is described in the book Dictionary of Distances by Deza and Deza. The specialized branch of graph theory dealing with the notion of distance is called “Metric graph theory”. Metric graph theory is an important branch of discrete mathematics with various applications to different branches of knowledge ranging from computer science, communications, genetics, management science, social choice theory, location and consensus theory. A nice survey of Metric Graph Theory from a geometric point of view is recently carried out by Bandelt and Chepoi (2008).

Mulder attempted the first systematic study of the notion of the intervals (geodesic intervals) in graphs in 1980. He studied many nice properties of the interval function (transit function) on the real line. This led many authors to study important classes of graphs,using the geodesic interval and geodesic convexity as main tools. As a result many important classes of graphs have arised. For example, median graphs.

A survey of different characterizations of median graphs and several structures related to median graphs is done by Klavˇzar and Mulder (1999). Generalizations of median graphs, namely, pseudo median graphs (Bandelt and Mulder, 1992), quasi-median graphs (Bandelt, Mulder and Wilkeit, 1994), recognition algorithms for quasi-median graphs (Hagauer, 1995), relationship between median graphs, semimedian graphs and partial cubes (Imrich, Klavˇzar, Mulder and Skrekovski, 1998), Ptolemic graphs (Farber and Jamison, 1986, 1987), bridged graphs (Farber, 1987) are available in the literature. Many of these classes of graphs possess an isometric embedding (distance preserving map from the vertex set of the graph) into hypercubes or its generalization known as Hamming graphs. There are many generalizations of these hypercube embeddable graphs known as l1- graphs which are graphs scale-embeddable into hypercubes. All these graphs form important classes of graphs from a metric point of view.