For a simple and finite graph \(G = (V,E)\), let \(w_{\max}(G)\) be the maximum total weight \(w(E) = \sum_{e\in E} w(e)\) of \(G\) over all weight functions \(w: E \to \{-1,1\}\) such that \(G\) has no positive cut, i.e., all cuts \(C\) satisfy \(w(C) \leq 0\).

For \(r \geq 1\), we prove that \(w_{\max}(G) \leq -\frac{|V|}{2}\) if \(G\) is \((2r-1)\)-regular and \(w_{\max}(G) \leq -\frac{r|V|}{2r+1}\) if \(G\) is \(2r\)-regular. We conjecture the existence of a constant \(c\) such that \(w_{\max}(G) \leq -\frac{5|V|}{6} + c\) if \(G\) is a connected cubic graph and prove a special case of this conjecture. Furthermore, as a weakened version of this conjecture, we prove that \(w_{\max}(G) \leq -\frac{2|V|}{3}+\frac{2}{3}\) if \(G\) is a connected cubic graph.

Let \(G_i\) be the subgraph of \(G\) whose edges are in the \(i\)-th color in an \(r\)-coloring of the edges of \(G\). If there exists an \(r\)-coloring of the edges of \(G\) such that \(H_i \nsubseteq G_i\) for all \(1 \leq i \leq r\), then \(G\) is said to be \(r\)-colorable to \((H_1, H_2, \ldots, H_r)\). The multicolor Ramsey number \(R(H_1, H_2, \ldots, H_r)\) is the smallest integer \(n\) such that \(K_n\) is not \(r\)-colorable to \((H_1, H_2, \ldots, H_r)\). It is well known that \(R(C_m, C_4, C_4) = m + 2\) for sufficiently large \(m\). In this paper, we determine the values of \(R(C_m, C_4, C_4)\) for \(m \geq 5\), which show that \(R(C_m, C_4, C_4) = m + 2\) for \(m \geq 11\).

The proof of gracefulness for the Generalised Petersen Graph \(P_{8t,3}\) for every \(t \geq 1\), written by the same author (Graceful labellings for an infinite class of generalised Petersen graphs, Ars Combinatoria \(81 (2006)\), pp. \(247-255)\), requires the change of just one label, for the only case \(t = 5\).

For words of length \(n\), generated by independent geometric random variables, we study the average initial and end heights of the last descent in the word. In addition, we compute the average initial and end height of the last descent in a random permutation of \(n\) letters.

We construct a record-breaking binary code of length \(17\), minimal distance \(6\), constant weight \(6\), and containing \(113\) codewords.

The purpose of this note is to give the power formula of the generalized Lah matrix and show \(\mathcal{L}[x,y] = \mathcal{FQ}[x,y]\), where \(\mathcal{F}\) is the Fibonacci matrix and \(\mathcal{Q}[x,y]\) is the lower triangular matrix. From it, several combinatorial identities involving the Fibonacci numbers are obtained.

A graph is called set reconstructible if it is determined uniquely (up to isomorphism) by the set of its vertex-deleted subgraphs. We prove that some classes of separable graphs with a unique endvertex are set reconstructible and show that all graphs are set reconstructible if all \(2\)-connected graphs are set reconstructible.

We prove the following extension of the Erdős-Ginzburg-Ziv Theorem. Let \(m\) be a positive integer. For every sequence \(\{a_i\}_{i\in I}\) of elements from the cyclic group \(\mathbb{Z}_m\), where \(|I| = 4m – 5\) (where \(|I| = 4m – 3\)), there exist two subsets \(A, B \subseteq I\) such that \(|A \cap B| = 2\) (such that \(|A \cap B| = 1\)), \(|A| = |B| = m\), and \(\sum\limits_{i\in b} a_i = \sum\limits_{i\in b} b_i = 0\).

A connected graph is said to be super edge-connected if every minimum edge-cut isolates a vertex. The restricted edge-connectivity \(\lambda’\) of a connected graph is the minimum number of edges whose deletion results in a disconnected graph such that each component has at least two vertices. It has been shown by A. H. Esfahanian and S. L. Hakimi (On computing a conditional edge-connectivity of a graph. Information Processing Letters, 27(1988), 195-199] that \(\lambda'(G) \leq \xi(G)\) for any graph of order at least four that is not a star, where \(\xi(G) = \min\{d_G(u) + d_G(v) – 2: uv \text{ is an edge in } G\}\). A graph \(G\) is called \(\lambda’\)-optimal if \(\lambda'(G) = \xi(G)\). This paper proves that the de Bruijn undirected graph \(UB(d,n)\) is \(\lambda’\)-optimal except \(UB(2,1)\), \(UB(3,1)\), and \(UB(2,3)\), and hence, is super edge-connected for \(n\geq 1\) and \(d\geq 2\).

The problem of graceful labeling of a particular class of trees called quasistars is considered. Such a quasistar is a tree \(Q\) with \(k\) distinct paths with lengths \(1, d+1, 2d+1, \ldots, (k-1)d+1\) joined at a unique vertex \(\theta\).

Thus, \(Q\) has \(1 + [1 + (d+1) + (2d+1) + \ldots + (k-1)d+1)] = 1+k +\frac{k(k-1)d}{2}\) vertices. The \(k\) paths of \(Q\) have lengths in arithmetic progression with common difference \(d\). It is shown that \(Q\) has a graceful labeling for all \(k \leq 6\) and all values of \(d\).