In this paper, we show that for every sufficiently large integer $n$ and every positive integer $c\le \lfloor \frac{1}{6}(\log \log n{)}^{\frac{1}{2}}\rfloor$, a Boolean lattice with $n$ atoms can be partitioned into chains of cardinality $c$, except for at most $c-1$ elements which also form a chain.

We construct all self-dual $[24,12,8]$ quaternary codes with a monomial automorphism of prime order $r>3$ and obtain a unique code for $r=23$ (which has automorphisms of orders $5$, $7$, and $11$ too), two inequivalent codes for $r=11$, $6$ inequivalent codes for $r=7$, and $12$ inequivalent codes for $r=5$. The obtained codes have $12$ different weight spectra.

Metamorphoses of small $k$-wheel systems for $k=3,4,$ and $6$ are obtained. In particular, we obtain simultaneous metamorphoses of: $3$-wheel systems into Steiner triple systems and into $K_{1,3}$-designs; $4$-wheel systems into $4$-cycle systems, $K_{1,4}$-designs, and bowtie systems; $6$-wheel systems into $6$-cycle systems, $K_{1,6}$-designs, and $3$-windmill designs or near-$3$-windmill designs.

We deal with the problem of labeling the vertices, edges, and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face, and the weights of all the faces constitute an arithmetical progression of difference $d$.

If $L$ is a list assignment function and $\kappa$ is a multiplicity function on the vertices of a graph $G$, a certain condition on $(G,L,\kappa )$, known as Hall’s multicoloring condition, is obviously necessary for the existence of a multicoloring of the vertices of $G$. A graph $G$ is said to be in the class $MHC$ if it has a multicoloring for any functions $L$ and $\kappa$ such that $(G,L,\kappa )$ satisfies Hall’s multicoloring condition. It is known that if $G$ is in $MHC$ then each block of $G$ is a clique and each cutpoint lies in precisely two blocks. We conjecture that the converse is true as well. It is also known that if $G$ is a graph consisting of two cliques joined at a point then $G$ is in $MHC$. We present a new proof of this result which uses common partial systems of distinct representatives, the relationship between matching number and vertex covering number for 3-partite hypergraphs, and Menger’s Theorem.

This paper presents a new approach in the quest for a solution to the $3x+1$ problem. The method relies on the convergence of the trajectories of the odd positive integers by exploiting the role of the positive integers of the form $1+4n$, where $n$ is a non-negative integer.

A cyclic or bicyclic $9\times 37$ double Youden rectangle (DYR) is provided for each of the four biplanes with $k=9$. These DYRs were obtained by computer search.

For loopless plane multigraphs $G$, the edge-face chromatic number and the entire chromatic number are asymptotically their fractional counterparts (LP relaxations) as these latter invariants tend to infinity. Proofs of these results are based on analogous theorems for the chromatic index and the total chromatic number, due, respectively, to Kahn [3] and to the first author [6]. Our two results fill in the missing pieces of a complete answer to the natural question: which of the seven invariants associated with colouring the nonempty subsets of $\{V,E,F\}$ exhibit “asymptotically good” behaviour?

The bin packing problem has been studied extensively since the 1970’s, and it is known to be applicable to many different areas, especially in operations research and computer science. In this paper, we present a variant of the classical bin packing problem, which allows the packing to exceed its bin size but at least a fraction of the last piece is within the bin, and we call it the open-end bin packing problem. This paper is focused on on-line open-end bin packing. An on-line open-end bin packing algorithm is to assign incoming pieces into the bins on-line, that is, there is no information about the sizes of the pieces in future arrivals. An on-line algorithm is optimal if it always produces a solution with the minimum number of bins used for packing. We show that no such optimal algorithm exists. We also present seven efficient on-line algorithms: Next Fit, Random Fit, Worst Fit, Best Fit, Refined Random Fit, Refined Worst Fit, and Refined Best Fit, which give sub-optimal solutions. The performances of these algorithms are studied. A case study for the application of the studied problem is presented, and this is a practical problem on maximizing the savings of using stored-value tickets issued by Kowloon-Canton Railway (KCR), which is one of the major public transportation means in Hong Kong.

We explore the maximum possible toughness among graphs with $n$ vertices and $m$ edges in the cases in which $\lceil \frac{3n}{2}\rceil \le m<2n$. In these cases, it is shown that the maximum toughness lies in the interval $[\frac{4}{3},\frac{3}{2}]$. Moreover, if $\lceil \frac{3n}{2}\rceil +2\le m<2n$, then the value $\frac{3}{2}$ is achieved. However, if $m\in \{\lceil \frac{3n}{2}\rceil ,\lceil \frac{3n}{2}\rceil +1\}$, then the maximum toughness can be strictly less than $\frac{3}{2}$. This provides an infinite family of graphs for which the maximum toughness is not half of the maximum connectivity. The values of maximum toughness are computed for all $1\le n\le 12$, and some open problems are presented.

A set $S$ of vertices of a graph $G=(V,E)$ is a total dominating set if every vertex of $V(G)$ is adjacent to some vertex in $S$. The total domination number ${\gamma }_t(G)$ is the minimum cardinality of a total dominating set of $G$. We define the total domination subdivision number $s{d}_{\gamma t}(G)$ to be the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the total domination number. We give upper bounds on the total domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on $G$ sufficient to imply that $s{d}_{\gamma t}(G)\le 3$. On the other hand, we show that this constant upper bound does not hold for all graphs. Finally, we show that $1\le s{d}_{\gamma t}(T)\le 3$ for any tree $T$, and characterize the caterpillars $T\$forwhich\text{(}s{d}_{\gamma t}(T)=3$.

We show that for every $d\ge 2$, the number of spanning trees of a $d$-dimensional grid with $N$ vertices grows like $C(d{)}^N$ for some constant $C(d)$. Moreover, we show that $C(d)=2d-\frac{1}{2}-\frac{5}{16d}+O(d^{-2})$ as $d$ goes to infinity.

An extended 5-cycle system of order $n$ is an ordered pair $(V,B)$, where $B$ is a collection of edge-disjoint 5-cycles, 2-tadpoles, and loops that partition the edges of the graph $K_n^{+}$ whose vertex set is an $n$-set $V$. In this paper, we show that an extended 5-cycle system of order $n$ exists for all $n$ except $n=2$ and $3$.

McMorris, Zaslavsky, and Diny give characterizations of upper bound graphs and double bound graphs in terms of edge clique covers, that is, a family of maximal complete subgraphs that covers all edges. Lundgren and Maybee give a characterization of upper bound graphs using a concept of non-maximal complete subgraphs. In this paper, we present characterizations of double bound graphs and semi-bound graphs in terms of edge covers of non-maximal complete subgraphs.

We consider families of linear self-orthogonal and self-dual codes over the ring $Z_4$, which are generated by weighing matrices $W(n,k)$ with $k\equiv 0(\mathrm{mod}4)$, whose entries are interpreted as elements of the ring $Z_4$. We obtain binary formally self-dual codes of minimal Hamming distance 4 by applying the Gray map to the quaternary codes generated by $W(n,4)$.

Let $G=(V,E)$ be a simple, undirected graph. A set of vertices $D$ is called an odd dominating set if for every vertex $v\in V(G)$, $|N[v]\cap D|\equiv 1(\mathrm{mod}2)$. The minimum cardinality of an odd dominating set is called the odd domination number of $G$. It is well known that every graph contains an odd dominating set, but this parameter has been studied very little. Our aim in this paper is to explore some basic features of the odd domination number and to compare it with the domination number of the graph, denoted by $\gamma (G)$. In addition, extremal values of ${\gamma }_{odd}(G)$ are calculated for several classes of graphs and a Nordhaus-Gaddum type inequality ${\gamma }_{odd}(G)+{\gamma }_{odd}(\overline{G})$ is considered.

In this paper, it will be shown that a Skolem sequence of order $n\equiv 0,1(\mathrm{mod}4)$ implies the existence of a graceful tree on $2n$ vertices which exhibits a perfect matching or a matching on $2n-2$ vertices. It will also be shown that a Hooked-Skolem sequence of order $n\equiv 2,3(\mathrm{mod}4)$ implies the existence of a graceful tree on $2n+1$ vertices which exhibits a matching on either $2n$ or $2n-2$ vertices. These results will be established using an algorithmic approach.

For $k\ge 1$ an integer, a set $D$ of vertices of a graph $G=(V,E)$ is a $k$-dominating set of $G$ if every vertex in $V–D$ is within distance $k$ from some vertex of $D$. The $k$-domination number ${\gamma }_k(G)$ of $G$ is the minimum cardinality among all $k$-dominating sets of $G$. For $\ell \ge 2$ an integer, the graph $G$ is $({\gamma }_k,\ell )$-critical if ${\gamma }_k(G)=\ell$ and ${\gamma }_k(G–v)=\ell –1$ for all vertices $v$ of $G$. If $G$ is $({\gamma }_k,\ell )$-critical for some $\ell$, then $G$ is also called a ${\gamma }_k$-critical graph. For a vertex $v$ of $G$, let $N_k(v)=\{u\in V–\{v\}|d(u,v)\le k\}$ and let ${\delta }_k(G)=min\{|N_k(v)|:v\in V\}$ and let ${\mathrm{\Delta }}_k(G)=max\{|N_k(v)|:v\in V\}$. It is shown that if $G$ is a nontrivial connected ${\gamma }_k$-critical graph, then ${\delta }_k(G)\ge 2k$. Further, it is established that the number of vertices in a $\gamma -k$-critical graph $G$ is bounded above by $({\mathrm{\Delta }}_k(G)+1)({\gamma }_k(G)-1)+1$ and that $G$ is a $({\gamma }_k,\ell )$-critical graph if and only if the $k$th power of $G$ is a $(\gamma ,\ell )$-critical graph. It is shown that $(k,\ell )$-critical graphs of arbitrarily large connectivity exist. Moreover, a graph without isolated vertices is shown to be ${\gamma }_k$-critical if and only if each of its blocks is ${\gamma }_k$-critical. Finally it is established that for an integer $\ell \ge 2$, every graph is an induced subgraph of some $({\gamma }_k,\ell )$-critical graph. This paper concludes with some partially answered questions and some open problems.

We provide complete lists of starters and Skolem sequences which generate perfect one-factorizations of complete graphs up to order $32$ for starters and $36$ for Skolem sequences. The resulting perfect one-factorizations are grouped into isomorphism classes, and further analysis of the results is performed.

We find new full orthogonal designs in order 72 and show that of 2700 possible $OD(72;s_1,s_2,s_3,72–s_1–s_2–s_3)$, 335 are known, of 432 possible $OD(72;s_1,s_2,72–s_1–s_2)$, 308 are known. All possible $OD(72;s_1,72–s_1)$ are known.

Classical bin packing has been studied extensively in the literature. Open-ends bin packing is a variant of the classical bin packing. Open-ends bin packing allows pieces to be partially beyond a bin, while the classical bin packing requires all pieces to be completely inside a bin. We investigate the open-ends bin packing problem for both the off-line and on-line versions and give algorithms to solve the problem for parametric cases.