Mathematics of relations – a SEA-EU grant 2025 graph theory research project
Project established new results in graph theory, which has numerous real-life applications, with paper submitted to reputable peer-reviewed journal
In 2025, I was one of the three recipients of the SEA-EU grant award by the University of Malta (UM). As a professor at the Department of Mathematics of the University’s Faculty of Science, I am actively engaged in mathematical research.
My grant funded a research project carried out in collaboration with academics from University of Gdańsk (UG) and Gdańsk University of Technology (GUT). UM and UG are members of SEA-EU, an alliance of nine coastal universities across Europe (Cádiz, Brest, Kiel, Gdańsk, Split, Malta, Algarve, Naples, NORD).
The project I led started with a research visit at UG during June 14-28, 2025. I was joined by my two doctoral students, Karl Bartolo and Dayle Scicluna, who were each supported by an Erasmus grant.
The project yielded a research paper that is published on Arxiv, an online repository for preprints, at https://arxiv.org/abs/2602.22980. My co-authors are Karl Bartolo (UM), Magda Dettlaff (UG), Magdalena Lemańska (GUT) and Paweł Żyliński (UG).
The paper was also submitted to a reputable peer-reviewed journal and is undergoing the usual review process. In it, we established new results in graph theory (GT), which is the mathematics of relations and connections. GT has numerous real-life applications, ranging from all forms of networks (social, computer, internet, transport) to chemistry.
In GT, a graph G is not the usual plot but essentially a network consisting of a set of objects, called vertices, together with a set of relations, called edges. If {x, y} is an edge of G, then this signifies that the vertices x and y of G are related. As demonstrated in the figure, a graph can be represented by a simple drawing: each vertex is represented by a point, and each edge is represented by a line joining its two vertices.
The set V(G) of vertices of G is called the vertex set of G. For a subset S of V(G), the closed neighbourhood N[S] consists of the vertices in S together with each vertex that is related to at least one of them. If N[S] is the whole of V(G), then S is called a dominating set of G.
Domination theory is the popular study of dominating sets. In a seminal paper entitled Partial domination � the isolation number of a graph and published in the journal Filomat in 2017, Professors Yair Caro (University of Haifa-Oranim, Israel) and Adriana Hansberg (National Autonomous University of Mexico, Mexico) widened the study of dominating sets to the study of isolating sets. As was the case of domination, the study of isolation has taken GT by storm; it has quickly become one of GT’s most active fields of investigation.
The domination problem is to determine how small a dominating set can be. This is the most natural case of the vast isolation problem. The second one is that of determining how small a subset S of V(G) can be if each edge of G has at least one vertex in N[S]. Such a set S is called an isolating set of G. The size (number of members) of a smallest one is called the isolation number of G.
Edge subdivision is a graph operation that has various applications. It involves ‘inserting a vertex on an edge’. More precisely, it replaces an edge {x, y} by two edges {x, z} and {z, y}, where z is a new vertex (added only for x and y). The abovementioned paper initiated the investigation of how subdividing edges affects the isolation number. It determines the graphs whose isolation number increases upon subdividing an arbitrary edge. It also shows that subdividing all edges, or all but one, always increases the isolation number, and that this result is best possible.
I will take part in the Being SEU-EU Conference 2026 (https://beingsea-eu.ug.edu.pl/conference) at UG from September 15 to 17, where I will share the successful experience of collaborating with the abovementioned academics from Gdańsk with the support of the SEA-EU grant.
Peter Borg
Did you know?
Real-life applications of graph theory:
• Social media platforms model users as vertices, and connections (such as a Facebook friendship) as edges, allowing them to measure the level of influence of a user (network centrality) and provide good friend recommendations.
• PageRank is an algorithm used by Google Search to rank web pages. It was developed by Google founders Larry Page and Sergey Brin at Stanford University in 1996, and named after both the term ‘web page’ and Larry Page. A web page can be represented by a vertex, and a link from a web page to another one can be represented by an edge. PageRank produces a measure of the influence/importance of a web page based on its links.
• Chemical graph theory is the application of graph theory to mathematical modelling of chemical phenomena, where atoms and chemical bonds are represented by vertices and edges, respectively.
For more trivia, see: www.um.edu.mt/think
Photo of the week
The above photo shows Peter Borg (first from right) from the Department of Mathematics of the University of Malta’s Faculty of Science, after he delivered a seminar at University of Gdańsk (UG) on June 18, 2025. It was part of a research visit that took place during June 14 to 28, 2025, funded by a SEA-EU grant 2025 awarded to him by the University of Malta (UM), for collaboration with mathematicians at UG. UM and UG are members of SEA-EU, an alliance of nine coastal universities across Europe (Cádiz, Brest, Kiel, Gdańsk, Split, Malta, Algarve, Naples, NORD). During the visit to UG, the professor was joined by his two doctoral students, Karl Bartolo and Dayle Scicluna, who were each supported by an Erasmus grant. In the photo, Bartolo is seen third from the right, and Scicluna is the first from the left among some of the other seminar attendees. For further details about the project, read the main story.
Sound bites
• Let P be a simple polygon with exactly n corners. Think of an art gallery with straight walls. The Art Gallery Theorem (ALT) states that the smallest number of guards needed to guard the whole interior of P is at most n/3 (n divided by 3). This famous result was proved by Vašek Chvátal in 1975 (A combinatorial theorem in plane geometry, Journal of Combinatorial Theory, Series B 18 (1975), 39-41). Joint research on isolating sets of graphs led Peter Borg (the present author) and Pawaton Kaemawichanurat to the following extension of ALT, relaxing the visibility condition: If at least one of every k consecutive corners of P must be visible to at least one guard, then the number of guards needed is at most n/(k + 2). They proved this result in a paper entitled Extensions of the Art Gallery Theorem and published in the journal Annals of Combinatorics in 2023. The case k = 1 (so n/(k + 2) becomes n/3 as in ALT) is given by ALT in a stronger form; ALT guarantees full visibility (not just visibility of corners). However, note that when k is larger than 1, the bound n/(k + 2) is smaller (and hence better as it means fewer guards are needed) than the ALT bound n/3. Both bounds are best possible, that is, they can be attained.
For more soundbites listen to Radio Mocha every Saturday at 7.30pm on Radju Malta and the following Monday at 9pm on Radju Malta 2
https://www.fb.com/RadioMochaMalta/