A simple graph \( G = (V(G), E(G)) \) admits an \( H \)-covering if every edge in \( E(G) \) belongs to a subgraph of \( G \) that is isomorphic to \( H \). An \((a,d)\)-\( H \)-\({antimagic\; total \;labeling}\) of \( G \) is a bijective function \( \xi : V(G) \cup E(G) \to \{1,2,\dots,|V(G)| + |E(G)|\} \) such that for all subgraphs \( H’ \) isomorphic to \( H \), the \( H \)-weights \( w(H’) = \sum_{v \in V(H’)} \xi(v) + \sum_{e \in E(H’)} \xi(e) \) constitute an arithmetic progression \( a, a+d, a+2d, \dots, a+(t-1)d \), where \( a \) and \( d \) are positive integers and \( t \) is the number of subgraphs of \( G \) isomorphic to \( H \). Additionally, the labeling \( \xi \) is called a \({super}\) \((a, d)\)-\( H \)-\({antimagic\; total\; labeling}\) if \( \xi(V(G)) = \{1, 2, \dots, |V(G)|\} \).

In this paper, we introduce the notion of \((a, d)\)-\( H \)-\({antimagic\; total\; labeling}\) and study some basic properties of such labeling. We provide an example of a family of graphs obtaining the labelings, that is providing \((a, d)\)-cycle-antimagic labelings of fans.

Let \( j \geq 2 \) be a natural number. For graphs \( G \) and \( H \), the size multipartite Ramsey number \( m_j(G, H) \) is the smallest natural number \( t \) such that any \( 2 \)-coloring by red and blue on the edges of \( K_{j \times t} \) necessarily forces a red \( G \) or a blue \( H \) as a subgraph. Let \( P_n \) be a path on \( n \) vertices. In this note, we determine the exact value of the size multipartite Ramsey number \( m_j(P_4, P_n) \) for \( n \geq 2 \).

Let \(j \geq 2\) be a natural number. For graphs \(G\) and \(H\), the size multipartite Ramsey number \(m_j(G, H)\) is the smallest natural number \(t\) such that any \(2\)-coloring by red and blue on the edges of \(K_{j \times t}\) necessarily forces a red \(G\) or a blue \(H\) as subgraph. Let \(P_n\) be a path on \(n\) vertices. In this note, we determine the exact value of the size multipartite Ramsey number \(m_j(P_4, P_n)\) for \(n \geq 2\).

In this paper, we determine the Ramsey number for the disjoint union of graphs versus a graph \( H \), especially \( R\left(\bigcup_{i=1}^{k} l_i S_{n_i}(1,1), W_6\right) \), \( R\left(\bigcup_{i=1}^{k} l_i S_{n_i}(1,2), W_6\right) \), and \( R\left(\bigcup_{i=1}^k l_i S_{n_i}, W_4\right) \).

In this paper, we discuss an upper bound for exponents of loopless asymmetric two-colored digraphs. If \( D \) is an asymmetric primitive two-colored digraph on \( n \) vertices, we show that \( \text{exp}(D) \leq 3n^2 + 2n – 2 \). For an asymmetric two-colored digraph \( D \) which contains a primitive two-colored cycle of length \( s \leq n \), we show its exponent is at most \( \frac{s^2 – 1}{2} + (s + 1)(n – s) \). We characterize such two-colored digraphs whose exponents equal \( \frac{s^2 – 1}{2} + (s + 1)(n – s) \) and show that the largest exponent of an asymmetric two-colored digraph lies in the interval \( \left[\frac{n^2 – 1}{2}, 3n^2 + 2n – 2\right] \) when \( n \) is odd, or \( \left[\frac{n^2}{2}, 3n^2 + 2n – 2\right] \) otherwise.

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.

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.

This article develops an efficient combinatorial algorithm based on labeled directed graphs and motivated by applications in data mining for designing multiple classifiers. Our method originates from the standard approach described in [37]. It defines a representation of a multiclass classifier in terms of several binary classifiers. We are using labeled graphs to introduce additional structure on the classifier. Representations of this sort are known to have serious advantages. An important property of these representations is their ability to correct errors of individual binary classifiers and produce correct combined output. For every representation like this we develop a combinatorial algorithm with quadratic running time to compute the largest number of errors of individual binary classifiers which can be corrected by the combined multiple classifier. In addition, we consider the question of optimizing the classifiers of this type and find all optimal representations for these multiple classifiers.

A graph is called supermagic if it admits a labeling of its edges by consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper, we prove that the necessary conditions for an \( r \)-regular supermagic graph of order \( n \) to exist are also sufficient. All proofs are constructive and they are based on finding supermagic labelings of circulant graphs.

A distance magic labeling of a graph of order \( n \) is a bijection \( f: V \to \{1, 2, \dots, n\} \) with the property that there is a positive integer constant \( k \) such that for any vertex \( x \), \( \sum_{y \in N(x)} f(y) = k \), where \( N(x) \) is the set of vertices adjacent to \( x \). In this paper, we prove new results about the distance magicness of graphs that have minimum degree one or two. Moreover, we construct distance magic labeling for an infinite family of non-regular graphs.

Since Moore digraphs do not exist for \( k \neq 1 \) and \( d \neq 1 \), the problem of finding digraphs of out-degree \( d \geq 2 \), diameter \( k \geq 2 \) and order close to the Moore bound becomes an interesting problem. To prove the non-existence of such digraphs or to assist in their construction (if they exist), we first may wish to establish some properties that such digraphs must possess. In this paper, we consider the diregularity of such digraphs. It is easy to show that any digraph with out-degree at most \( d \geq 2 \), diameter \( k \geq 2 \) and order one or two less than the Moore bound must have all vertices of out-degree \( d \). However, establishing the regularity or otherwise of the in-degree of such a digraph is not easy. In this paper, we prove that all digraphs of defect two are either diregular or almost diregular. Additionally, in the case of defect one, we present a new, simpler, and shorter proof that a digraph of defect one must be diregular, and in the case of defect two and for \( d = 2 \) and \( k \geq 3 \), we present an alternative proof that a digraph of defect two must be diregular.

In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree \(d\) and \(d^2 + 1\) vertices), and found that such graphs exist only for \(d = 2, 3, 7\) and possibly \(57\). In 1980, Erdős et al., using eigenvalue analysis, showed that, with the exception of \(C_4\), there are no graphs of diameter 2, maximum degree \(d\) and \(d^2\) vertices. In this paper, we show that graphs of diameter 2, maximum degree \(d\) and \(d^2 – 1\) vertices do not exist for most values of \(d\) with \(d \geq 6\), and conjecture that they do not exist for any \(d \geq 6\).