Workshop on Applied Mathematics and Graph Theory

4th Macedonian Workshop on Graph Theory and Its Applications (2019)

Ohrid, August 26–30, 2019
Book of Abstracts

Invited Talk

Homomorphisms of signed graphs

Reza Naserasr
IRIF (Institut de Recherche en Informatique Fondamentale), University of Paris-Diderot, Paris, France
reza@irif.fr

A signed graph is a graph together with an assignment of signs ($+$ or $-$) to each of its edges.

In this talk I introduce a natural extension of the notion of homomorphisms of graphs to signed graphs. A few reformulations of the question and connections with homomorphisms of 2-edge-colored graphs will be presented first.

Then, after presenting a basic no-homomorphism lemma, we will try to find graph classes under which the necessary conditions of the no-homomorphism lemma become also sufficient. Two examples of such results to be discussed are as follows:

Theorem 1. If the maximum average degree of a simple graph $G$ is less than $\frac{8}{3}$, then for any signature $\sigma$, the signed graph $(G,\sigma)$ maps to the signed graph on $K_4$ with exactly one negative edge, provided $(G,\sigma)$ has no loop and no digon.

Theorem 2. Any planar signed graph with no odd-cycle and no digon maps to the signed graph on $K_{4,4}$ where a perfect matching is a set of negative edges.

The second theorem is stronger than the Four Color Theorem, and its proof uses the Four Color Theorem.

Contributed Talks

Distance based indices in nanotubical graphs

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

Nanotubical graphs are obtained by wrapping a hexagonal grid, and then possibly closing the tube with caps. In this paper we derive asymptotics for several generalizations of the Wiener index for nanotubical graphs.

We introduce the measure

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

where $\lambda \in \mathbb{R}$ and $f(u,v)$ is a nonnegative symmetric function which is non-decreasing and depends 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$, and
  • the circumference of the nanotube.

As a consequence, we obtain the asymptotics for:

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

Mathematical Approach to Strokes as an Attractor Within Communication Dynamical System

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

Transactional Analysis as a personality theory has offered powerful concepts to explain and improve communication between individuals. However, positive productive communication among large groups—as a compound set of transactions—has not been well explained.

Like weather and other chaotic processes, group behavior is not easily understood or predicted. It has long been suspected that in large groups (organizations, communities, societies), positive communication plays a leading role in maintaining the duration and quality of interaction.

This paper relates the mathematical notion of dynamical systems to the compound system of communication. The postulate is that strokes—a concept introduced by E. Berne as a way people recognize each other, and elaborated by Steiner as a mechanism of exchanging information—introduce stability into the functioning of large groups.

Odd edge-colorability of subcubic graphs

Risto Atanasov
Western Carolina University, Cullowhee, North Carolina, USA
ratanasov@email.wcu.edu
(Joint work with Mirko Petruševski and Riste Škrekovski)

An edge-coloring of a graph $G$ is said to be odd if for each vertex $v$ of $G$ and each color $c$, the vertex $v$ either uses the color $c$ an odd number of times or does not use it at all.

The minimum number of colors needed for an odd edge-coloring of $G$ is the odd chromatic index, denoted $\chi'_o(G)$.

In this presentation, we consider loopless subcubic graphs, and give a complete characterization in terms of the value of their odd chromatic index.

Production and Characterization of MWCNT’s by Electrolysis in Molten Salt

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

Carbon nanotubes (CNTs) have become a major research focus due to their remarkable structure and unusual properties. This study presents a new electrochemical method for producing multi-walled carbon nanotubes (MWCNTs) via electrolysis in molten salt using non-stationary current regimes.

The process relies on ion intercalation: cations reduce at the cathode, intercalate into the electrode surface, and generate high mechanical stress that causes exfoliation—enabling electrochemical synthesis of MWCNTs.

Key advantages include precise control over:

  • applied voltage,
  • current density,
  • temperature, and
  • morphology of starting material.

Characterization techniques used:

  • SEM and TEM: show curved nanotubes, length $1\text{–}20~\mu\text{m}$, diameter $10\text{–}40~\text{nm}$,
  • Raman spectroscopy: indicates low crystallinity,
  • TGA/DTA: combustion occurs in two stages—at $450^\circ\text{C}$ (MWCNTs) and $720^\circ\text{C}$ (fullerenes/graphite).

The product contains up to 90% MWCNTs, and the method is significantly cheaper than commercial alternatives.

Vertex geometry on nanotubes and nanotori

Pavel Dimovski
Faculty of Technology and Metallurgy, Ss Cyril and Methodius Univ., Skopje, Macedonia
dimovski.pavel@gmail.com
(Joint work with Vesna Andova and Riste Škrekovski)

Nanotubes are graphs obtained by wrapping a hexagonal grid into a cylinder; nanotori result from wrapping in two directions.

Here, we assign coordinates to each vertex on the hexagonal grid, and extend this to tubes and tori. This coordinate system is highly useful for:

  • computing distances,
  • analyzing benzenoid systems,
  • studying structural properties of nanotubes and nanotori.

Decompositions and coverings of graphs by parity regular subgraphs

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

Only two types of finite graphs are parity regular (all vertex degrees share the same parity):

  • Even graphs: all degrees even,
  • Odd graphs: all degrees odd.

An old result by Matthews (1978) links nowhere-zero flows to edge coverings by even subgraphs.

This talk presents recent advances on decomposing and covering graphs using the fewest possible odd subgraphs. We also discuss mixed decompositions involving both even and odd subgraphs, and pose open structural and algorithmic questions.

Key references:

  • Pyber (1991): every graph is coverable by 3 odd subgraphs.
  • Matrai (2006): confirmed the bound is sharp.
  • Kano et al. (2018): decomposition into two odd subgraphs is polynomial-time decidable.

On the largest interval in the image of Wiener index

Jelena Sedlar
University of Split, Croatia
jsedlar@gradst.hr

The Wiener index $W(G)$ of a graph $G$ is the sum of distances over all unordered pairs of vertices.

Let $\mathcal{T}_n$ be the class of trees on $n$ vertices, and $W[\mathcal{T}_n]$ the set of all Wiener index values attained by such trees.

It is known that:

  • $|W[\mathcal{T}_n]| \leq \frac{n^3}{15} + O(n^2)$ for even $n$,
  • $|W[\mathcal{T}_n]| \leq \frac{n^3}{15} + O(n)$ for odd $n$.

We study the largest interval contained in $W[\mathcal{T}_n]$, and prove its size is:

  • $\frac{n^3}{15} + O(n^{5/2})$ for even $n$,
  • $\frac{n^3}{15} + O(n^{5/2})$ for odd $n$.

Since this interval is slightly smaller than the full image, we deduce the exact asymptotic size of $W[\mathcal{T}_n]$, thereby resolving two conjectures from the literature.

Implementation of Wireless Sensor Networks in Particulate Matter Reduction Using an Air Quality Monitoring System

Mare Srbinovska
Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ., Skopje, Macedonia
mares@feit.ukim.edu.mk

Air pollution in cities adversely affects human health. One mitigation strategy is the use of green walls, whose plants absorb particulate matter (PM) through leaves and growing media.

This paper presents a low-cost, energy-efficient wireless sensor network for air quality monitoring, deployable in urban areas of interest. The system measures PM concentration before and after green wall installation.

Preliminary results from an ongoing experiment show measurable reduction in PM levels near green walls, validated by real-time data from the sensor network.

Walks in starlike graphs

Dragan Stevanović
Mathematical Institute, Serbian Academy of Sciences and Arts, Belgrade, Serbia
dragance106@yahoo.com

The number of walks of length $k$ in a graph is given by the sum of entries in $A^k$, where $A$ is the adjacency matrix.

Comparing walk counts between graphs yields inequalities for:

  • spectral radii,
  • Estrada indices.

Using injective embeddings of walk sets (with occasional shortcuts), we prove that the ordering of starlike trees by number of walks coincides with the shortlex ordering of nondecreasing sequences of their branch lengths.

On space syntax: applications of graph theory to architecture

Sanja Stevanović
Mathematical Institute, Serbian Academy of Sciences and Arts, Belgrade, Serbia
sanjastevanovic@yahoo.com

Space syntax is a subfield of architecture and urbanism that uses graph theory to model spatial configurations.

Graphs represent:

  • rooms or streets as vertices,
  • adjacencies or connections as edges.

Common invariants used:

  • integration (closeness centrality),
  • connectivity (degree),
  • depth (distance from entrance).

This talk reviews methods for assigning graphs to buildings and discusses how graph invariants quantify spatial properties like accessibility, visibility, and navigability.

Odd colorings and coverings of graphs

Riste Škrekovski
Faculty of Information Studies, Novo mesto & University of Ljubljana, Slovenia
skrekovski@gmail.com
(Joint work with Risto Atanasov, Borut Lužar, and Mirko Petruševski)

A (finite) graph is odd if all its vertices have odd degrees.

Given a graph $G$, define:

  • $\chi(G)$: minimum number of odd subgraphs in a decomposition of $G$,
  • $\mathrm{cov}_o(G)$: minimum number in an edge-cover by odd subgraphs.

Known results:

  • Pyber (1991): $\chi(G) \leq 4$ for all simple graphs,
  • Matrai (2006): $\mathrm{cov}_o(G) \leq 3$,
  • Both bounds are sharp.

Recent work provides structural characterizations for loopless multigraphs achieving these bounds. Moreover:

  • Deciding $\chi(G) \leq 4$ is in P,
  • Deciding $\chi(G) \leq 2$ is in P (Kano et al., 2019),
  • For subcubic graphs, $\chi(G) \leq 2$ is decidable in linear time,
  • But deciding $\mathrm{cov}_o(G) \leq 2$ may be NP-hard.

We also discuss list analogues, generalizations, and open problems.

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