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

Department of Mathematics, Cochin University of Science and Technology

Strongly distance-balanced graphs and graph products

A graph G is strongly distance-balanced if for every edge uv of G and every i 0 the number of vertices x with d.x; u/ D d.x; v/ 1 D i equals the number of vertices y with d.y; v/ D d.y; u/ 1 D i. It is proved that the strong product of graphs is strongly distance-balanced if and only if both factors are strongly distance-balanced. It is also proved that connected components of the direct product of two bipartite graphs are strongly distancebalanced if and only if both factors are strongly distance-balanced. Additionally, a new characterization of distance-balanced graphs and an algorithm of time complexity O.mn/ for their recognition, wheremis the number of edges and n the number of vertices of the graph in question, are given

Median Sets and Median Number of a Graph

A profile is a finite sequence of vertices of a graph. The set of all vertices of the graph which minimises the sum of the distances to the vertices of the profile is the median of the profile. Any subset of the vertex set such that it is the median of some profile is called a median set. The number of median sets of a graph is defined to be the median number of the graph. In this paper, we identify the median sets of various classes of graphs such as Kp − e, Kp,q forP > 2, and wheel graph and so forth. The median numbers of these graphs and hypercubes are found out, and an upper bound for the median number of even cycles is established.We also express the median number of a product graph in terms of the median number of their factors.

On The Center Sets and Center Numbers of Some Graph Classes

For a set S of vertices and the vertex v in a connected graph G, max x2S d(x, v) is called the S-eccentricity of v in G. The set of vertices with minimum S-eccentricity is called the S-center of G. Any set A of vertices of G such that A is an S-center for some set S of vertices of G is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, Km,n, Kn −e, wheel graphs, odd cycles and symmetric even graphs and enumerate them for many of these graph classes. We also introduce the concept of center number which is defined as the number of distinct center sets of a graph and determine the center number of some graph classes

Content aggregation on knowledge bases using graph clustering

Recently, research projects such as PADLR and SWAP have developed tools like Edutella or Bibster, which are targeted at establishing peer-to-peer knowledge management (P2PKM) systems. In such a system, it is necessary to obtain provide brief semantic descriptions of peers, so that routing algorithms or matchmaking processes can make decisions about which communities peers should belong to, or to which peers a given query should be forwarded. This paper proposes the use of graph clustering techniques on knowledge bases for that purpose. Using this clustering, we can show that our strategy requires up to 58% fewer queries than the baselines to yield full recall in a bibliographic P2PKM scenario.

Understanding Subsystems in Biology through Dimensionality Reduction, Graph Partitioning and Analytical Modeling

Biological systems exhibit rich and complex behavior through the orchestrated interplay of a large array of components. It is hypothesized that separable subsystems with some degree of functional autonomy exist; deciphering their independent behavior and functionality would greatly facilitate understanding the system as a whole. Discovering and analyzing such subsystems are hence pivotal problems in the quest to gain a quantitative understanding of complex biological systems. In this work, using approaches from machine learning, physics and graph theory, methods for the identification and analysis of such subsystems were developed. A novel methodology, based on a recent machine learning algorithm known as non-negative matrix factorization (NMF), was developed to discover such subsystems in a set of large-scale gene expression data. This set of subsystems was then used to predict functional relationships between genes, and this approach was shown to score significantly higher than conventional methods when benchmarking them against existing databases. Moreover, a mathematical treatment was developed to treat simple network subsystems based only on their topology (independent of particular parameter values). Application to a problem of experimental interest demonstrated the need for extentions to the conventional model to fully explain the experimental data. Finally, the notion of a subsystem was evaluated from a topological perspective. A number of different protein networks were examined to analyze their topological properties with respect to separability, seeking to find separable subsystems. These networks were shown to exhibit separability in a nonintuitive fashion, while the separable subsystems were of strong biological significance. It was demonstrated that the separability property found was not due to incomplete or biased data, but is likely to reflect biological structure.

Web Graph

Slides and an essay on the Web Graph, search engines and how Google calculates Page Rank

Graph Theory and Social Networks Tutorial

For COMP60

Speak to me graph.

Se compone de diez actividades destinadas a ayudar a los profesores a desarrollar las capacidades de análisis e interpretación de datos de los alumnos de ciencias. Cada actividad incluye una hoja de preguntas y una hoja de datos, ésta última, disponible en archivos de Excel, para que los estudiantes utilicen las nuevas tecnologías para crear gráficos. Los ejercicios están pensados para el nivel superior de la etapa 2 (key stage 2) del currículo nacional inglés y para la etapa 3, es decir, para primaria y secundaria, y se centran en el contenido de 'Sc2 Life and Living Proceses'.

Visualización geográfica 3D mediante un API Universal y políglota. Acercando los globos virtuales al desarrollador de mashups de mapas

La librería Javascript de código abierto Mapstraction permite al desarrollador abstraerse de las pequeñas diferencias entre las distintas APIs de mapas. Mediante el uso de esta librería, el creador de mashups de mapas puede implementar sus aplicaciones tan sólo una vez con la posibilidad de cambiar de proveedor de mapas de forma sencilla, si así se requiere. En el presente trabajo se ha extendido la funcionalidad de esta librería para el soporte de funcionalidad 3D propia de los globos virtuales, de la que hasta ahora carecía: selección del ángulo de visión, extrusión del terreno, estereoscopía 3D o inclusión de modelos tridimensionales, por citar algunas. Además, se ha realizado una integración del globo virtual de la Nasa, de código abierto, World Wind, antes apenas utilizado para el desarrollo de mashups al no disponer de un API Javascript para su fácil incorporación

A Note on the periodic orbits and topological entropy of graph maps

This paper deals with the relationship between the periodic orbits of continuous maps on graphs and the topological entropy of the map. We show that the topological entropy of a graph map can be approximated by the entropy of its periodic orbits

IDELab MapstractionInteractive: API Universal y Políglota

Continuamente aparecen nuevas plataformas de gestión de cartografía web, con el inconveniente de que cada una de ellas utiliza un API propia. Dada la gran heterogeneidad de APIs de Mapas existente, sería conveniente disponer de una librería de mapas capaz de abstraer al desarrollador de las pequeñas diferencias entre ellas. Este es el objetivo de la librería Javascript de código abierto Mapstraction. Este tipo de API recibe el nombre de «API Universal y Políglota». Gracias a Mapstraction se pueden desarrollar aplicaciones en las que el usuario puede visualizar la información cartográfica con varios proveedores, pero presenta el inconveniente de no proporcionar mecanismos de creación y/o edición. En este documento se recogen las principales novedades que presenta la librería IDELab MapstractionInteractive, una extensión de Mapstraction que ofrece nueva funcionalidad para solventar las carencias de ésta. Las nuevas funcionalidades implementadas para los proveedores que se incluyen dentro de la librería brindan al usuario la posibilidad de poder editar y crear geometrías sobre el mapa (puntos, líneas y polígonos). Por otra parte, también se implementan dentro de la librería nuevos eventos para los mapas, de forma que el programador puede tener un mayor control de lo que el usuario hace sobre éstos