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.

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.

We present a theorem which characterizes the class of line graphs of directed graphs. The characterization is an analogue of both the characterization of line graphs by Krausz (1943) and of directed line graphs of directed graphs by Harary and Norman (1960). Our characterization simplifies greatly in the case that the graph is bipartite. This and another result which we present draws attention to the special case of bipartite line graphs of directed graphs. As a result we explore the problem of finding the complete list of forbidden subgraphs for the class of bipartite line graphs of directed graphs. It appears, however, that this problem is extremely difficult. We do find two infinite families of forbidden subgraphs as well as several other illustrative examples.

A block graph is a graph in which each block (maximal biconnected subgraph) is a clique. A block graph can, equivalently, be seen as a tree of cliques where the blocks form complete subgraphs connected to each other in a tree-like, hierarchical structure. Such graphs provide a good conceptual and computational framework in designing, analyzing, and optimizing resilient and efficient power networks. In view of the above applications, this paper investigates the \(k\)-fault tolerant power domination number of block graphs. Also, we obtained a lower bound for \(k\)-fault tolerant power domination number when an edge in the graph is contracted.

We define \(3\)-PBIBDs to simplify the notation used in one of Hanani’s celebrated papers, where he developed important tools for the constructions of \(3\)-designs. A special case of the \(3\)-PBIBD, a \(3\)-GDD\((n,2,4;\lambda_1,\lambda_2)\), was recently studied in [5] and [6]. In this note, we develop necessary conditions for the existence of another special case, denoted \(3'\)-GDD\((n,3,4;\) \(\mu_1,\mu_2)\), and provide several constructions for infinite families of these designs. We show that the necessary conditions are sufficient for the existence of \(3'\)-GDD\((n,3,4;\mu_1,\mu_2)\) when \(\mu_2=0\) and \(\mu_1\) is arbitrary. In particular, when \(\mu_1\) is even and \(\mu_2 = 0\), such designs exist for all \(n\); and when \(\mu_1\) is odd and \(\mu_2 = 0\), they exist for even \(n\). We also provide instances of nonexistence.

A Kempe chain in a colored graph is a maximal connected component containing at most two colors. Kempe chains have played an important role historically in the study of the Four Color Problem. Some methods of systematically applying Kempe chain color exchanges have been studied by Alfred Errera and Weiguo Xie. A map constructed by Errera represents an important counterexample to some implementations of these methods. Using the ideas of Irving Kittell, we determine all colorings of the Errera map which form such a counterexample and describe how to color them individually. We then extend our results from the Errera map to a family of graphs containing the Errera map in a specific way. Being able to color this family of graphs appears to address many cases which prove difficult for the previous systematic color exchange methods.

We use Rosa-type labelings to decompose complete graphs into unicyclic, disconnected, non-bipartite graphs on nine edges. For any such graph \(H\), we prove there exists an \(H\)-design of \(K_{18k+1}\) and \(K_{18k}\) for all positive integers \(k.\)

In this paper, we continue investigation of decompositions of complete graphs into graphs with seven edges. The spectrum has been completely determined for such graphs with at most six vertices. The spectrum for bipartite graphs is completely known for graphs with seven or eight vertices. In this paper we completely solve the case of disconnected unicyclic bipartite graphs with seven edges by studying the remaining graphs with nine or ten vertices.