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.

This paper introduces an automaton model called a dual position automaton (a dual PA), and then gives a bit-parallel algorithm for generating a dual PA from a regular expression (RE). For any RE \( r \) over an alphabet \( \Sigma \), our translation algorithm generates a dual PA consisting of \( \tilde{m}(\tilde{m} + 1) \) bits in \( O(\tilde{m}\lceil \tilde{m}/w \rceil) \) time and space, where \( w \) is the length of a computer word, \( \tilde{m} = \sum_{a \in \Sigma} m_a \), and \( m_a \) is the number of occurrences of an alphabet symbol \( a \) in \( r \). Furthermore, we give a method to construct a compact DFA representation from a dual PA. This DFA representation requires only \( (\tilde{m} + 1) \sum_{a \in \Sigma} 2^{m_a} \) bits. Finally, we show RE matching algorithms using such a DFA representation.

We investigate the problem of efficient representations of intervals of positive integers in TCAM (Ternary Content Addressable Memory). The integers are encoded by binary strings of the same length \( n \) and a TCAM of width \( n \) is a string-oriented representation of arbitrary sets of \( n \)-bit strings in terms of a collection of simple sets, called rules. Each rule is a concatenation (of length \( m \)) of singleton sets (i.e., single digits \( 0 \) and \( 1 \)) or the set \(\{0,1\}\) denoted by \( * \). We consider a family of \( n \)-bit encodings for integers, called dense-tree encodings, which includes the lexicographic encoding (i.e., standard unsigned binary encoding) and the binary reflected Gray encoding. We provide exact bounds (with respect to \( n \)) on the minimal sizes of TCAMs representing a subset of \( n \)-bit strings corresponding to an interval. Some other issues related to the minimal sizes and number of essential rules of TCAMs are also investigated.