Every labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge \(ae\) is the absolute value of the difference of the labels of \(a\) and \(e\). A labeling of the vertices of a graph of order \(p\) is minimally \(k\)-equitable if the vertices are labeled with elements of \({1,2, \ldots, p}\) and in the induced labeling of its edges, every label either occurs exactly \(k\) times or does not occur at all. We prove that the corona graph \(C_{2n}OK_1\) is minimally \(4\)-equitable.

A set of Bishops cover a board if they attack all unoccupied squares. What is the minimum number of Bishops needed to cover an \(k \times n\) board \(?\) Yaglom and Yaglom showed that if \(k = n\), the answer is \(n\). We extend this result by showing that the minimum is \(2\lfloor \frac{n}{2}\rfloor\) if \(k 2k > 2\), a cover is given with \(2\lfloor\frac{k+n}{2}\rfloor\) Bishops. We conjecture that this is the minimum value. This conjecture is verified when \(k \leq 3\) or \(n \leq 2k + 5\).

It is proved that the following graphs are harmonious:(1) shell graphs (2) cycles with the maximum possible number of concurrent alternate chords (3) Some families of multiple shells

In this paper, we determine all harmonious graphs of order \(6\).
All graphs in this paper are finite, simple and undirected. We shall use the basic notation and terminology of graph theory as in [1].

Let \(R(n)\) denote the number of two-color partitions of \(n\). We obtain several identities concerning \(R(n)\).

We show that if \(M(n, m)\) denotes the time of a \((u, v)\)-minimum cut computation in a directed graph with \(n \geq 2\) nodes, \(m\) edges, and \(s\) and \(t\) are two distinct given nodes, then there exists an algorithm with \(O(n^2m+n\cdot M(n, m))\) running time for the directed minimum odd (or even) \((s, t)\)-cut problem and for its certain generalizations.

Basic properties of in-degree distribution of a general model of random digraphs \(D(n, \mathcal{P})\) are presented. Then some relations between random digraphs \(D(n, \mathcal{P})\) for different probability distributions \(\mathcal{P}\)’s are studied. In this context, a problem of the existence of a threshold function for every monotone digraph property of \(D(n, \mathcal{P})\) is discussed.

For a given structure (graph, multigraph, or pseudograph) \(G\) and an integer \(r \geq \Delta(G)\), a smallest inducing \(r\)-regularization of \(G\) (which is an \(r\)-regular superstructure of the smallest possible order, with bounded edge multiplicities, and containing \(G\) as an induced substructure) is constructed.

It is an established fact that some graph-theoretic extremal questions play an important part in the investigation of communication network vulnerability. Questions concerning the realizability of graph invariants are generalizations of these extremal problems. We define a \((p, q, \lambda, \delta)\) graph as a graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). An arbitrary quadruple of integers \((a, b, c, d)\) is called \((p, q, \lambda, \delta)\) realizable if there is a \((p, q, \lambda, \delta)\) graph with \(p = a, q = b, \lambda = c\), and \(\delta = d\). Inequalities representing necessary and sufficient conditions for a quadruple to be \((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta), (p, q, \lambda, \Delta), (p, q, \delta, \Delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\lambda\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa), (p, q, \lambda), (p, q, \delta), (p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.

An aperiodic perfect map (APM) is an array with the property that each possible array of certain size, called a window, arises exactly once as a subarray in the array. In this article, we give some constructions which imply a complete answer for the existence of APMs with \(2 \times 2\) windows for any alphabet size.