Let \(s'(G)\) denote the Hall-condition index of a graph \(G\). Hilton and Johnson recently introduced this parameter and proved that \(\Delta(G) \leq s'(G) \leq \Delta(G) + 1\). A graph \(G\) is \(s’\)-Class 1 if \(s'(G) = \Delta(G)\) and is \(s’\)-Class 2 otherwise. A graph \(G\) is \(s’\)-critical if \(G\) is connected, \(s’\)-Class 2, and, for every edge \(e\), \(s'(G – e) < s'(G)\). We use the concept of the fractional chromatic index of a graph to classify \(s’\)-Class 2 in terms of overfull subgraphs, and similarly to classify \(s’\)-critical graphs. We apply these results to show that the following variation of the Overfull Conjecture is true;

A graph \(G\) is \(s’\)-Class 2 if and only if \(G\) contains an overfull subgraph \(H\) with \(\Delta(G) = \Delta(H)\).

We prove that if \(m\) be a positive integer and \(X\) is a totally ordered set, then there exists a function \(\phi: X \to \{1,\ldots,m\}\) such that, for every interval \(I\) in \(X\) and every positive integer \(r \leq |I|\), there exist elements \(x_1 < x_2 < \cdots < x_r\) of \(I\) such that \(\phi(x_{i+1}) \equiv \phi(x_{i}) + 1 \pmod{m}\) for \(i=1,\ldots,r-1\).

We prove that the complete graph \(K_v\) can be decomposed into cuboctahedra if and only if \(v \equiv 1 \text{ or } 33 \pmod{48}\).

In this paper, we present algorithms for locating the vertices in a tree of \(n\) vertices of positive edge-weighted tree and a positive vertex-weighted tree from which we broadcast multiple messages in a minimum cost. Their complexity is \(O(n^2 \log n)\). It improves a direct recursive approach which gives \(O(n^3)\). In the case where all the weights are equal to one, the complexity is \(O(n)\).

The affine resolvable \(2-(27,9,4)\) designs were classified by Lam and Tonchev \([9, 10]\). We use their construction of the designs to examine the ternary codes of the designs and show, using Magma [3], that each of the codes, apart from two, contains, amongst its constant weight-9 codewords, a copy of the ternary code of the affine geometry design of points and planes in \(AG_3(F_3)\). We also show how the ternary codes of the 68 designs and of their dual designs, together with properties of the automorphism groups of the designs, can be used to characterize the designs.

A perfect hash function for a subset \(X\) of \(\{0,1,\ldots,n-1\}\) is an injection \(h\) from \(X\) into the set \(\{0,1,\ldots,m-1\}\).
Perfect hash functions are useful for the compact storage and fast retrieval of frequently used objects. In this paper, we discuss some new practical algorithms for efficient construction of perfect hash functions, and we analyze their complexity and program size.

A Kuratowski-type approach for \([2,3]\)-graphs, i.e., hypergraphs whose edges have cardinality not more than \(3\), is presented, leading to a well-quasi-order in such a context, with a complete obstruction set of six forbidden hypergraphs to plane embedding.

We show that, for all primes \(p \equiv 1 \pmod{4}\), \(29 \leq p < 10,000\), \(p \neq 97, 193, 257, 449, 641, 769, 1153, 1409, 7681\), there exist \({Z}\)-cyclic triplewhist tournaments on \(p\) elements which are also Mendelsohn designs. We also show that such designs exist on \(v\) elements whenever \(v\) is a product of such primes \(p\).

An algorithm is presented in which a polynomial deck, \(\mathcal{P}D\), consisting of \(m\) polynomials of degree \(m-1\), is analysed to check whether it is the deck of characteristic polynomials of the one-vertex-deleted subgraphs of the line graph, \(H\), of a triangle-free graph, \(G\). We show that if two necessary conditions on \(\mathcal{P}D\), identified by counting the edges and triangles in \(H\), are satisfied, then one can construct potential triangle-free root graphs, \(G\), and by comparing the polynomial decks of the line graph of each with \(\mathcal{P}D\), identify the root graph.

Let \(\sigma_2(G) = \min\{d_G(u)+d_G(v) | u,v \in V(G), u,v \notin E(G)\}\) for a non-complete graph \(G\). An \([a, b]\)-factor of \(G\) is a spanning subgraph \(F\) with minimum degree \(\delta(F) \geq a\) and maximum degree \(\Delta(F) \leq b\).
In this note, we give a partially positive answer to a conjecture of M. Kano. We prove the following results:

Let \(G\) be a 2-edge-connected graph of order \(n\) and let \(k \geq 2\) be an integer. If \(\sigma_2(G) \geq {4n}/{(k +2)}\), then \(G\) has a 2-edge-connected \([2, k]\)-factor if \(k\) is even and a 2-edge-connected \([2, k + 1]\)-factor if \(k\) is odd.
Indeed, if \(k\) is odd, there exists a graph \(G\) which satisfies the same hypotheses and has no 2-edge-connected \([2, k]\)-factor.
Nevertheless, we have shown that if \(G\) is 2-connected with minimum degree \(\delta(G) \geq {2n}/{(k +2)}\), then \(G\) has a 2-edge-connected \([2, k]\)-factor.