2nd Conference on Applied Mathematics and Graph Theory (2017)

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

Conference Details

• Date: August 2017
• Location: Ohrid, Macedonia
• Venue: Hotel Kongresen Centar-Ohrid

Keynote Speakers

The conference featured invited talks from leading researchers in the field. Speakers included experts in graph theory, combinatorial optimization, and applied mathematics.

Topics Covered

1. Graph Theory: Structural graph theory, extremal graph theory, graph algorithms
2. Applied Mathematics: Mathematical modeling, optimization, numerical methods
3. Network Science: Complex networks, social networks, biological networks
4. Mathematical Chemistry: Chemical graph theory, molecular descriptors
5. Interdisciplinary Applications: Mathematics in computer science, engineering, and natural sciences

Impact

The 2nd conference built upon the success of the inaugural workshop, establishing the event as a regular gathering for researchers in the region. It helped to:

• Strengthen collaborations between institutions
• Provide a platform for young researchers to present their work
• Foster interdisciplinary discussions between mathematicians and applied scientists

Proceedings

Zagreb Indices and Beyond

Ivan Gutman
Faculty of Science, University of Kragujevac, Kragujevac, Serbia

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. Let $d(v)$ denote the degree (= number of first neighbors) of the vertex $v \in V(G)$. Two old (oldest) vertex–degree–based graph invariants that are of interest in mathematical chemistry are the first Zagreb index $M_1$ and the second Zagreb index $M_2$, defined as

Their mathematical properties were extensively studied in hundreds of papers.

Recently, several modifications of the Zagreb indices have been considered, of which the most interesting are the following: Some time ago the general first Zagreb index

was studied, where $\alpha$ is a real number. Special attention was paid to the cases $\alpha = -1$ (inverse degree) and $\alpha = 3$ (forgotten index).

The hyper–Zagreb index and the sigma-index are defined as:

The reformulated versions of Zagreb–type indices replace vertices with edges, and consider the degree $d(uv)$ of the edge $uv \in E(G)$. Thus, the reformulated Zagreb–type index of a graph $G$ is just the ordinary Zagreb–type index of the line graph $L(G)$.

Zagreb–type invariants, based on combination of vertex and edge degrees have also been put forward. Let $d_2(v)$ be the second-degree of the vertex $v$ (= number of its second neighbors). Then the leap Zagreb indices are

To each Zagreb–type index of the form

a coindex can be associated, defined as

Some properties of the above listed Zagreb–type indices will be mentioned and open problems discussed.

Lower bound on the Szeged index using the Wiener index

Martin Knor
Slovak University of Technology in Bratislava, Faculty of Civil Engineering, Bratislava, Slovakia
(Joint work with M. Bonamy, B. Lužar, A. Pinlou and R. Škrekovski)

Let $G$ be a connected non-complete graph on $n$ vertices. We prove that

with equality if and only if $G$ is the complete graph $K_{n-1}$ with one vertex attached to either 2 or $n-2$ vertices. Further, using our method we improve some known lower bounds on the Szeged index for special graphs, such as the bipartite graphs and the graphs of girth at least five. We also pose some related conjectures.

Maximal Wiener index for graphs with prescribed number of blocks

Katarína Hriňáková
Department of Mathematics and Descriptive Geometry, Faculty of Civil Engineering, Slovak University of Technology, Bratislava, Slovakia
(Joint work with Stéphane Bessy, François Dross and Riste Škrekovski)

Wiener index, which is defined as the sum of distances between all unordered pairs of vertices in a graph, is one of the oldest and also most popular molecular descriptors. We show that among all graphs on $n$ vertices and with given number of blocks $p$, the maximum Wiener index is attained either by a graph composed of a path of length $p-1$ with an attached cycle on $n-p+1$ vertices, or a graph composed of two cycles connected by a path of length $p - 2$, or just the path $P_n$ when $p = n - 1$.

One open problem on Wiener index of a graph

Snježana Majstorović
Department of Mathematics, Josip Juraj Strossmayer University of Osijek, Osijek, Croatia
(Joint work with Martin Knor and Riste Škrekovski)

The Wiener index $W(G)$ of a connected graph $G$ is defined to be the sum of distances between all pairs of vertices in $G$. In 1991 L. Šoltés studied changes of the Wiener index caused by removing a single vertex. He posed the problem of finding all graphs $G$ so that equality $W(G) = W(G - v)$ holds for all their vertices $v$. The cycle with 11 vertices was the unique known graph with this property.

We study this problem and find graphs whose Wiener index does not change when a particular vertex is removed. We show that there is a unicyclic graph $G$ on $n$ vertices with $W(G) = W(G - v)$ if and only if $n \geq 9$. Also, there is a unicyclic graph $G$ with a cycle of length $c$ for which $W(G) = W(G - v)$ if and only if $c \geq 5$. Moreover, we show that every graph $G$ is an induced subgraph of $H$, such that $W(H) = W(H - v)$. This shows that the class of graphs whose Wiener index does not change when a particular vertex is removed is rich. It gives hope that Šoltés’s problem may have also some solutions distinct from $C_{11}$.

Distance based topological indices on nanotubical graphs

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

Nanotubical graphs are obtained by wrapping a hexagonal grid, and then possibly closing the tube with patches. In this paper we determine asymptotic formulas for several distance-based topological indices, namely the Balaban index, Sum-Balaban index, Wiener index, Gutman index, and Harary index, for open nanotubes. In all the cases, the leading term depends on the circumference of the nanotubical graph, but not on its specific type.

Mathematical Aspects of Balaban index

Riste Škrekovski
Faculty of Information Studies, Novo mesto; Institute of Mathematics, Physics and Mechanics, Ljubljana; University of Primorska, FAMNIT, Koper, Slovenia
(Joint work with Martin Knor and Aleksandra Tepeh)

Balaban index is defined as

where the sum is taken over all edges of a connected graph $G$, $n$ and $m$ are the cardinalities of the vertex and the edge set of $G$, respectively, and $w(u)$ (resp. $w(v)$) denotes the sum of distances from $u$ (resp. $v$) to all the other vertices of $G$.

In the talk, I will present some of our mathematical results on this index. First, an upper bound for the Balaban index of $r$-regular graphs on $n$ vertices, and also improved bound for fullerene graphs. Next we consider graphs of order $n$ with minimum Balaban index, and finally about the accumulation points of this index.

Predicting melting points by the Graovac–Pisanski index

Niko Tratnik & Petra Žigert Pleteršek
University of Maribor, Maribor, Slovenia
(Joint work with Matevž Črepnjak)

The Graovac–Pisanski index, which is also called the modified Wiener index, was introduced in 1991 by A. Graovac and T. Pisanski. This variation of the classical Wiener index takes into account the symmetries of a graph.

More precisely, the Graovac–Pisanski index of a graph $G$ is defined as

In the talk, we will present how this index can be used to predict melting points of some families of molecules, for example alkanes and polyaromatic hydrocarbons.

The Stable Roommates Problem with Unranked Entries

Aleksandar Shurbevski
Kyoto University, Kyoto, Japan

The stable roommates problem (SR) and its extensions is one of the most well-studied problems in the area of matching under preference. Given a set of an even number of participants, each of which has ranked all of the others in a strict order of preference, the SR asks to determine pairs of participants such that each participant is matched in a pair, and there do not exist two participants that are not matched with each other, yet prefer each other to their assigned partners. Given a matching $M$, a pair of unmatched participants that prefer each othe to their partners matched by $M$ is said to be a blocking pair of $M$, and a matching that has no blocking pair is said to be stable.

Among the various extensions of the SR the most common ones are the SR with incomplete preference lists (SRI), where “acceptable” pairs are limited by only allowing participants that have included each other in their preference lists to be matched together; and the SR with partially ordered preference lists (SRP), which introduces “indifference” in participants’ preferences. In the context of indifference, more than one definition of stability are possible:

• A matching is called weakly stable if there is no pair of unmatched participants that strictly prefer each other to their matched partners,
• A matching is called super-stable if no two unmatched participants prefer each other to their matched partners, or are indifferent between each other and their respective matched partners.

There exist linear time algorithms for the SR and the SRI which give a stable matching or correctly determine that none exists. While the problem of finding a super-stable matching for an instance of the SRP (or determining that none exists) is solvable in polynomial time, the equivalent problem is NP-hard under weak stability.

Henceforth, we focus on weak stability and omit the quantifier “weak.” In light of the NP-hardness results from introducing indifference in the preference lists of the SR, we restrict the notion of indifference and introduce unranked entries, such that a participant is indifferent between an unranked and any other entry in her preference list. A pair of participants $u$ and $v$ such that $u$ is unranked in $v$’s preference list will never become a blocking pair since $v$ is indifferent between $u$ and any other participant in $v$’s preference list. Likewise, if $u$ and $v$ are matched in a matching $M$, then no pair including $v$ can become a blocking pair to $M$. We call this problem SRU, for stable roommates problem with unranked entries.

We show that the SRU is NP-complete even when

• all pairs are acceptable,
• each participant has two unranked entries in her preference list, or is an unranked entry of three other participants, and
• each participant does not have unranked entries, or is herself not unranked for any of the other participants.

On the other hand, given an SRU instance with $m$ acceptable pairs and $k$ unranked entries in total, we can devise an $O(2^k m)$-time algorithm to find a stable matching or determine that none exists. This algorithm is based on an enumeration procedure which for each of the $O(2^k)$ subsets of pairs including an unranked entry checks if there exists a stable matching containing that subset by applying a known $O(m)$-time delayed acceptance algorithm due to Gusfield and Irving for the SRI.

It is an interesting future research direction to investigate the nature of SR instances where indifference in participants’ preferences are further restricted, and in particular, determine if there exists a particular class of SRU instances that are solvable in polynomial time. It seems possible that the SRU where unranked entries form a matching in the corresponding graph can be solved in polynomial time.

Borderenergetic graphs

Boris Furtula
Faculty of Science, University of Kragujevac, Kragujevac, Serbia

Energy of a graph was conceived in 1978. It originates from the theoretical chemistry and it is strongly connected with the so-called total $\pi$-electron energy of a conjugated molecule.

Let $\lambda_1, \lambda_2, \dots, \lambda_n$ be the eigenvalues of a graph $G$. Then, the energy of a graph is defined as

Several hundreds of papers dealing with graph energy have been published so far. Numerous authors have been investigating hyperenergetic and hypoenergetic graphs. A hyperenergetic graph is one that has larger energy than a complete graph of the same order, while a hypoenergetic graph is one having energy lower than its order.

On the other hand, borderenergetic graphs are those that have the same energy as the complete graph of the same order:

Such graphs were introduced recently. The overview of results on borderenergetic graphs and computational efforts to designate them will be outlined.

Spanning trees and eigenvalues of graphs

Ebrahim Ghorbani
Department of Mathematics, K. N. Toosi University of Technology, Tehran, Iran
School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

Let $G$ be a graph. We denote by $A(G)$ the adjacency matrix, by $L(G)$ the line graph and by $\tau(G)$ the number of spanning trees of $G$. We study the interconnection between $\tau(G)$ and the multiplicities of even integer eigenvalues of $A(L(G))$. Our motivation comes partly from the previous works by several authors on the connection between $\tau(G)$ and the multiplicity of the zero eigenvalue, i.e. the nullity of $A(L(G))$.

Doob proved that the binary rank (i.e. the rank over the two-element field) of $A(L(G))$ for any connected graph $G$ of order $n$ is $n - 1$ if $n$ is odd, and $n - 2$ if $n$ is even. This result was stated and proved in the context of Matroid Theory. Considering the rank over the real numbers, Sciriha showed that the order of every tree whose line graph is singular is even and also that the nullity of the line graph of a tree is at most one.

Recently, Bapat found an interesting generalization by proving that if $\tau(G)$ is odd, then $A(L(G))$ has nullity at most 1. We extend these results to establish a closer connection between $\tau(G)$ and eigenvalues of $L(G)$ and $Q(G)$, the Laplacian and signless Laplacian matrices of graphs $G$, respectively. We prove that if $G$ has an odd number of vertices and $\tau(G)$ is not divisible by 4, then

1. $L(G)$ has no even integer eigenvalue,
2. $Q(G)$ has no integer eigenvalue $\lambda \equiv 2 \pmod{4}$, and
3. $Q(G)$ has at most one eigenvalue $\lambda \equiv 0 \pmod{4}$ and such an eigenvalue is simple.

As a consequence, we extend previous results by Gutman and Sciriha and by Bapat on the nullity of adjacency matrices of the line graphs. We also show that if $\tau(G) = 2^t s$ with $s$ odd, then the multiplicity of any even integer eigenvalue of $Q(G)$ is at most $t+1$. Among other things, we prove that if $L(G)$ or $Q(G)$ has an even integer eigenvalue of multiplicity at least 2, then $\tau(G)$ is divisible by 4. As a very special case of this result, a conjecture by Zhou et al. on the nullity of adjacency matrices of the line graphs of unicyclic graphs follows.

On two conjectures on sum of the powers of signless Laplacian eigenvalues of a graph

Firouzeh Ashraf
Technical and Vocational University, Tehran, Iran

Let $G$ be a simple graph and $Q(G)$ be the signless Laplacian matrix of $G$. Let $S_\alpha(G)$ be the sum of the $\alpha$-th powers of the nonzero eigenvalues of $Q(G)$. We disprove two conjectures by You and Yang on the extremal values of $S_\alpha(G)$ among bipartite graphs and among graphs with bounded connectivity.

Prime labeling of 2-regular graphs

Justin Z. Schroeder

A prime labeling of a graph $G$ on $n$ vertices is a bijection $f: V(G) \to \{1, 2, \dots, n\}$ such that $f(v)$ and $f(w)$ are relatively prime for every edge $vw$. It was conjectured in 1982 that a 2-regular graph, which must be a union of cycles, has a prime labeling if and only if at most one of the cycles has odd length. We will discuss how the author’s recent result that every cubic bipartite graph has a prime labeling applies to 2-regular graphs, and we will close with a strategy for providing a complete resolution to the original conjecture.

Odd edge-colorability of subcubic graphs

Riste Atanasov
Mathematics and Computer Science Department, Western Carolina University, USA
(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 $\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.