The maximum possible toughness among graphs with \(n\) vertices and \(m\) edges is considered. This is an analog of the corresponding problem regarding maximum connectivity solved by Harary. We show that, if \(m < \lceil \frac{3n}{2} \rceil\) or \(m \geq n(\lfloor \frac{n}{6} \rfloor + \lfloor \frac{n \mod 6}{3} \rfloor)\), then the maximum toughness is half of the maximum connectivity. The same conclusion is obtained if \(r = \lfloor \frac{2m}{n} \rfloor \geq 1\) and \(\frac{(n-1)(r+1)}{2} \leq m < \frac{n(r+1)}{2}\). However, maximum toughness can be strictly less than half of maximum connectivity. Some values of maximum toughness are computed for \(1 \leq n \leq 12\), and some open problems are presented

We describe a random variable \(\text{D}_\text{{n,m}}\), \(\text{n} \geq \text{m} \geq 1\), as the number of failures until the first success in a sequence of n Bernoulli trials containing exactly m successes, for which all possible sequences containing m successes and n-m failures are equally likely. We give the probability density function, the expectation, and the variance of \(\text{D}_\text{{n,m}}\). We define a random variable \(\text{D}_\text{n}\), \(\text{n} \geq 1\), to be the mean of \(\text{D}_\text{n,1}, \ldots, \text{D}_\text{n,n}\). We show that E\([\text{D}_\text{n}]\) is a monotonically increasing function of n and is bounded by \(\ln\) n. We apply these results to a practical application involving a video-on-demand system with interleaved movie files and a delayed start protocol for keeping a balanced workload.

The exact values of \(c(n)\) are determined, where \(c(n)\) denotes the largest \(k\) for which there exists a triangle-free \(k\)-regular graph on \(n\) vertices containing a cut-vertex. As a corollary, we obtain a lower bound on the densest triangle-free regular graphs of given order that do not have a one-factorization.

In the search for doubly resolvable Kirkman triple systems of order \(v\), systems admitting an automorphism of order \((v-3)/3\) fixing three elements, and acting on the remaining elements in three orbits of length \((v-3)/3\), have been of particular interest. We have established by computer that 100 such Kirkman triple systems exist for \(v=21\), 90,598 for \(v=27\), at least 4,494,390 for \(v=33\), and at least 1,626,684 for \(v=39\). This improves substantially on known lower bounds for numbers of Kirkman triple systems. We also establish that the KTS(27)s so produced yield 47 nonisomorphic doubly resolved KTS(27)s admitting the same automorphism.

Let \(r(a)\) be the replication number of the vertex \(a\) of a path design \(P(v,k, 1)\), \(k \geq 3\). Let \(\bar{r}(v,k) = \text{min}\{\text{max}_{a\in V} \,r(a) | (V,\mathcal{B}) \text{ is a } P(v,k, 1)\}\). A path design \(P(v,k,1)\), \((W,\mathcal{D})\), is said to be \({almost\; balanced}\) if \(\bar{r}(v,k) – 1 \leq r(y) \leq \bar{r}(v,k)\) for each \(y \in W\). Let \(v \equiv 0 \text{ or } 1 \pmod{2(k-1)}\) (for each odd \(k\), \(k \geq 3\)) and let \(v_y \equiv 0 \text{ or } 1 \pmod{k-1}\) (for each even \(k\), \(k \geq 4\)). In this note, we determine the spectrum \(\mathcal{B}\mathcal{S}\mathcal{A}\mathcal{B}\mathcal{P}(v,k,1)\) of integers \(x\) such that there exists an almost balanced path design \(P(v,k, 1)\) with a blocking set of cardinality \(x\).

A border of a string \(x\) is a proper (but possibly empty) prefix of \(x\) that is also a suffix of \(x\). The \({border \;array}\) \(\beta = \beta[1..n]\) of a string \(x = x[1..n]\) is an array of nonnegative integers in which each element \(\beta(i)\), \(1 \leq i \leq n\), is the length of the longest border of \(x[1..i]\). In this paper, we first present a simple linear-time algorithm to determine whether or not a given array \(y = y[1..n]\) of integers is a border array of some string on an alphabet of unbounded size, and then a slightly more complex linear-time algorithm for an alphabet of any given (bounded) size \(\alpha\). We then consider the problem of generating all possible distinct border arrays of given length \(n\) on a bounded or unbounded alphabet, and doing so in time proportional to the number of arrays generated. A previously published algorithm that claims to solve this problem in constant time per array generated is shown to be incorrect, and new algorithms are proposed. We conclude with an equally efficient on-line algorithm for this problem.

In developing an observation made by the author concerning a class of expansions of the sine function, M. Xinrong has recently analysed the question of a generalised form through a succinct use of linear operator theory. This paper constitutes an extension of his work, in which the current problem is solved completely by examining the generating function of a finite sequence central to the formulation.

For graphs \(G\) and \(H\), the Ramsey number \(R(G, H)\) is the least integer \(n\) such that every 2-coloring of the edges of \(K_n\) contains a subgraph isomorphic to \(G\) in the first color or a subgraph isomorphic to \(H\) in the second color. Graph \(G\) is a \((C_4, K_n)\)-graph if \(G\) doesn’t contain a cycle \(C_4\) and \(G\) has no independent set of order \(n\). Jayawardene and Rousseau showed that \(21 \leq R(C_4, K_7) \leq 22\). In this work, we determine \(R(C_4, K_7) = 22\) and \(R(C_4, K_8) = 26\), and enumerate various families of \((C_4, K_n)\)-graphs. In particular, we construct all \((C_4, K_n)\)-graphs for \(n < 7\), and all \((C_4, K_n)\)-graphs on at least 19 vertices. Most of the results are based on computer algorithms.

For \(\text{k}>0\), we call a graph G=(V,E) as \(\underline{\text{Z}_\text{k}-magic}\) if there exists an edge labeling \(\text{I: E(G)} \rightarrow \text{Z}_\text{k}^*\) such that the induced vertex set labeling \(\text{I}^+: \text{V(G)} \rightarrow \text{Z}_\text{k}\) defined by

\[\text{I}^+(\text{v}) = \Sigma \{(\text{I(u,v)) : (u,v)} \in \text{E(G)}\}\]

is a constant map. We denote the set of all \(k\) such that \(G\) is \(k\)-magic by \(IM(G)\). We call this set as the \(\textbf{integer-magic spectrum}\) of \(G\). This paper deals with determining the integer-magic spectra of powers of paths \(\text{P}\text{n}^\text{k}\) for \(k=2\) and \(3\). We also show that IM(\(\text{P}_{2\text{k}}^\text{k}) = \text{N}\setminus\{2\}\) for all odd integers \(\text{k}>1\). Finally, a conjecture for \(IM\)\((\text{P}_\text{n}^\text{k})\) for \(\text{k}\geq4\) is proposed.

A new graph labeling problem on simple graphs called edge-balanced labeling is introduced by Kong and Lee [11]. They conjectured that all trees except \(K_{1,n}\) where \(n\) is odd, and all connected regular graphs except \(K_2\) are edge-balanced. In this paper, we extend the concept of edge-balanced labeling to multigraphs and completely characterize the edge-balanced multigraphs. Thus, we proved that the above two conjectures are true. A byproduct of this result is a proof that the problem of deciding whether a graph is edge-balanced does not belong to NP-hard.