Grant: Discovery Grants Program - Individual
Université de Montréal
$10,000.00
Algebraic problems in graph theory
FY 2006-07
Summary
A convex set of nodes in a graph (network) is one in which transmission of information is as efficient as it can be in the sense that no shortest path between any two nodes goes outside the set. We have introduced a parameter (called the prehull number) which measures the intrinsic non-convexity of a network: the higher the value of this parameter, the less convex the overall structure of the network is considered to be. From this point of view it is of interest to obtain as much information as possible about those networks for which the prehull number is small. This is one of the major themes of this proposal. We are also applying this concept to a certain type of graphs, called benzenoid graphs, that arise in organic chemistry, where a high degree of convexity of the graph is related to the stability of the corresponding molecule. We also consider networks in which all nodes are indistinguishable from each other because of the symmetry properties of the network ("vertex-transitive networks). Some of the most frequently employed interconnection networks are of this type. The problem to be considered there is the existence of so-called uniform geodesic routings (i.e. routings by shortest paths geodesics) in which every node lies on the same number of paths of the routing. We propose to give an algebraic characterisation of those networks that admit such routings, using the fact that vertex-transitive networks can be represented by a certain type of quasigroups.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
7315-2006
Name nom
Sabidussi, Gert
Department département
Mathématiques et de statistique
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2006
Competition year année de concours
2006
Award amount
10000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
5
Application title
Algebraic problems in graph theory
Keyword
NA
Application summary
A convex set of nodes in a graph (network) is one in which transmission of information is as efficient as it can be in the sense that no shortest path between any two nodes goes outside the set. We have introduced a parameter (called the prehull number) which measures the intrinsic non-convexity of a network: the higher the value of this parameter, the less convex the overall structure of the network is considered to be. From this point of view it is of interest to obtain as much information as possible about those networks for which the prehull number is small. This is one of the major themes of this proposal. We are also applying this concept to a certain type of graphs, called benzenoid graphs, that arise in organic chemistry, where a high degree of convexity of the graph is related to the stability of the corresponding molecule. We also consider networks in which all nodes are indistinguishable from each other because of the symmetry properties of the network ("vertex-transitive networks). Some of the most frequently employed interconnection networks are of this type. The problem to be considered there is the existence of so-called uniform geodesic routings (i.e. routings by shortest paths geodesics) in which every node lies on the same number of paths of the routing. We propose to give an algebraic characterisation of those networks that admit such routings, using the fact that vertex-transitive networks can be represented by a certain type of quasigroups.