Workshop on Applied Mathematics and Graph Theory

7th Macedonian Workshop on Graph Theory and Its Applications (2023)

Ohrid, August 12–17, 2023
Book of Abstracts

Invited Talks

Optimizing carbon nanotubes and graphene production: unraveling the optimal parameters through machine learning

Beti Andonovik
Faculty of Technology and Metallurgy, Ss Cyril and Methodius Univ., Skopje, North Macedonia
beti@tmf.ukim.edu.mk

We present the design and development of new technologies for producing carbon nanotubes (CNTs) and graphene by electrolysis in molten salts. The aim is to achieve non-expensive, high-quality materials, making them economically viable for various applications.

  • For MWCNTs, we investigate both non-stationary and stationary current regimes.
  • For graphene, we consider constant/reversing cell voltage and constant/reversing overpotential methods.

The electrolysis process offers ecological and economical advantages with precise control over:

  • applied voltage,
  • current density,
  • temperature,
  • electrolyte type,
  • graphite material.

To determine the relationship between these parameters and material quality, we employ explainable tree-based Machine Learning (ML) models, trained using labeled data from domain experts. The extracted rules guide optimal production, resulting in high-yield materials that are up to ten times more cost-effective than existing technologies.

The Borel–Ritt problem in ultraholomorphic classes

Andreas Debrouwere
Department of Mathematics and Data Science, Vrije Universiteit Brussel, Brussels, Belgium
andreas.debrouwere@vub.be

A classical result of E. Borel (1895) states that every formal power series is the Taylor series at 0 of some smooth function on $\mathbb{R}$.

In 1916, Ritt generalized this: every formal power series is the asymptotic expansion at 0 of some holomorphic function on a sector $S \subset \mathbb{C}$. This is the Borel–Ritt theorem.

Ultraholomorphic classes are spaces of holomorphic functions on sectors whose derivatives satisfy bounds governed by a weight sequence.

Problem: Find analogues of the Borel–Ritt theorem in ultraholomorphic classes.

This talk surveys known results and open questions related to this problem.

Quasi-analytic representation theory of $(\mathbb{R}^d,+)$ over quasi-complete locally convex spaces

Bojan Prangoski
Faculty of Mechanical Engineering, Ss. Cyril and Methodius Univ., Skopje, Macedonia
bprangoski@yahoo.com

Let $(\pi, E)$ be a representation of a Lie group $G$ on a locally convex space $E$. It induces an action of the algebra $\mathcal{D}(G)$ via

$$ \Pi(f)e = \int_G f(g)\pi(g)e\,dg. $$

For $G = (\mathbb{R},+)$, Dixmier–Malliavin showed that the space of smooth vectors satisfies a weak factorization property. Recent work extended this to analytic vectors.

In this talk, we generalize further:

  1. Allow $E$ to be a quasi-complete locally convex space (not just Banach or Fréchet).
  2. Solve the problem in the general quasi-analytic setting, using ultradifferentiable vectors of Beurling and Roumieu type.

We identify the appropriate convolution algebra and prove a factorization property without “span”.

(Joint work with Andreas Debrouwere and Jasson Vindas.)

Normal 5-edge-colorings and some superpositioned snarks

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

An edge $e$ in a proper edge-coloring of a cubic graph $G$ is normal if the number of distinct colors on the four edges adjacent to $e$ is 2 or 4.

A normal edge-coloring requires every edge to be normal. The Petersen Coloring Conjecture is equivalent to: every bridgeless cubic graph admits a normal 5-edge-coloring.

Since 3-edge-colorable graphs are trivially normal, it suffices to study snarks.

We consider superpositioned snarks: choose a cycle $C$ in a snark $G$, and replace vertices/edges of $C$ with supervertices/superedges derived from another snark $H$.

We provide two sufficient conditions for such superpositions to admit a normal 5-edge-coloring, with applications when $H$ is:

  • a hypohamiltonian snark, or
  • a Flower snark.

These results imply the Berge–Fulkerson Conjecture holds for this class.

Contributed Talks

Splitting subspaces of linear operators over finite fields

Divya Aggarwal
Indraprastha Institute of Information Technology Delhi, India
divyaa@iiitd.ac.in

Let $V$ be an $N$-dimensional vector space over $\mathbb{F}_q$, and $T$ a linear operator on $V$. Given $m \mid N$, an $m$-dimensional subspace $W \subseteq V$ is $T$-splitting if

$$ V = W \oplus TW \oplus \cdots \oplus T^{d-1}W, \quad d = N/m. $$

Let $\sigma(m,d;T)$ denote the number of such subspaces.

  • We prove $\sigma(m,d;T)$ depends only on the similarity class type of $T$.
  • For cyclic nilpotent $T$, we give an explicit formula.
  • For fixed $m,d,\tau$, the function $\sigma_q(m,d;\tau)$ is a polynomial in $q$.

Structured Output Prediction for Time-to-Event Estimation: A Semi-Supervised Approach in Survival Analysis

Viktor Andonovikj
Jožef Stefan Institute, Ljubljana, Slovenia
andonovic.viksa@gmail.com

Standard survival analysis struggles with mixed categorical/continuous data; pure ML methods struggle with censoring.

We propose a semi-supervised structured output prediction framework for time-to-event estimation.

Applied to Public Employment Services data, our method:

  • predicts time-to-employment for jobseekers,
  • outperforms conventional methods in accuracy and scalability,
  • uses SHAP for interpretability,
  • helps prioritize those needing immediate support.

Diameter of nanotori

Vesna Andova
Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ., Skopje, Macedonia
vesna.andova@gmail.com, vesnaa@feit.ukim.edu.mk

A nanotorus $G_{a,b,c}$ is a cubic graph with only hexagonal faces, embeddable on a torus, defined by three parameters $a,b,c$.

We solve an open problem from Alspach’s survey: determine $\mathrm{diam}(G_{a,b,c})$.

Results:

  • If $b \leq a$, then $\mathrm{diam}(G_{a,b,c}) = a$.
  • If $a < b$, we distinguish:
    • $a \leq c < b$,
    • $c < a < b$,
  • and compute the diameter for sufficiently large $b$.

(Joint work with Martin Knor and Riste Škrekovski.)

Abelian and Tauberian results for the fractional Fourier and short time Fourier transforms

Sanja Atanasova
Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ., Skopje, Macedonia
ksanja@feit.ukim.edu.mk

We introduce the fractional short-time Fourier transform in $\mathcal{S}'(\mathbb{R})$ and provide generalized asymptotics for:

  • fractional Fourier transform,
  • short-time Fourier transform.

We establish Abelian and Tauberian-type theorems in this setting.

H-integral and Gaussian integral normal mixed Cayley graphs

Bikash Bhattacharjya
Indian Institute of Technology Guwahati, India
b.bikash@iitg.ac.in

  • A mixed graph is H-integral if all eigenvalues of its Hermitian adjacency matrix are integers.
  • It is Gaussian integral if all eigenvalues of its $(0,1)$-adjacency matrix are Gaussian integers.

We:

  • characterize H-integral normal mixed Cayley graphs over finite groups,
  • prove: a normal mixed Cayley graph is H-integral iff it is Gaussian integral.

Omega Invariant and Combinatorial Properties

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

The Omega invariant is closely related to the Euler characteristic and cyclomatic number.

It has applications in:

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

We summarize recent combinatorial results and resolve open problems on degree sequence realizability.

Uniformly concentrated partitions of unity and its application

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

We define Wiener amalgam spaces of (quasi)analytic ultradistributions where:

  • local components belong to translation–modulation invariant Banach spaces,
  • global components are in weighted $L^p$ or $C_0$.

We provide a discrete characterization via uniformly concentrated partitions of unity and identify strong duals.

(Joint work with Bojan Prangoski.)

On metric dimension of circulant graphs with $t$ consecutive generators

Martin Knor
Slovak University of Technology in Bratislava, Slovakia
knor@math.sk

For a graph $G$, the metric dimension $\dim(G)$ is the size of the smallest set $W \subseteq V(G)$ such that all vertices have distinct distance vectors to $W$.

Consider the circulant graph:

$$ C_n(1,2,\dots,t) = \mathrm{Cay}(\mathbb{Z}_n, \{\pm1, \pm2, \dots, \pm t\}). $$

We prove:

$$ \dim(C_n(1,2,\dots,t)) \geq \left\lceil \frac{2t}{3} \right\rceil + 1, $$

and characterize equality cases. As a corollary, we fully determine $\dim(C_n(1,2,\dots,5))$.

(Joint work with Riste Škrekovski and Tomáš Vetrík.)

TBA

Kiril Lisichkov
Faculty of Technology and Metallurgy, Ss Cyril and Methodius Univ., Skopje, Macedonia
kiril@tmf.ukim.edu.mk

(Abstract not provided.)

TBA

Sijche Pechkova
Faculty of Technology and Metallurgy, Ss Cyril and Methodius Univ., Skopje, Macedonia
sijche@gmail.com

(Abstract not provided.)

Proper edge-colorings with a rich neighbor condition

Mirko Petruševski
Faculty of Mechanical Engineering, Ss. Cyril and Methodius Univ., Skopje, Macedonia
mirko.petrushevski@gmail.com

An edge is rich if no color repeats among its neighboring edges. A strong edge-coloring requires all edges to be rich.

We introduce a weaker notion: a rich-neighbor coloring is a proper edge-coloring where every non-isolated edge has at least one rich neighbor.

Conjecture: Every connected subcubic graph $G \ne K_4$ admits a rich-neighbor 5-coloring.

We prove: every subcubic graph admits a rich-neighbor coloring with at most 7 colors.

We also discuss related notions: normal-neighbor and poor-neighbor colorings.

(Joint work with Riste Škrekovski.)

The Odd Coloring

Riste Škrekovski
Faculty of Information Studies, Novo mesto & University of Ljubljana, Slovenia
skrekovski@gmail.com

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

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

The odd chromatic number $\chi_o(G)$ is the minimum number of colors in such a coloring.

We discuss:

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

(Joint work with Mirko Petruševski and Yair Caro.)

The Indian Charter on Planet Earth, the European Decentralization Activities, and a Walk-Through the Next Generation Internet Agenda

Vlado Stankovski
University of Ljubljana, Slovenia
Vlado.Stankovski@fri.uni-lj.si

Humanity’s deep cultural knowledge is being lost in the digital age. Emerging technologies—IoT, AI, Blockchain, Digital Twins—can embed ethical and sustainability principles into the core of the Internet.

Projects like DE-CENTER, ONTOCHAIN, TRUSTCHAIN, and EBSI-VECTOR aim to build a Next Generation Internet that is:

  • trustworthy,
  • human-rights compliant,
  • sustainable.

This talk explores how such infrastructures can serve humanity’s long-term needs.

Shedding Vertices and Their Recognition

David Tankus
Sami Shamoon College of Engineering, Ashdod, Israel
davidt@sce.ac.il

  • An independent set is maximal if not contained in a larger one; maximum if of largest possible size ($\alpha(G)$).
  • A graph is well-covered if all maximal independent sets are maximum.

A vertex $v$ is shedding if for every independent set $S \subseteq V \setminus N[v]$, there exists $u \in N(v)$ such that $S \cup \{u\}$ is independent.

Theorem: For a well-covered graph $G$ with no isolated vertices, the following are equivalent:

  1. $G \in \mathcal{W}_2$,
  2. $G \setminus N[v] \in \mathcal{W}_2$ for all $v$,
  3. All vertices are shedding.

We prove:

Recognizing shedding vertices in triangle-free graphs is co-NP-complete.

We also relate shedding vertices to relating edges (edges $xy$ where both $S \cup \{x\}$ and $S \cup \{y\}$ can be maximal).

(Joint work with Vadim E. Levit.)

Decomposition of complete graph into trees and cycles

Murugan Varadhan
Vellore Institute of Technology, India
murugan.v@vit.ac.in

(Abstract not provided.)

Almost Periodicity in Abstract Impulsive Volterra Integro-Differential Inclusions

Daniel Velinov
Faculty of Civil Engineering, Ss. Cyril and Methodius University, Skopje
velinov.daniel@gmail.com

We study abstract impulsive Volterra integro-differential inclusions using $(a,k)$-regularized $C$-resolvent families.

We introduce new classes of piecewise continuous almost periodic functions with values in complex Banach spaces.

We prove existence and uniqueness of almost periodic solutions and demonstrate applications to concrete systems.

Publisher: Macedonian Society of Graph Theorists
Editor: Vesna Andova
Scientific Committee: Riste Škrekovski, Pavel Dimovski, Martin Knor, Snježana Majstorović, Vesna Andova, Mirko Petruševski
Local Organizing Committee: Vesna Andova, Mirko Petruševski, Riste Škrekovski, Pavel Dimovski
Technical Support: Vesna Andova, Mirko Petruševski
Sponsors: Ss. Cyril and Methodius University (FEIT, FTM), Faculty of Information Sciences (Novo mesto)