10973679
Amalgamations of factorizations of complete equipartite graphs
Let t be a positive integer, and let L=(l"1,...,l"t) and K=(k"1,...,k"t) be collections of nonnegative integers. A graph has a (t,K,L) factorization if it can be represented as the edge-disjoint union of factors F"1,...,F"t where, for 1=
33185867
The computational complexity of the parallel knock-out problem
We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for a given bipartite graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers k>=2, the problem of whether a given bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) k rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time. We also show that r-regular graphs with r>=1, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.
32211298
Path factors and parallel knock-out schemes of almost claw-free graphs
An H"1,{H"2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H"1 and all other components (if there are any) isomorphic to the graph H"2. We completely characterise the class of connected almost claw-free graphs that have a P"7,{P"2}-factor, where P"7 and P"2 denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5^.^3^7^6) time algorithm for claw-free graphs on n vertices).
15187204
Defining sets for Latin squares given that they are based on groups
We investigate defining sets for Latin squares where we are given that the Latin square is the Cayley table for some group. Our main result is that the proportion of entries in a smallest defining set approaches zero as the order of the group increases without bound.