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\).

The distance \( d(u, v) \) between a pair of vertices \( u \) and \( v \) in a connected graph \( G \) is the length of a shortest path joining them. A vertex \( v \) of a connected graph \( G \) is an eccentric vertex of a vertex \( u \) if \( v \) is a vertex at greatest distance from \( u \); while \( v \) is an eccentric vertex of \( G \) if \( v \) is an eccentric vertex of some vertex of \( G \). A vertex \( v \) of \( G \) is a boundary vertex of a vertex \( u \) if \( d(u,w) \leq d(u,v) \) for each neighbour \( w \) of \( v \). A vertex \( v \) is a boundary vertex of \( G \) if \( v \) is a boundary vertex of some vertex of \( G \). It is easy to see that for a vertex \( u \), its eccentric vertices are boundary vertices for \( u \); but not conversely. In this paper, we introduce a new type of eccentricity called b-eccentricity and we study its properties.

A labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge \((x,y)\) is the absolute value of the difference of the labels of \(x\) and \(y\). We say that a labeling of the vertices of a graph of order \(n\) is minimally \(k\)-equitable if the vertices are labeled with \(1, 2, \dots, n\) and in the induced labeling of its edges, every label either occurs exactly \(k\) times or does not occur at all. In this paper, we prove that Butterfly and Benes networks are minimally \(2^r\)-equitable where \(r\) is the dimension of the networks.

The method of large scale group testing has been used in the economical testing of blood samples, and in non-testing situations such as experimental designs and coding theory, for over \(50\) years. Some very basic questions addressing the minimum number of tests required to identify defective samples still remain unsolved, including the situation where one defective sample in each of two batches are to be found. This gives rise to an intriguing graph theoretical conjecture concerning bipartite graphs, a conjecture which in this paper is proved to be true in the case where vertices in one part of the bipartite graph have low degree.

Using the action of the linear fractional groups \( L_2(q) \), where \( q = 8, 25, 27, 29, 31 \) and \( 32 \), some \( 1 \)-designs are constructed. It is shown that subgroups of the automorphism group of \( L_2(q) \) appear as the full automorphism group of the constructed designs. In the cases \( q = 8 \) and \( 32 \), it is shown that the symmetric groups \( \mathbb{S}_9 \) and \( \mathbb{S}_{33} \), respectively, appear as the automorphism group of one of the constructed designs.

Here we consider string matching problems that arise naturally in applications to music retrieval. The \( \delta \)-Matching problem calculates, for a given text \( T_{1..n} \) and a pattern \( P_{1..m} \) on an alphabet of integers, the list of all indices \( \mathcal{I}_\delta = \{1 \leq i \leq n-m+1 : \max_{j=1}^m \{|P_j – T_{i+j-1}| \leq \delta\}\} \). The \( \gamma \)-Matching problem computes, for given \( T \) and \( P \), the list of all indices \( \mathcal{I}_\gamma = \{1 \leq i \leq n-m+1 : \sum_{j=1}^m |P_j – T_{i+j-1}| \leq \gamma\} \). In this paper, we extend the current result on the different matching problems to handle the presence of “\emph{don’t care}” symbols. We present efficient algorithms that calculate \( \mathcal{I}_\delta \), \( \mathcal{I}_\gamma \), and \( \mathcal{I}_{(\delta,\gamma)} = \mathcal{I}_\delta \cap \mathcal{I}_\gamma \) for pattern \( P \) with occurrences of “don’t cares”.