8th Macedonian Workshop on Graph Theory and Applied Mathematics (2024)

Ohrid, August 9–13, 2024
Book of Abstracts

Invited Talks

Symmetry Properties of Nut Graphs

Nino Bašić
University of Primorska, Koper, Slovenia
nino.basic@famnit.upr.si
(Joint work with Patrick W. Fowler and Tomaž Pisanski)

A nut graph is a simple graph whose adjacency matrix has a single zero eigenvalue, and all entries of any corresponding eigenvector are nonzero. Nut graphs have at least seven vertices; they are connected, non-bipartite, and leafless.

In this talk, we present symmetry properties of nut graphs:

Every nut graph $G$ has at least one more edge orbit than vertex orbit.
Consequently, edge-transitive nut graphs do not exist.
We construct infinite families of vertex-transitive nut graphs with:
- two edge orbits, or
- two vertex orbits and three edge orbits.
Moreover, every finite group is realizable as the automorphism group of infinitely many nut graphs.
These constructions can be made regular, with explicit examples for degrees 8, 12, 16, 20, and 24.

Symmetry Equiincidence of Natural Orbitals

Jerzy Cioslowski
Institute of Physics, University of Szczecin, Poland
jerzy.cioslowski@usz.edu.pl

The symmetry equiincidence principle quantifies how natural orbitals (NOs)—ordered by nonincreasing occupation numbers—are distributed among irreducible representations (irreps) of the point group of the underlying on-top two-electron density.

For resolvable point groups (e.g., $C_{2v}, D_{3h}, O_h$), the symmetry incidences (asymptotic probabilities of NOs belonging to a given irrep) are proportional to the squares of the irrep dimensions.

This result relies on sufficient symmetry planes. It yields only linear combinations of incidences for quasiresolvable groups and fails for unresolvable groups like $C_1$, $C_n$, $D_n$, $T$, $O$, and $I$.

Characterization of Polymer Matrix Composites Reinforced with Carbon Nanostructures

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

We synthesize multi-walled carbon nanotubes (MWCNTs) and graphene via electrolysis in molten salt under potentiostatic conditions using nonstationary current regimes.

We then fabricate conductive nanocomposites using:

PMMA (poly(methyl methacrylate)) or
PVDF (poly(vinylidene fluoride))

matrices reinforced with:

graphene,
MWCNTs, or
a hybrid mix including fullerenes.

Nanocomposites are prepared as thin films via solvent casting:

PMMA dissolved in chloroform,
PVDF in N-dimethylacetamide,
with 72-hour solvent evaporation.

Reinforcements are used functionalized (via HNO₃ + X-ray irradiation) or non-functionalized.

Characterization techniques:

Raman spectroscopy,
TEM/SEM,
TGA,
ICP-OES (chemical analysis),
Four-point probe (conductivity).

Keywords: nanocomposites, PMMA, PVDF, graphene, MWCNTs.

Strong Edge-Coloring of Graphs

Roman Soták
Pavol Jozef Šafárik University in Košice, Slovakia
roman.sotak@upjs.sk

A strong edge-coloring is an edge-coloring where each color class is an induced matching.

For a $k$-regular graph, at least $2k - 1$ colors are needed. We characterize all $k$-regular graphs admitting a strong edge-coloring with exactly $2k - 1$ colors.

In particular, a cubic graph is strongly 5-edge-colorable if it covers the Petersen graph.

We also study the list version:

Dai et al. (2018): subcubic graphs have strong list-chromatic index ≤ 11.
We improve this and give a tight upper bound.
Proof uses Combinatorial Nullstellensatz on the shortest cycle with pendant edges.

Finally, we present an infinite class of cubic graphs where the strong chromatic index ≠ strong list-chromatic index.

Some Developments on the Wiener–Ikehara Theorem

Jasson Vindas
Ghent University, Belgium
jasson.vindas@ugent.be

The Wiener–Ikehara theorem is a cornerstone of complex Tauberian theory for Laplace transforms, with applications in number theory and spectral theory.

Recent developments include:

Minimal assumptions on boundary behavior of Laplace transforms,
Exact forms without remainder terms,
Quantified versions with error estimates.

This talk surveys advances from the last decade.

Variety of Mutual-Visibility Problems in Graph Theory

Ismael G. Yero
University of Cádiz, Spain
ismael.gonzalez@uca.es

Let $G$ be a connected simple graph. Two vertices $x, y \in V(G)$ are $S$-visible (for $S \subseteq V(G)$) if there exists a shortest $x$–$y$ path $P$ such that $P \cap S \subseteq \{x, y\}$.

$S$ is a mutual-visibility set if every pair in $S$ is $S$-visible.
The mutual-visibility number $\mu(G)$ is the size of the largest such $S$.

Variants include:

Total mutual-visibility: every pair in $V(G)$ is $S$-visible.
Outer mutual-visibility: pairs within $S$ and between $S$ and $V \setminus S$ are $S$-visible.
Dual mutual-visibility: both $S$ and $V \setminus S$ are mutual-visibility sets.

We present results from [1,2], including characterizations for diameter-2 graphs.

References
[1] S. Cicerone et al., Mutual-visibility problems on graphs of diameter two, arXiv:2401.02373
[2] S. Cicerone et al., Variety of mutual-visibility problems in graphs, Theor. Comput. Sci. 974 (2023) 114096

Contributed Talks

Diameter of Nanotori

Vesna Andova
Faculty of Electrical Engineering and Information Technologies, UKIM, Skopje
vesna.andova@gmail.com
(Joint work with Pavel Dimovski, Martin Knor, and Riste Škrekovski)

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

We solve an open problem from Alspach’s survey:

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$.

Detecting Communities Under Constraints in Directed Acyclic Networks

Suzana Antunović
University of Split, Croatia
suzana.antunovic264@gmail.com

We propose an algorithm for community detection in DAGs that respects a given topological ordering.

The method:

Recursively assigns vertices to communities,
Respects vertex order,
Maximizes modularity,
Induces an ordering on communities.

This enables analysis of inter-community dynamics in hierarchical networks.

Asymptotic Analysis of Some Fractional Transforms on Distribution Spaces

Sanja Atanasova
FEIT, UKIM, Skopje
ksanja@feit.ukim.edu.mk

We present Abelian and Tauberian-type results linking the quasi-asymptotic behavior of distributions to asymptotics of:

fractional Fourier transform,
short-time Fourier transform.

Scaling properties are quantified using Karamata regularly varying functions.

Wave Front Sets with Respect to Banach Spaces of Ultradistributions

Pavel Dimovski
Faculty of Technology and Metallurgy, UKIM, Skopje
dimovski.pavel@gmail.com

We define ultradistributional wave front sets relative to translation–modulation invariant Banach spaces with solid Fourier images.

Main result: characterization via the short-time Fourier transform.

Some Spectral Characterizations of Graphs with Self-loops

Irena Jovanović
Union University, Belgrade, Serbia
irenaire@gmail.com
(Joint work with Saieed Akbari and Johnny Lim)

For a graph $G$ and $S \subseteq V(G)$, let $G_S$ be obtained by adding a self-loop at each vertex in $S$. Its adjacency matrix is:

$$ A(G_S) = A(G) + I_S, $$

where $I_S$ has 1s on diagonal entries for $S$.

The energy of $G_S$ is defined as:

$$ E(G_S) = \sum_{i=1}^n \left| \lambda_i(G_S) - \frac{|S|}{n} \right|. $$

We:

Disprove a conjecture that $E(G_S) > E(G)$ for all nontrivial $S$,
Study line graphs $L(G_S)$: eigenvalues ≥ −2,
Show $E(L(G)) < E(L(G_S))$ when $S \ne \emptyset$,
Compute characteristic polynomials for subdivision graphs with loops,
Provide bounds on energy based on eigenvalue inequalities.

On Šoltés Vertices in Regular Graphs

Martin Knor
Slovak University of Technology, Bratislava
knor@math.sk
(Joint work with Nino Bašić and Riste Škrekovski)

The Wiener index $W(G)$ is the sum of all pairwise distances.

A vertex $v$ is a Šoltés vertex if $W(G - v) = W(G)$.

Only one graph is known where all vertices are Šoltés vertices: $C_{11}$.

We present a construction showing that the number of Šoltés vertices is unbounded in cubic graphs.

Supported by APVV-19-0308, APVV-22-0005, VEGA 1/0567/22, VEGA 1/0069/23.

Complexity of Graph Algebraic Expressions: Recent Findings

Mark Korenblit
Holon Institute of Technology, Israel
korenblit@hit.ac.il
(Joint work with Vadim E. Levit)

For an st-dag (two-terminal directed acyclic graph), the canonical expression is the sum of products of edge labels over all spanning paths.

The complexity is the total number of label occurrences.

Series–parallel graphs admit optimal expressions (each label once).
For general graphs, optimal representation is NP-complete.

The $k$-Multiset Antidimension of Graphs with Applications into Privacy in Networks

Dorota Kuziak
University of Cádiz, Spain
dorota.kuziak@uca.es

In standard metric representation, vertex $x$ w.r.t. $S = \{v_1,\dots,v_r\}$ is the vector:

$$ r(x|S) = (d(x,v_1), \dots, d(x,v_r)). $$

In the multiset version, we use:

$$ m(x|S) = \{\!\{ d(x,v_1), \dots, d(x,v_r) \}\!\}. $$

A set $S$ is a $k$-multiset antiresolving set if for every $u \notin S$, there are at least $k-1$ other vertices $v$ with $m(u|S) = m(v|S)$.

The $k$-multiset antidimension is the minimum size of such $S$.

This models $(k,\ell)$-anonymity in social networks against active attacks.

Combining Proper and Square Colorings

Borut Lužar
Faculty of Information Sciences, Novo mesto, Slovenia
borut.luzar@gmail.com

We consider colorings with two types of colors:

Proper colors: may repeat on non-adjacent vertices,
Strong colors: must appear only on objects at distance ≥ 3.

This interpolates between proper coloring and square coloring (coloring $G^2$).

Motivated by $S$-packing colorings, this framework reveals new structural properties and computational challenges.

Reich-type Contractive Mapping into a Complete Metric Space

Samoil Malcheski
International Slavic University, Sveti Nikole, Macedonia
samoil.malcheski@msu.edu.mk

We generalize the Reich fixed-point theorem on a complete metric space $(X,d)$.

Using a continuous, injective, subsequentially convergent mapping $T$, and a function $f \in \Theta$ (monotone, $f^{-1}(0) = \{0\}$, subadditive), we establish existence and uniqueness of fixed points.

Objective Determination of the Type of Trend Function in Economic Processes

Risto Malcheski
risto.malceski@gmail.com

We propose a method to objectively determine the functional form of a trend in economic time series without a priori assumptions.

The approach uses:

Linear algebra,
Difference equations,
Differential equations,

to infer trend type directly from data.

Generalisations of Connectedness and Separatedness by Using the Notion of Chain

Zoran Misajleski
Faculty of Civil Engineering, UKIM, Skopje
zokimisajleski@gmail.com

We generalize connectedness and separatedness using the concept of chains.

Several topological-like properties are established in this discrete setting.

Hermite Expansions for Spaces of Functions with Nearly Optimal Time-Frequency Decay

Lenny Neyt
Ghent University, Belgium
Lenny.Neyt@UGent.be
(Joint work with Joachim Toft and Jasson Vindas)

The Hardy uncertainty principle states: if

$$ |f(t)| \lesssim e^{-\eta t^2}, \quad |\hat{f}(\xi)| \lesssim e^{-\eta \xi^2}, $$

then $\eta \leq 1/2$, with equality only for Gaussians.

We study functions satisfying this for all $\eta < 1/2$.

Such $f$ satisfy:

$$ |H(f,n)| \lesssim e^{-r n} \quad \forall r > 0, $$

where $H(f,n)$ is the $n$-th Hermite coefficient.

Refined bounds correspond to sharper time-frequency decay.

Tools: Bargmann transform, Phragmén–Lindelöf principle.

Topological Data Analysis and Decision Trees for Breast Cancer Detection using Thermal Images

Sijche Pechkova
Faculty of Technology and Metallurgy, UKIM, Skopje
sijche@gmail.com
(Joint work with Lydmila Wenger)

We propose a breast cancer detection method using:

Thermal images,
Topological Data Analysis (TDA) features (persistent homology),
Decision tree classifier.

Achieves 92% classification accuracy.

TDA captures geometric structure; combined with ML, it enhances diagnostic reliability.

A Comprehensive Study on Air Pollution Prediction in North Macedonia: Insights from LASSO Modeling

Aleksandar Pechkov
apechkov@gmail.com
(Joint work with Mare Srbinovska, Sijche Pechkova, et al.)

We apply LASSO regression to predict air pollution in North Macedonia using:

Meteorological data,
Pollutant concentrations,
Temporal factors.

We:

Identify key predictors,
Assess model robustness,
Investigate the impact of the COVID-19 pandemic on pollution levels.

Results support proactive environmental policy.

The Odd Coloring and its Variations

Mirko Petruševski
Faculty of Mechanical Engineering, UKIM, Skopje
mirko.petrushevski@gmail.com
(Joint work with Riste Škrekovski and Yair Caro)

A proper vertex coloring $\phi$ 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.

We discuss:

Basic properties,
Upper bounds,
Characterizations,
Relation to proper conflict-free coloring,
Introduction of strong odd colorings.

Core Potentials: a Hypercube Perspective

Guillaume Scholz
Leipzig University, Germany
gllm.scholz@gmail.com
(Joint work with Anahy Santiago Arguello and Peter Stadler)

Segmentations partition an ordered set into intervals. The Consensus Segmentation problem seeks a median segmentation.

Many dissimilarity measures derive from potentials (set functions).

We link this to finding the median in an edge-weighted hypercube, revealing structural insights and enabling new solution strategies.

Graph B

Riste Škrekovski
Faculty of Information Studies, Novo mesto & University of Ljubljana
skrekovski@gmail.com
(Joint work with Jelena Sedlar and Borut Lužar)

In this talk, the focus will be on Graph B, which is named after Borut.

(Note: Abstract is intentionally minimal in source document.)

On Normal and List Normal Edge-Coloring of Cubic Graphs

Diana Švecová
Pavol Jozef Šafárik University in Košice, Slovakia
diana.svecova@student.upjs.sk

A normal edge-coloring of a cubic graph is a proper edge-coloring where every edge is adjacent to either 2 or 4 distinct colors.

The Petersen Coloring Conjecture ⇔ every bridgeless cubic graph has a normal 5-edge-coloring.

Known: all cubic graphs admit normal coloring with ≤ 7 colors.

We present results for special graph classes.

We also introduce the list version:

Some cubic graphs require ≥ 9 colors,
Some bridgeless cubic graphs require ≥ 8 colors.

Geometric Description and Structure of the Photon and Electron

Kostadin Trenchevski
Faculty of Natural Sciences and Mathematics, UKIM, Skopje
kostadin.trenchevskil@gmail.com

(Abstract not provided in source document.)

Almost Periodic Functions in the Framework of Measure Theory

Daniel Velinov
Faculty of Civil Engineering, UKIM, Skopje
velinov.daniel@gmail.com

We introduce new classes of multi-dimensional almost periodic functions in the context of general measure theory.

Applications include:

Abstract Volterra integro-differential inclusions,
Semilinear systems in Banach spaces.

We emphasize structural properties and practical relevance.

Derivatives of Multivariate Real Functions Without Limits

Aneta Velkoska
UIST “St. Paul the Apostle”, Ohrid, Macedonia
aneta.velkoska@uist.edu.mk

Standard differentiability requires open domains. We adopt an algebraic approach to define derivatives without limits.

We extend differentiability to tangentially locally linearly independent (TLLI) sets—a broad class beyond open sets.

Based on ideas from Grauert–Lieb–Fischer.

On the Iterates of the Laguerre Operator

Dorde Vučković
Technical Faculty “Mihajlo Pupin”, Zrenjanin, Serbia
djordjeplusja@gmail.com
(Joint work with Stevan Pilipović, Nenad Teofanov, Smiljana Jakšić)

We define test function spaces on $\mathbb{R}^d_+$ using iterates of the Laguerre operator.

These spaces are natural counterparts of global Pilipović spaces on $\mathbb{R}^d$.

We show they coincide with nontrivial $G$-type spaces, and construct associated ultradistribution spaces.

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