A mapping of the set of undirected simple (loopless) graphs to itself is a linear operator if it maps the edgeless graph to the edgeless graph and maps the union of graphs to the union of their images. A linear operator preserves a set if it maps that set to itself. We study linear operators that map sets defined by the restriction of their chromatic number. For example the set of all graphs whose chromatic number is at least \(k\) for some fixed \(3\leq k\leq n\). We show these linear operators must be vertex permutations.

The first Zagreb index of a graph \(G\) is defined as \(\sum\limits_{u \in V} d_G^2(u)\), where \(d_G(u)\) is the degree of vertex \(u\) in \(G\). The algebraic connectivity of a graph \(G\) is defined as the second smallest eigenvalue of the Laplacian matrix of \(G\). Using Wagner’s inequality, we in this paper first obtain an upper bound for the algebraic connectivity that involves the first Zagreb index of a graph. Following the ideas of obtaining the upper bound, we present sufficient conditions involving the first Zagreb index and the algebraic connectivity for some Hamiltonian properties of graphs.

We present a proof of a conjecture of Goh and Wildberger on the factorization of the spread polynomials. We indicate how the factors can be effectively calculated and exhibit a connection to the factorization of Fibonacci numbers into primitive parts.

For a graph \(G\), let \(la(G)\) denote the linear arboricity of \(G\) and \(\Delta(G)\) denote the maximum degree of \(G\). The famous linear arboricity conjecture was made by Akiyama, Exoo, and Harary [Covering and packing in graphs. IV. Linear arboricity] in 1981. It asserts that \(la(G) \leq \Bigl\lceil\frac{\Delta(G)+1}{2}\Bigr\rceil\). In this paper, we prove the linear arboricity conjecture for products of a path and a complete graph, and for products of a path and a tree.

Let \(G\) be a connected graph. The center function defined on \(G\) yields a set of vertices that minimizes the maximum distance from the given input vertices. Through axiomatic characterization of the center function, we identify the specific axioms that characterize its behavior on connected graphs. Universal axioms encompass the properties satisfied by the center function on all connected graphs. However, for some graphs, the center function cannot be fully characterized using universal axioms alone. To address this, a set of graph class-specific axioms, known as non-universal axioms, was introduced. In the case of book graphs (Cartesian product of star graph \(K_{1,n}\) and path \(P_2\)), the center function cannot be adequately characterized using known universal axioms. Therefore, in this context, we find an axiomatic characterization of the center function on book graphs using the universal axioms and one newly introduced Cycle Consensus \((CC)\) axiom.

We study a search problem on capturing a moving target on an infinite real line. Two autonomous mobile robots (which can move with a maximum speed of 1) are initially placed at the origin, while an oblivious moving target is initially placed at distance d from the origin. The robots can move along the line in either direction, but the target is oblivious, cannot change direction, and moves either away from or toward the origin at a constant speed v. Our aim is to design efficient algorithms for two robots to capture the target. The target is captured only when both robots are co-located with it. The robots communicate only face-to-face (F2F), meaning they can exchange information only when co-located. We design algorithms under various knowledge scenarios regarding d, v, and the target’s direction of movement. We analyze competitive ratios, i.e., the capture time versus the optimal full-knowledge scenario, and show that our strategies use at most three direction changes.