Bounds on the Order of Graphs under Degree and Distance Constraints

The main aim is to find the best possible general bounds on the number of nodes in a network, modelled as a graph, given constraints with respect to the maximum possible number of connections at any node, and given the maximum possible delay, or distance (measured by the number of intermediate nodes along a shortest path between any two nodes). The project includes many related subproblems, such as:

Supported by ARC Grant DP0208238

Applications of Combinatorics to Data Security

Research in data security is being carried out mainly in the areas of statisticaldatabase security (that is, the prevention of data inference) and in secret sharing (for passwords or cryptographic keys), with a special focus on applications in health informatics. The security problem in statistical databases is to find suitable mechanisms for the prevention of the inference of individual data items from the results of statistical queries concerning subsets of the records in a database. We study the security level versus the usability of the database and the exactness of the query responses. Secret sharing can be used for secret/shared/hierarchic access to a computer system or a database. We are considering the use of combinatorial structures, graphs and graph labeling for the implementation of schemes which will allow for an emergency access and which will reflect the hierarchic structure of employees in an organisation.

Topology of Dynamic Networks

The main aim is to investigate properties of real dynamic networks such associal networks or the Internet. Large dynamic networks such as the Internet are difficult to explore. Dynamic networks are usually neither well-structured nor random. It is a challenge to discover some new properties of such networks but the rewards can be quite significant as the new knowledge can be applied to optimise algorithms operating on such networks. The project includes many related subproblems, such as:

Structural Properties of Eccentric Graphs and Digraphs

An eccentric digraph of a graph contains the same set of vertices but arcs that correspond to the relation “is an eccentric node of”, that is, there are arcs from a node to those nodes which are furthest from the given node. We study the structural properties of eccentric digraph. Since we deal only with finite graphs and digraphs, every iteration of eccentric digraphs consists of a cycle and a tail. We study the properties of eccentric digraph iterations, in particular, the possible lengths of the tails and periods.

Graph Labeling and its Applications

Our interest is on one hand in summable graph labelings, such as sum, mod sum and integral sum labelling; and on the other hand, in the magic and antimagic graph labelling. Sum graph labelling can be used as an alternative method for defining and storing graphs. It would be interesting to find out if or when this method could be practically applicable for graph structures stored electronically.