resume | schedule | research | publication | teaching | academic family tree | student | erdös number | contact | miscellaneous

 

Please visit our group, The Combinatorial Mathematics Group, page to get more information about the projects and the people involved.

 

Extremal graphs and digraphs 

 

 

In the design of large interconnection networks there is usually a need for each pair of nodes to communicate or to exchange data efficiently, but it is impractical to directly connect each pair of nodes. Therefore, the problem of designing networks is concerned with two constraints: the limitation of the number of connections attached to every node and also the limitation of the number of intermediate nodes on the communication route between any two given nodes.

 

The first constraint is modeled by the degree of a node. The second constraint is modeled by distance parameters of a graph, such as diameter, radius, or average distance. We are particularly interested in the diameter parameter. 

 

Thus in graph theoretical terms, the problem becomes

The Degree/Diameter Problem

For given d and k, find graphs (if the network is unidirectional) or digraphs (for a bidirectional network) of maximum degree or out-degree d and diameter at most k with maximum number of vertices nd,k.

A well-known upper bound for nd,k is the so-called Moore bound that was first proposed by E.F. Moore. 

 

In general, the degree/diameter problem is not an easy problem to solve. For instance, the existence of Moore graph of degree 57 and diameter 2 is a long-standing (46 years and counting!) and famous open problem in Graph Theory. Both approaches that are used to attack the problem, i.e.,

·   establishing upper bound for nd,k by proving the nonexistence of graphs or digraphs with order "close" to the Moore bound and

·   establishing lower bound for nd,k by constructing large graphs and digraphs

progressed slowly during the years; the gaps between the two bounds are still enormous, especially for large values of d and k.

 

An up-to-date table of largest known graph for small values of d and k can be found here.

 

Our contributions towards the solutions of the problem include: The Neighbourhood Theorem (a powerful tool to improve non-existence of graphs with certain properties), the non-existence of graphs with degree 4 and order two less than Moore bound and, planar (and other surfaces) version of the degree/diameter problem.  

 

A more complete description of the degree/diameter problem is provided in ?.

 

Related publications:

·         Mirka Miller, Minh Hoang Nguyen and Rinovia Simanjuntak, Repeats in graphs and digraphs, Proceedings of EuroComb 2003, to appear.

·         Rinovia Simanjuntak and Mirka Miller, Neighbourhood Lemma for graphs of order two less than the Moore bound, Technical Report No. CS02012 (2002) School of Electrical Engineering and Computer Science, The University of Newcastle Australia.

·         Rinovia Simanjuntak and Mirka Miller, Largest planar digraphs of diameter 2, Proceedings of Thirteenth Australasian Workshop of Combinatorial Algorithm, Fraser Island, Australia, 7-10 July 2001.

·         Rinovia Simanjuntak and Edy Tri Baskoro, The uniqueness of almost Moore digraph with degree 4 and diameter 2, Proceeding  of SEAMS-GMU International Confference 1999 on Mathematics and its Applications, Jogjakarta, Indonesia, 26-29 July 1999. See also Proc. ITB Vol 32 No 1 (2000) 7-11.

 

 

Magic and antimagic graph labelings 

 

 

A labeling (or valuation) of a graph is any mapping that sends some set of graph elements to a set of numbers (usually positive or non-negative integers). If the domain is the vertex-set or the edge-set or both, the labelings are called respectively vertex-labelings or edge-labelings or total-labelings. A complete survey of graph labelings, written by Joseph Gallian, can be downloaded in The Electronic Journal of Combinatorics.

 

I am working on some special types of graph labelings that are called magic and antimagic graph labelings. We especially consider the so-called (a,d)-antimagic labelings; and in this one type of graph labelings we have devised a new terminology for defining such labelings and found all posible combinations of the labelings within our terminology, studied properties of the labelings, and constructed labelings for several families of graphs.

 

Together with Chris Rodger, we also introduced labelings that are both magic and distance-based; and we called such labelings the d-magic labelings, with d denote the desirable distance in the labelings.

 

With Edy Baskoro, we are working on the application of the magic labeling to secret sharing scheme, by introducing a set called a critical set of a particular magic labeling of a graph.

 

Related publications:

·         Mirka Miller, Chris Rodger and Rinovia Simanjuntak, Distance magic labeling of graphs, Australasian J. of Combinatorics, to appear.

·         Martin Bača, François Bertault, James MacDougall, Mirka Miller, Rinovia Simanjuntak, and Slamin, Vertex-antimagic total labelings of graphs, Discussiones Mathematicae Graph Theory, to appear. 

·         Slamin, Martin Bača, Yuqing Lin, Mirka Miller, and Rinovia Simanjuntak, Edge-magic total labelings of wheels, fans and friendship graphs, Bulletin of ICA, 35 (2002) 89-98.

·         Martin Bača, Yuqing Lin, Mirka Miller, Rinovia Simanjuntak, New constructions of magic and antimagic graph labelings, Util. Math. 60 (2001) 229-239.

·         Mirka Miller, Chris Rodger and Rinovia Simanjuntak, On distance magic graphs, Proceedings of Twelfth Australasian Workshop of Combinatorial Algorithm, Lembang, Indonesia, 14-17 July 2001 .

·         YuQing Lin, Mirka Miller, Rinovia Simanjuntak, and Slamin, Magic and antimagic labelings of wheels, Proceedings of Eleventh Australasian Workshop of Combinatorial Algorithm, Hunter Valley, Australia, 29 July - 1 August 2000. 

·         Rinovia Simanjuntak, Mirka Miller, and François Bertault, Two new (a,d)-antimagic graph labelings, Proceedings of Eleventh Australasian Workshop of Combinatorial Algorithm, Hunter Valley, Australia, 29 July - 1 August 2000. 

·         Rinovia Simanjuntak and Mirka Miller, A survey of (a,d)-antimagic graph labelings, MIHMI (Journal of the Indonesian Mathematical Society) Vol. 6 No 5, Prosiding Konperensi Nasional Matematika X, Bandung, Indonesia, 17-20 July 2000. 

 

 

 Resolvability and metric dimension in graphs

 

 

Comming soon.

 

 

 

Home

presented in English and Indonesian

@2003-2006 rino ~ e-mail me

last updated: 4 December 2006