Cut vertices are often used as a measure of nodes’ importance within a network. These are nodes whose failure disconnects a connected graph. Let \(N(G)\) be the number of connected induced subgraphs of a graph \(G\). In this work, we investigate the maximum of \(N(G)\) where \(G\) is a unicyclic graph with \(n\) nodes of which \(c\) are cut vertices. For all valid \(n,c\), we give a full description of those maximal (that maximise \(N(.)\)) unicyclic graphs. It is found that there are generally two maximal unicyclic graphs. For infinitely many values of \(n,c\), however, there is a unique maximal unicyclic graph with \(n\) nodes and \(c\) cut vertices. In particular, the well-known negative correlation between the number of connected induced subgraphs of trees and the Wiener index (sum of distances) fails for unicyclic graphs with \(n\) nodes and \(c\) cut vertices: for instance, the maximal unicyclic graph with \(n=3,4\mod 5\) nodes and \(c=n-5>3\) cut vertices is different from the unique graph that was shown by Tan et al. [The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices. J. Appl. Math. Comput., 55:1–24, 2017] to minimise the Wiener index. Our main characterisation of maximal unicyclic graphs with respect to the number of connected induced subgraphs also applies to unicyclic graphs with \(n\) nodes, \(c\) cut vertices and girth at most \(g>3\), since it is shown that the girth of every maximal graph with \(n\) nodes and \(c\) cut vertices cannot exceed \(4\).

The honeymoon Oberwolfach problem HOP\((2m_1,2m_2,\ldots,2m_t)\) asks the following question. Given \(n=m_1+m_2+\ldots +m_t\) newlywed couples at a conference and \(t\) round tables of sizes \(2m_1,2m_2,\ldots,2m_t\), is it possible to arrange the \(2n\) participants at these tables for \(2n-2\) meals so that each participant sits next to their spouse at every meal, and sits next to every other participant exactly once? A solution to HOP\((2m_1,2m_2,\ldots,2m_t)\) is a decomposition of \(K_{2n}+(2n-3)I\), the complete graph \(K_{2n}\) with \(2n-3\) additional copies of a fixed 1-factor \(I\), into 2-factors, each consisting of disjoint \(I\)-alternating cycles of lengths \(2m_1,2m_2,\ldots,2m_t\). The honeymoon Oberwolfach problem was introduced in a 2019 paper by Lepine and Šajna. The authors conjectured that HOP\((2m_1,2m_2,\ldots,\) \(2m_t)\) has a solution whenever the obvious necessary conditions are satisfied, and proved the conjecture for several large cases, including the uniform cycle length case \(m_1=\ldots=m_t\), and the small cases with \(n \le 9\). In the present paper, we extend the latter result to all cases with \(n \le 20\) using a computer-assisted search.

We introduce and investigate a new class of graph maps, called backward edge-preserving maps. These are the maps between the vertex sets of graphs such that the pre-image of every edge in the target graph is an edge in the source graph. We give a complete structural characterization of such maps for both general and connected graphs. We also explore the relationship between backward edge-preserving maps, metric maps, and graph homomorphisms, and establish criteria for the intersection of these classes. Furthermore, we study a related class of graph cohomomorphisms and establish conditions under which a map can simultaneously be a homomorphism and a cohomomorphism.

A directed star is a star digraph in which the centre is either a sink or a source. With every directed star, we associate a weight \(w\left(\alpha\right)\). Let \(D\) be a digraph; and \(C\), a spanning subgraph of \(D\); in which every component is a directed star. Then \(C\) is called a directed star cover of \(D\), and the weight of \(C\) is \(w(C)=\prod_{\alpha}w\left(\alpha\right)\), where the product is taken over all the components \(\alpha\) of \(C\). The directed star polynomial of \(D\) is \[E\left(D;\mathbf{w}\right)=\sum w(C),\] where the sum is taken over all the directed star covers of \(D\). The paper establishes properties of star polynomials and establishes relationships between star polynomials, source polynomials (where all components are source stars), and sink polynomials (where all components are sink stars). Furthermore, it presents methods to compute these polynomials for general digraphs. We derive formulae for the star polynomials of rooted products of digraphs. Moreover, we establish applications of these polynomials to several domination parameters and obtain results regarding these polynomials and independent sets in undirected graphs.

Let \(G\) be an undirected graph. The \(k\)-strong labeling (coloring) number of \(G\), \(\chi_k(G)\), is the minimum number of labels (colors) necessary to label all the vertices of \(G\) so that no two vertices that are exactly of distance \(k\) apart have the same label. \(\chi_1\) is the usual chromatic number. In this article it is shown that any linear operator on the set of graphs on \(n\) vertices thar preserves \(\chi_k\) is a vertex permutation.

Cartesian-product networks combine well-studied graphs to create new structures with inherited properties, making them valuable for interconnection networks and parallel algorithms. Cycle decompositions of these networks are crucial for fault tolerance and adaptive routing. In this paper, we address the hypercube version of the Oberwolfach problem, focusing on decompositions of \(Q_n\) into cycles of equal or unequal lengths. We present an algorithm that enumerates all possible cycle types in \(Q_n\) and determine which decompositions are feasible or infeasible for \(Q_4\). Using an inductive approach, we extend these results to \(Q_n\) by leveraging distinct perfect matchings of \(Q_4\), yielding a variety of cycle decompositions. Additionally, we present results on factorizations of \(Q_n\) when \(n\) is a power of \(2\). These findings enhance the understanding of cycle structures in hypercubes and their applications to interconnection networks.

We investigate the combinatorial structure of edge-disjoint triangle packings in the complete graph \(K_n\). Two triangles are said to be edge-disjoint if they share no common edges, though they may share at most one vertex. For a given \(n\), let \(T_n\) denote the total number of subsets of triangles in \(K_n\) that are pairwise edge-disjoint, including the empty set, and let \(T_n^k\) denote the number of \(k\)-element sets of such triangles. In this article, we establish: (i) a general recurrence relation for \(T_n\) that enables asymptotic analysis, yielding the growth \(\log T_n = \Theta(n^2 \log n)\) for large \(n\); (ii) exact closed-form formulas for the number of edge-disjoint pairs (\(T_n^2\)), triples (\(T_n^3\)), and quadruples (\(T_n^4\)) of triangles in \(K_n\) for \(n \geq 6\). These results extend classical work on Steiner Triple Systems and provide new tools for analyzing triangle packings in complete graphs.

This paper introduces Hadamard-type \(t\)-Fibonacci-Lehmer (HTFL) sequences, a new hybrid construction combining Lehmer and Fibonacci recurrences. We establish their fundamental properties, including simple periodicity, and extend the definition to finite groups, with a detailed study of the Heisenberg group. Building on these results, we propose two Diffie–Hellman-style key exchange protocols based on upper-triangular unipotent matrices parameterized by HTFL sequence terms. Our work thus connects sequence theory, group theory, and cryptography in a novel way. While the algebraic framework and periodicity analysis are rigorous, we present the cryptographic constructions primarily as a conceptual foundation. We also discuss potential security considerations and outline directions for strengthening these schemes under formal hardness assumptions. This study demonstrates that HTFL sequences provide a fertile ground for both combinatorial investigations and future cryptographic applications.

We model each 4\(\mathrm{\times}\)4 magic square by encoding its 16 integers as magnitudes of repelling positive point charges on a fixed 2D lattice, evolved under Coulomb forces with linear damping and a harmonic pinning to anchor sites. We simulate all 880 magic squares and compare them with equally sized ensembles of random permutations of \(\{1,{\dots},16\}\). Three readouts differentiate the ensembles. (i) Final positions: magic cases form sixteen tight, index-specific clusters on an annulus, whereas random cases show broader arcs and central accumulation. (ii) Displacement–correlation structure: across cases, many pair-of-pairs of inter-index displacements in magic squares are near-linearly dependent; the random ensemble exhibits only moderate relationships, with |r| and R\(^2\) distributions shifted to weaker correlation. (iii) Center potential: the Coulomb-type potential at the geometric center collapses to a single value at the anchors for all magic squares and remains narrowly distributed after dynamics, while random squares remain broad. Sensitivity analysis reveals a broad damping–stiffness region with high convergence, indicating that the results are robust to parameter choice.

Tolerance graphs, introduced by M. C. Golumbic and C. L. Monma in 1982, are a generalization of interval graphs. In this paper, we propose an application of coloring of tolerance graphs together with machine learning, in particular supervised learning, in solving problems of airport gate assignment during a pandemic of an airborne disease. The idea is to minimize a contact between passengers at the gates, in order to slow down a spread of the disease. This application includes calculating the chromatic number of a graph and finding a clique of a given size in the graph. As a result, we obtain the minimum number of gates needed under the given assumptions and the corresponding gate assignment. Further, we propose an application of list coloring, a generalization of a coloring, of tolerance graphs in solving these problems. Besides the theoretical approach, the corresponding algorithms are given. The algorithms developed may take into account several parameters, such as the number of passengers on a flight, the number of newly infected people per 1000 inhabitants. A similar approach can be taken for classroom assignment during a pandemic, scheduling meetings, etc.