Workshop on Applied Mathematics and Graph Theory

3rd Macedonian Workshop on Graph Theory and Its Applications (2018)

Ohrid, August 13–17, 2018
Book of Abstracts

The third edition of the Workshop on Applied Mathematics and Graph Theory was held in August 2018 in Ohrid, Macedonia.

Invited Talk

A Word on the Quality of Topological Molecular Descriptors

Boris Furtula
Faculty of Science, University of Kragujevac, Serbia
furtula@kg.ac.rs

A molecular descriptor is an inescapable ingredient in QSPR/QSAR researches. There is a legion of so-called molecular descriptors. However, a majority of them have never been used in any chemically sound investigation, but they are just a product of mathematical joggling.

This talk aims to present a chemist’s view on molecular descriptors. A couple of topics will be covered here:

  • A definition of a molecular descriptor;
  • Classification of molecular descriptors;
  • A history of molecular descriptors;
  • A recipe for developing a topological “molecular” descriptor;
  • Qualities of a proper molecular descriptor.

The focus of this talk will be on the qualities of molecular descriptors and the ways in which they could be quantified. These will be illustrated on the symmetric division deg index. Quantified properties of topological molecular descriptors are suitable for ranking and filtering existing ones, but also, they could be used as a condition that must be met when introducing new topological indices.

Contributed Talks

Vertex geometry on hexagonal lattice and nanotubes

Vesna Andova
Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ., Ruger Boskovik 18, 1000 Skopje, Macedonia
vesna.andova@gmail.com
(Joint work with Pavel Dimovski and Riste Škrekovski)

Nanotubes are graphs obtained by wrapping a hexagonal grid, and then possibly closing the tube with patches. Here we assign a coordinate to each vertex on a hexagonal grid, and respectively on a tube. This approach might be very useful when dealing with distances on a hexagonal tube as well as on benzenoid systems.

Some results on unique-maximum coloring of plane graphs

Riste Škrekovski
Faculty of Information Studies, Novo mesto & Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
skrekovski@gmail.com
(Joint work with Vesna Andova, Bernard Lidický, Borut Lužar, and Kacy Messerschmidt)

A unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face $\alpha$, the maximal color appears exactly once on the vertices of $\alpha$.

Fabrici and Gőring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem. Wendland later decreased the upper bound from six to five.

We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. So, we conclude that the facial unique-maximum chromatic number of the sphere is not four but five.

Additionally, we will consider a facial edge-coloring analogue of the aforementioned coloring.

Relaxed version of Šoltés’s problem

Snježana Majstorović
University of Osijek, Croatia
smajstor@mathos.hr

The total distance or Wiener index $W(G)$ of a connected graph $G$ is defined as the sum of distances between all (unordered) pairs of vertices in $G$. In 1991, Šoltés posed the following problem:

Find all such graphs $G$ that the equality $W(G) = W(G - v)$ holds for all their vertices $v$.

Until now, only one such graph is known: it is a cycle with 11 vertices ($C_{11}$).

Motivated by Šoltés’s problem, we construct an infinite family of unicyclic graphs which preserve total distance after removal of a particular vertex. We prove that there are infinitely many unicyclic graphs with this property even when we fix the length of the cycle.

We show that for every graph $G$ there are infinitely many graphs $H$ such that $G$ is an induced subgraph of $H$ and $W(H) = W(H - v)$ for some vertex $v \in V(H) \setminus V(G)$.

For $k > 3$, we show that there are infinitely many graphs $G$ with a vertex $v$ of degree $k$ for which $W(G) = W(G - v)$.

We prove the existence of such graphs when the degree is $n - 1$ or $n - 2$. Finally, we show that dense graphs cannot be a solution of Šoltés’s problem.

Our contribution shows that the class of graphs whose total distance does not change when a particular vertex is removed is rich. This gives hope that Šoltés’s problem may have another solution besides $C_{11}$.

Steiner triple systems with small circumference

Justin Z. Schroeder
USA & Macedonia
jzschroeder@gmail.com

Let $S = (V, \mathcal{B})$ be a Steiner triple system on $n$ points. For any distinct points $a, b \in V$, let $G_{a,b}$ be the graph on vertex set $V \setminus \{a,b,c\}$, where $\{a,b,c\} \in \mathcal{B}$, such that $xy$ is an edge in $G_{a,b}$ if and only if $\{a,x,y\} \in \mathcal{B}$ or $\{b,x,y\} \in \mathcal{B}$.

$G_{a,b}$ is called a cycle graph and consists of a disjoint union of even cycles.

We define the circumference of $S$, denoted $c(S)$, to be the length of the longest cycle contained in any cycle graph $G_{a,b}$, and we define $c(n)$ to be the minimum value of $c(S)$ taken over all Steiner triple systems $S$ of order $n$.

In this talk, we present some constructions for $\mathrm{STS}(n)$ with small circumference, discuss what is known about $c(n)$ for $n < 100$, and apply these results to a graph coloring problem of Häggkvist.

On vertex-parity edge-colorings

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

A vertex signature of a finite graph $G$ is any mapping $\tau : V(G) \to \{0,1\}$. An edge-coloring of $G$ is said to be vertex-parity for the pair $(G,\tau)$ if for every vertex $v$, each color used on the edges incident to $v$ appears in parity accordance with $\tau$, i.e., an even or odd number of times depending on whether $\tau(v)$ equals $0$ or $1$, respectively.

The minimum number of colors for which $(G,\tau)$ admits such an edge-coloring is denoted by $\chi'(G,\tau)$. We present necessary and sufficient conditions for existence of such a coloring, and discuss the possible values of this graph parameter. We also mention a recent application of vertex-parity edge-colorings.

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