Recent Progress on the Partition Dimension of Graphs

Prof. Dr. Edy Tri Baskoro
Faculty of Mathematics and Natural Sciences
Institut Teknologi Bandung

Abstract

The study of the partition dimension of connected graphs was introduced by GChartrand, E. Salehi and P. Zhang (1998) with the aim of finding a new way in attacking the problem of determining the metric dimension of graphs. The notion of graph metric dimension itself was initially studied by by Slater (1975) and Harary & Melter (1976).

Let G(V,Ebe a connected graph. Let \Pi = {L1L2, …, Lbe an ordered partition of V(G). The representation of any vertex v with respect to \Pi, denoted by r (v, \Pi), is defined as the t-vector with the elements are all distances between v to the partition classes in \Pi, namely r(v, \Pi) = (d(vL1), d(vL2), …, d(vLt)). The partition \Pi is called a resolving partition if the representations of all vertices in G are different. We define the partition dimension of graph G by the minimum integer k such that G possess a resolving k-partition.

The study of graph partition dimension has received much attention in the last two decades. In general, finding the partition dimension of a graph in general is one of interesting and difficult problems in graph theory.  There are only a few classes of graphs whose partition dimensions can be determined. For instance, for trees, we have known the partition dimensions of paths, stars, caterpillar, lobsters and other specific trees. However, the remaining ‘huge’ classes of trees are stiil unknown for their partition dimensions. The charactering study all graphs with a certain partition dimension has been also conducted. In this paper, we will discuss the current progress of the partition dimension of graphs.

Edy

Prof. Dr. Edy Tri Baskoro
Faculty of Mathematics and Natural Sciences

Institut Teknologi Bandung

Edy Tri Baskoro was born in Jombang, Indonesia 22 May 1964, received his B.Sc degree in mathematics from Institut Teknollogi Bandung (ITB) Indonesia in 1987, and his PhD degree from the University of Newcastle, Australia in 1996. Since then he has held a senior academic position at ITB. He is Dean of Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung for the period of 2015-2020. Since July 2006, he has been honoured a professor in mathematics of ITB. He has been also an adjunct professor at the University of Newcastle Australia and the Abdus Salam School of Mathematical Sciences, GC University, Lahore Pakistan.

His main research interests are graph theory and combinatorics. He is a pioneer in the development of graph theory and combinatorics in Indonesia. For his contributions to these fields he has been awarded First Prize National Best Lecturer (2008), Habibie Award in Basic Science Research (2009), Australian Alumni Award for Excellence in Education (2009), and the Extraordinary Intellectual Quality Award (2010). Satyalancana Karya Satya from the President of Indonesia (2013) and Ganesa Cendekia Widya Adiutama from ITB (2014). He also plays a significant role in the development of mathematics in South East Asia region. He was the President of South East Asian Mathematical Society (2014- 2015), He has been engaged with CIMPA as a member of Scientific Committee since 2009 until now. He has also contributed to the development of national standards for education from primary school to higher education in Indonesia as the member of the Board of National Standards for Education 2005-2014. As of Dec 2018, he has published over 153 research papers in international reputable journals and produced over 28 PhD graduates.