Workshop on Applied Mathematics and Graph Theory

6th Macedonian Workshop on Graph Theory and Its Applications (2022)

Ohrid, August 13–17, 2022
Book of Abstracts

Invited Talks

Distances in orientations of graphs

Peter Dankelmann
University of Johannesburg, Johannesburg, South Africa
pdankelmann@uj.ac.za

An orientation of a graph $G$ is a digraph obtained from $G$ by assigning a direction to every edge. The well-known Robbins’ Theorem states that every bridgeless graph has an orientation that is strong, i.e., in which between every two vertices there is a directed path. However, Robbins’ Theorem does not give any information on the possible increase in the distances between vertices.

The oriented diameter of a bridgeless graph $G$ is defined as the minimum diameter among all strong orientations of $G$. The natural question—if a bridgeless graph of small diameter has an orientation of small diameter—was answered affirmatively by Chvátal and Thomassen, but sharp bounds on the oriented diameter in terms of the graph’s diameter are known only for diameter 2 or 3.

In this talk, we survey known results on the relationship between oriented diameter and other graph parameters, and present new findings.

On the ratio of domination and independent domination in regular graphs

Martin Knor
Slovak University of Technology in Bratislava, Slovakia
knor@math.sk
(Joint work with Riste Škrekovski and Aleksandra Tepeh)

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex of $G$ is in $S$ or adjacent to a vertex in $S$. If, in addition, $S$ is independent, then it is an independent dominating set.

Let:

  • $\gamma(G)$ = domination number (minimum size of a dominating set),
  • $i(G)$ = independent domination number (minimum size of an independent dominating set).

We prove that for all integers $k \geq 3$, if $G$ is a connected $k$-regular graph, then

$$ \frac{i(G)}{\gamma(G)} \leq \frac{k}{2}, $$

with equality if and only if $G = K_{k,k}$.

This result was previously known only for $k \leq 6$.

Supported by Slovak grants APVV-17-0428, APVV-19-0308, VEGA 1/0206/20, VEGA 1/0567/22, and Slovenian ARRS programs P1-0383, J1-1692, J1-8130.

Constructing mutually orthogonal symmetric hamiltonian double latin squares from Mullin–Nemeth starters in finite fields

Justin Z. Schroeder
Gostivar, North Macedonia
jzschroeder@gmail.com

Double Latin squares—a natural extension of Latin squares—were introduced in 2003 by Hilton et al. Of particular interest are mutually orthogonal symmetric Hamiltonian double Latin squares of order $2n$, abbreviated MOSHLS($2n$), because they cannot be constructed by simply joining Latin squares of order $n$.

A proof was originally provided for the existence of MOSHLS($2n$) for all $n \leq 13$. In this talk, we develop a construction of MOSHLS($2q$) for many prime-power values of $q$ using a special family of strong starters known as Mullin–Nemeth starters.

Connections to:

  • orthogonal Hamilton path decompositions of complete graphs, and
  • orthogonal 1-factorizations of complete bipartite graphs
    are also explored.

Contributed Talks

Fast Triangles Counting in a Graph

Abulfaz Abiyev
Khazar University, Baku, Azerbaijan
vetenbaku@gmail.com

(Abstract not provided in source document. Title retained for completeness.)

Distance based indices on nanotubical graphs

Vesna Andova
Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ., Skopje, North Macedonia
vesna.andova@gmail.com, vesnaa@feit.ukim.edu.mk
(Joint work with Martin Knor and Riste Škrekovski)

Nanotubical graphs are obtained by wrapping a hexagonal grid and possibly closing the tube with caps. We derive asymptotics for several generalizations of the Wiener index.

Define the measure:

$$ I_\lambda(G) = \sum_{u \ne v} f(u,v) \cdot \mathrm{dist}(u,v)^\lambda, $$

where $\lambda \in \mathbb{R}$ and $f(u,v)$ is a nonnegative symmetric function, non-decreasing and depending only on $\deg(u)$ and $\deg(v)$.

We show that the leading term of $I_\lambda(G)$ depends only on:

  • $\lambda$,
  • $f(x,y)$ when $\deg(x) = \deg(y) = 3$,
  • the circumference of the nanotube.

As a consequence, we obtain asymptotics for:

  • generalized Wiener index,
  • Harary index,
  • hyper-Wiener index,
  • additively weighted Harary index,
  • generalized degree distance,
  • modified degree distance index.

Community analysis in Slovenian labour network 2010–2020

Viktor Andonovikj
Jožef Stefan Institute, Ljubljana, Slovenia
andonovic.viksa@gmail.com
(Joint work with Pavle Boskoski, Bojan Evkoski, Tjaša Redek, and Biljana Mileva Boshkoska)

We apply community detection and influence analysis to the Slovenian labour market network from 2010 to 2020 to identify occupation groups and key influential roles.

This is the first work to successfully apply these methods to the Slovenian labour network. The results support employment services in identifying job opportunities and highlight how existing administrative data can be leveraged to improve employment outcomes.

Optimal selection of parameters for production of Multiwall Carbon Nanotubes (MWCNTs) by electrolysis in molten salts using machine learning

Beti Andonovic
Faculty of Technology and Metallurgy, Ss Cyril and Methodius Univ., Skopje, North Macedonia
beti@tmf.ukim.edu.mk
(Joint work with Viktor Andonovikj, Mimoza Kovaci Azemi, and Aleksandar T. Dimitrov)

We design a new electrochemical method for producing MWCNTs via electrolysis in molten salts under stationary and non-stationary current regimes. The process is simple, ecological, economical, and allows precise control of:

  • applied voltage,
  • current density,
  • temperature.

Using explainable tree-based machine learning models, we infer the relationship between experimental parameters and MWCNT quality (labeled by domain experts). This enables high-yield, low-cost production—up to 10× cheaper than commercial alternatives.

On the Nullity of Altans and Iterated Altans

Nino Bašić
University of Primorska (FAMNIT & IAM), Koper, Slovenia; Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
nino.basic@famnit.upr.si
(Joint work with Patrick W. Fowler)

Altanisation constructs generalized coronenes by attaching a perimeter cycle of length $2|H|$ to a parent graph $G$ via an attachment set $H \subseteq V(G)$.

We prove sharp bounds on nullity (dimension of kernel of adjacency matrix):

  • For any $G$ and $H$, $\eta(\text{altan}(G,H)) \leq \eta(G) + 2$.
  • The case $\eta(\text{altan}) = \eta(G) + 2$ occurs first for a benzenoid with just 5 hexagons.
  • We exhibit an infinite family of convex benzenoids with $D_{3h}$ symmetry where nullity increases from 2 to 3 under altanisation.

References:
[1] N. Bašić, P. W. Fowler, On the nullity of altans and iterated altans, MATCH Commun. Math. Comput. Chem. 88 (2022) 705–745.
[2] N. Bašić, P. W. Fowler, A curious family of convex benzenoids and their altans, Discrete Math. Lett. 9 (2022) 111–117.

Omega Invariant and Some Open Problems in Graph Theory

Ismail Naci Cangul
Bursa Uludağ University, Türkiye
cangul@uludag.edu.tr

The Omega invariant is a graph parameter closely related to the Euler characteristic and cyclomatic number. It has been applied to:

  • degree sequence realizability,
  • topological indices,
  • counting algorithms.

In this talk, we summarize recent results and address open problems concerning the realizability of degree sequences using the Omega invariant.

Mathematical analysis in characterization of carbon nanotubes (CNTs) produced by electrolysis in molten salts

Aleksandar T. Dimitrov
Faculty of Technology and Metallurgy, Ss Cyril and Methodius Univ., Skopje, North Macedonia
aco@tmf.ukim.edu.mk
(Joint work with Viktor Andonovikj, Beti Andonovic, and Mimoza Kovaci Azemi)

We perform full molecular characterization of experimentally produced multi-wall carbon nanotubes (MWCNTs). Each CNT is represented mathematically via its hexagonal lattice structure.

Key structural parameters determined:

  • innermost and outermost diameters,
  • chiral indices $(m,n)$,
  • number of walls,
  • unit cell parameters.

Using Raman spectroscopy and Python-based assignment algorithms, we accurately determine chirality, enabling computation of distance-based topological indices from graph representations of nanotube walls.

Glimpse of Translation–Modulation Invariant Banach Spaces of generalized functions

Pavel Dimovski
Faculty of Technology and Metallurgy, Ss Cyril and Methodius Univ., Skopje, North Macedonia
dimovski.pavel@gmail.com

We introduce a new class of translation–modulation invariant Banach spaces of ultradistributions. These spaces:

  • are stable under Fourier transform and tensor products,
  • carry a natural Banach convolution module structure over a Beurling algebra,
  • admit a Banach multiplication module structure over a Wiener–Beurling algebra.

As a classical application, we investigate the wave front set with respect to these spaces.

Coverability of graphs by two parity regular subgraphs

Mirko Petruševski
Faculty of Mechanical Engineering, Ss Cyril and Methodius Univ., Skopje, North Macedonia
mirko.petrushevski@gmail.com
(Joint work with Riste Škrekovski)

A graph is parity regular if all vertex degrees have the same parity (all even or all odd).

This talk addresses:

  • when a graph can be covered or decomposed into two parity regular subgraphs,
  • complexity aspects (e.g., NP-hardness),
  • sufficient conditions for such coverings.

Linear Algorithm For Travelling Salesman Problem Based On Iterative Extension Of The Path With A Single Point At Each Step

Sijche Pechkova
Faculty of Technology and Metallurgy, Ss Cyril and Methodius Univ., Skopje, North Macedonia
sijche@gmail.com
(Joint work with Mile Jovanov and Aleksandar Pechkov)

We present a heuristic algorithm for the Travelling Salesman Problem (TSP) that iteratively extends a path by adding one point at a time. While not optimal, it provides good-quality solutions in low computational time, making it suitable for large instances where even $O(n^2)$ algorithms are too slow.

Tested on standard datasets, the results are close to optimal and useful when resources or time are limited.

Locally irregular edge colorings and the bow-tie graph

Jelena Sedlar
University of Split, Faculty of Civil Engineering and Architecture, Croatia
jsedlar@gradst.hr

A graph is locally irregular if every pair of adjacent vertices has distinct degrees. A locally irregular edge coloring is an edge coloring where each color class induces a locally irregular subgraph.

The Local Irregularity Conjecture claims that every colorable graph admits such a coloring with at most three colors.

We examine the conjecture on unicyclic graphs and cacti, where the bow-tie graph (two triangles sharing a vertex) plays a critical role.

The Odd Coloring

Riste Škrekovski
Faculty of Information Studies, Novo mesto & University of Ljubljana, Slovenia
skrekovski@gmail.com
(Joint work with Mirko Petruševski and Yair Caro)

A proper vertex coloring $\phi$ of a graph $G$ is odd if for every non-isolated vertex $x \in V(G)$, there exists a color $c$ such that

$$ |\phi^{-1}(c) \cap N(x)| \text{ is odd}. $$

The odd chromatic number, denoted $\chi_o(G)$, is the minimum number of colors in any odd coloring of $G$.

We discuss:

  • basic properties,
  • upper bounds,
  • characterizations,
  • connections to proper conflict-free coloring,
  • open problems.

Publisher: Macedonian Society of Graph Theorists
Editor: Vesna Andova
Scientific Committee: Riste Škrekovski, Vesna Andova, Mirko Petruševski
Local Organizing Committee: Vesna Andova, Mirko Petruševski, Riste Škrekovski, Pavel Dimovski, Bojan Prangoski
Technical Support: Vesna Andova, Mirko Petruševski
Sponsors: Faculty of Electrical Engineering and Information Technologies & Ss. Cyril and Methodius University, Skopje