Please visit our group, The Combinatorial Mathematics Group, page to get more information about the projects and the people involved.
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
In general, the degree/diameter problem is
not an easy problem to solve. For instance, the existence of
· 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
A more complete description of the degree/diameter problem is provided in ?.
· 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)
· 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.
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.
· 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.
presented in English and Indonesian
@2003-2006 rino ~ e-mail me
last updated: 4 December 2006