Let \( G = (V(G), E(G)) \) be a simple graph and let \( f \) be a function from \( V(G) \) to a subset of positive integers. An \( f \)-\({coloring}\) of \( G \) is a generalized edge-coloring such that every vertex \( v \in V(G) \) has at most \( f(v) \) edges colored with the same color. The minimum number of colors needed to define an \( f \)-coloring of \( G \) is called the \( f \)-\({chromatic\; index}\) of \( G \), and denoted by \( \chi_f'(G) \). The \( f \)-chromatic index of \( G \) is equal to \( \Delta_f(G) \) or \( \Delta_f(G) + 1 \), where \( \Delta_f(G) = \max \left\{ \frac{d(v)}{f(v)} \mid v \in V(G) \right\} \). \( G \) is called in the \({class-1}\), denoted by \( C_f1 \), if \( \chi_f'(G) = \Delta_f(G) \); otherwise \( G \) is called in the \({class-2}\), denoted by \( C_f2 \). In this paper, we show that the corona product of a cycle with either the complement of a complete graph, or a path, or a cycle is in \( C_f1 \).

For a simple graph \( G \) with the vertex set \( V \) and the edge set \( E \), a labeling \( \lambda: V \cup E \to \{1, 2, 3, \ldots, k\} \) is called a vertex-irregular total \( k \)-labeling of \( G \) if for any two different vertices \( x \) and \( y \) in \( V \) we have \( wt(x) \neq wt(y) \), where \( wt(x) = \lambda(x) + \sum_{xy \in E} \lambda(xy) \).

The total vertex-irregular strength, denoted by \( tvs(G) \), is the smallest positive integer \( k \) for which \( G \) has a vertex-irregular total \( k \)-labeling. In this paper, we determine the total vertex-irregular strength of a disjoint union of \( t \) copies of a path, denoted by \( tP_n \). We prove that for any \( t \geq 2 \),

\[
tvs(tP_n) =
\begin{cases}
t & \text{for } n = 1, \\
t+1 & \text{for } 2 \leq n \leq 3, \\
\lceil \frac{nt+1}{3} \rceil & \text{for } n \geq 4.
\end{cases}
\]

Let \( G = (V, E) \) be a graph with order \(|G|\) and size \(|E|\). An \((a, d)\)-vertex-antimagic total labeling is a bijection \( \alpha \) from the set of all vertices and edges to the set of consecutive integers \(\{1, 2, \ldots, |V| + |E|\}\), such that the weights of the vertices form an arithmetic progression with the initial term \( a \) and the common difference \( d \). If \( \alpha(V(G)) = \{1, 2, \ldots, |V|\} \) then we call the labeling super \((a, d)\)-vertex antimagic total. In this paper, we show some basic properties of such labelings on a disjoint union of regular graphs and demonstrate how to construct such labelings for some classes of graphs, such as cycles, generalized Petersen graphs, and circulant graphs, for \( d = 1 \).

In this paper, we determine the partition dimension of a complete multipartite graph \( K_{n_1, n_2, \ldots, n_r} \), namely \( pd(K_{n_1, n_2, \ldots, n_r}) \). We show that \( pd(K_{n_1, n_2, \ldots, n_r}) = r + n – 1 \) if \( n_i = n \) for \( 1 \leq i \leq r \), and \( pd(K_{n_1, n_2, \ldots, n_r}) = r + n – 2 \) for \( n = n_1 \geq n_2 \geq \ldots \geq n_r \). We also show that the partition dimension of the caterpillar graph \( C_n^m \) is \( m \) for \( n \leq m \) and \( m + 1 \) for \( n > m \), and the partition dimension of the windmill graph \( W_{2}^{n} \) is \( k \), where \( k \) is the smallest integer such that \( \binom{k}{2} \geq m \).

Let \( G \) be a graph with vertex set \( V = V(G) \) and edge set \( E = E(G) \), and let \( n = |V(G)| \) and \( e = |E(G)| \). A \({vertex-magic\; total\; labeling}\) (VMTL) of a graph is defined as a one-to-one mapping taking the vertices and edges onto the set of integers \(\{1, 2, \ldots, n+e\}\), with the property that the sum of the label on a vertex and the labels on its incident edges is a constant independent of the choice of vertex. In this paper, we present the vertex-magic total labeling of the disjoint union of \( t \) generalized Petersen graphs \(\bigcup_{j=1}^t P(n_j, m_j)\), and the disjoint union of \( t \) special circulant graphs \(\bigcup_{j=1}^t C_n(1, m_j)\).

A \((p,q)\)-graph \( G \) is called \((a,d)\)-\({edge\; antimagic\; total}\), in short \((a,d)\)-EAMT, if there exist integers \( a > 0 \), \( d \geq 0 \) and a bijection \( \lambda: V \cup E \to \{1, 2, \ldots, p+q\} \) such that \( W = \{w(xy) : xy \in E\} = \{a, a+d, \ldots, a + (q-1)d\} \), where \( w(xy) = \lambda(x) + \lambda(y) + \lambda(xy) \) is the edge-weight of \( xy \). An \((a,d)\)-EAMT labeling \( \lambda \) of \( G \) is \({super}\), in short \((a,d)\)-SEAMT, if \( \lambda(V) = \{1, 2, \ldots, p\} \). In this paper, we propose some theorems on how to construct new (bigger) \((a, d)\)-SEAMT graphs from old (smaller) ones.

Let \( G = (V, E) \) be a graph with \( V(G) \) as a set of vertices and \( E(G) \) as a set of edges, where \( n = |V(G)| \) and \( e = |E(G)| \). A graph \( G = (V, E) \) is said to be \((a, d)\)-vertex antimagic total if there exist positive integers \( a \), \( d \), and a bijection \( \lambda \) from \( V(G) \cup E(G) \) to the set of consecutive integers \(\{1, 2, \ldots, n+e\}\) such that the weight of vertices forms an arithmetical progression with initial term \( a \) and common difference \( d \). In this paper, we will give \((a, d)\)-vertex antimagic total labeling of disconnected graphs, which consists of the union of \( t \) suns for \( d \in \{1, 2, 3, 4, 6\} \).

For given graphs \( G \) and \( H \), the \({Ramsey\; number}\) \( R(G, H) \) is the least natural number \( n \) such that for every graph \( F \) of order \( n \) the following condition holds: either \( F \) contains \( G \) or the complement of \( F \) contains \( H \). In this paper, we determine the Ramsey number for a disjoint union of paths versus the cocktail party graph.

We study the complexity of the longest common subsequence (LCS) problem from a new perspective. By an indeterminate string (i-string, for short) we mean a sequence \( \tilde{X} = \tilde{X}[1]\tilde{X}[2]\ldots \tilde{X}[n] \), where \( \tilde{X}[i] \subseteq \Sigma \) for each \( i \), and \( \Sigma \) is a given alphabet of potentially large size. A subsequence of \( \tilde{X} \) is any usual string over \( \Sigma \) which is an element of the finite (but usually of exponential size) language \( \tilde{X}[i_1]\tilde{X}[i_2]\ldots \tilde{X}[i_p] \), where \( 1 \leq i_1 < i_2 < i_3 \ldots < i_p \leq n \), \( p \geq 0 \). Similarly, we define a supersequence of \( x \). Our first version of the LCS problem is Problem ILCS: for given i-strings \( \tilde{X} \) and \( \tilde{Y} \), find their longest common subsequence. From the complexity point of view, new parameters of the input correspond to \( |\Sigma| \), and maximum size \( \ell \) of the subsets in \( \tilde{X} \) and \( \tilde{Y} \). There is also a third parameter \( \mathcal{R} \), which gives a measure of similarity between \( \tilde{X} \) and \( \tilde{Y} \). The smaller the \( \mathcal{R} \), the lesser is the time for solving Problem ILCS. Our second version of the LCS problem is Problem CILCS (constrained ILCS): for given i-strings \( \tilde{X} \) and \( \tilde{Y} \) and a plain string \( Z \), find the longest common subsequence of \( \tilde{X} \) and \( \tilde{Y} \) which is, at the same time, a supersequence of \( Z \). In this paper, we present several efficient algorithms to solve both ILCS and CILCS problems. The efficiency in our algorithms is obtained in particular by using an efficient data structure for special types of range maxima queries and fast multiplication of boolean matrices.

We introduce a practical disk-based compressed text index that, when the text is compressible, takes much less space than the suffix array. It provides good I/O times for searching, which in particular improve when the text is compressible. In this aspect our index is unique, as most compressed indexes are slower than their classical counterparts on secondary memory. We analyze our index and show experimentally that it is extremely competitive on compressible texts. As side contributions, we introduce a compressed rank dictionary for secondary memory operating in one I/O access, as well as a simple encoding of sequences that achieves high-order compression and provides constant-time random access, both in main and secondary memory.