Given a graph, a no-hole \(2\)-distant coloring (also called \(N\)-coloring) is a function \(f\) that assigns to each vertex a non-negative integer (color) such that the separation of the colors of any pair of adjacent vertices must be at least \(2\), and all the colors used by \(f\) form a consecutive set (the no-hole assumption). The minimum consecutive \(N\)-span of \(G\), \(csp(G)\), is the minimum difference of the largest and the smallest colors used in an \(N\)-coloring of \(G\), if there exists such a coloring; otherwise, define \(csp(G) = \infty\). Here we investigate the exact values of \(csp(G)\) for unit interval graphs (also known as \(1\)-unit sphere graphs). Earlier results by Roberts [18] indicate that if \(G\) is a unit interval graph on \(n\) vertices, then \(csp_1(G)\) is either \(2\chi(G) – 1\) or \(2\chi(G) – 2\), if \(n > 2\chi(G) – 1\); \(csp_1(G) = \infty\), if \(n < 2\chi(G) – 1\), where \(\chi(G)\) denotes the chromatic number. We show that in the former case (when \(n > 2\chi(G) – 1\)), both values of \(csp_1(G)\) are attained, and give several families of unit interval graphs such that \(csp_1(G) = 2\chi(G) – 2\). In addition, the exact values of \(csp_1(G)\) are completely determined for unit interval graphs with \(\chi(G) = 3\).

Let \(G\) be a graph. Let \(\gamma\) denote the minimum cardinality of a dominating set in \(G\). Let \(\beta\), respectively \(i\), denote the maximum, respectively minimum, cardinality of a maximal independent set in \(G\). We show \(\gamma + \Delta \geq \left\lceil {2\sqrt{n}-1} \right\rceil\), where \(n\) is the number of vertices of \(G\). A straightforward construction shows that given any \(G’\) there exists a graph \(G\) such that \(\gamma(G) + \Delta(G) = \left\lceil {2\sqrt{n}-1} \right\rceil\) and \(G’\) is an induced subgraph of \(G\), making classification of these \(\gamma+\Delta\) minimum graphs difficult.

We then focus on the subclass of these graphs with the stronger condition that \(\beta + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\). For such graphs \(i = \beta\) and thus the graphs are well-covered. If \(G\) is a graph with \(\beta + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\), we have \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). We give a catalogue of all well-covered graphs with \(\Delta \leq 3\) and \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). Again we establish that given any \(G’\) we can construct \(G\) such that \(G’\) is an induced subgraph of \(G\) and \(G\) satisfies \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). In fact, the graph \(G\) can be constructed so that \(\beta(G) + \Delta(G) = \left\lceil {2\sqrt{n}-1} \right\rceil\). We remark that \(\Delta(G)\) may be much larger than \(\Delta(G’)\).

We conclude the paper by analyzing integer solutions to \(\left\lceil \frac{n}{\Delta+1} \right\rceil + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\). In particular, for each \(n\), the values of \(\Delta\) that satisfy the equation form an interval. When \(n\) is a perfect square, this interval contains only one value, namely \(\sqrt{n}\). For each \((n, \Delta)\) solution to the equation, there exists a graph \(G\) with \(n\) vertices, maximum degree \(\Delta\), and \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\).

We construct a family of \(p-1\) square \(p \times p\) matrices (\(p\) is any prime) whose periodic cross-correlation values are uniformly \(-p, 0, +p\) between all pairs of the matrices in the family. For every one of the matrices in the family, all the off-peak autocorrelation values are \(-p\) and \(0\), while the single peak value is \(p(p-1)\). For \(p = 127\) (where the values \(-p, 0, +p\) are below \(1\%\) of the size \(p^2\) of the matrices) utilization of this construction has resulted in the superimposed embedding of twelve of the matrices (as watermarks) in the standard image “Lenna” and their subsequent retrieval without recourse to the unmarked image.

Let \(D\) be a connected symmetric digraph, \(\Gamma\) a group of automorphisms of \(D\), and \(A\) a finite abelian group with some specified property. We discuss the number of isomorphism classes of \(g\)-cyclic \(A\)-covers of \(D\) with respect to a group \(\Gamma\) of automorphisms of \(D\). Furthermore, we enumerate the number of \(I\)-isomorphism classes of \(g\)-cyclic \(\mathbb{Z}_{2^m}\)-covers of \(D\) for the cyclic group \(\mathbb{Z}_{2^m}\) of order \(2^m\), where \(I\) is the trivial subgroup of \(Aut(D)\).

We characterize tough-maximum graphs, that is, graphs having maximum number of edges among all graphs with given number of vertices and toughness.

The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as

\[t(G) = \min \left\{ \frac{|S|}{\omega(G – S)} \mid S \subset V(G), \omega(G – S) \geq 2 \right\},\]

where \(\omega(G – S)\) is the number of components of \(G – S\). We also define \(t(K_n) = +\infty\) for every \(n\).

The total graph \(T(G)\) of a graph \(G\) is the graph whose vertex set can be put in one-to-one correspondence with the set \(V(G) \cup E(G)\) such that two vertices of \(T(G)\) are adjacent if and only if the corresponding elements of \(G\) are adjacent or incident.

In this article, we study the toughness of the total graph \(T(G)\) of a graph \(G\) on at least \(3\) vertices and give especially that \(t(T(G)) = t(G)\) if \(\kappa(G) = \lambda(G)\) and \(\kappa(G) \leq 2\), where \(\kappa(G)\) and \(\lambda(G)\) are the vertex and the edge-connectivity of \(G\), respectively.

We shall consider a problem of finding an ‘optimum’ tree which is closely related to the network flow problem proposed by Ford and Fulkerson, and call the solution to this problem a lexicographically optimum traffic tree (LOTT). Before examining this problem in detail, we shall review the problem of finding an optimum requirement spanning tree (ORST) studied by Hu, which is also related to the network flow problem. We can regard the LOTT problem as a min-max problem and the ORST problem as a min-sum problem. It shall be shown that, while LOTTs and ORSTs coincide completely without maximum degree constraints, they do not always coincide with the constraints. Further, we shall show that LOTTs can be expressed by simple recursion in a special case.

It is well known that some graph-theoretic extremal questions play a significant role in the investigation of communication network vulnerability. Answering questions concerning the realizability of graph invariants also solves several of these extremal problems. We define a \((p, q, \kappa, \Delta)\) graph as a graph having \(p\) points, \(q\) lines, point connectivity \(\kappa\) and maximum degree \(\Delta\). An arbitrary quadruple of integers \((a, b, c, d)\) is called \((p, q, \kappa, \Delta)\) realizable if there is a \((p, q, \kappa, \Delta)\) graph with \(p = a, q = b, \kappa = c\) and \(\Delta = d\). Necessary and sufficient conditions for a quadruple to be \((p, q, \kappa, \Delta)\) realizable are derived. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability, where \(\lambda\) denotes the line connectivity of a graph and \(\delta\) denotes the minimum degree for all points in a graph.

We introduce the concept of a free \(a\)-valuation of a graph, and prove that the vertex-disjoint union of any collection of graphs with free \(\alpha\)-valuations has an \(\alpha\)-valuation. Many bipartite graphs have free \(\alpha\)-valuations, including the complete bipartite graph \(K_{m,n}\) when \(m > 1\) and \(n > 2\), and the \(d\)-cube \(Q_d\) for \(d > 2\).

Let \(G\) be a \(2\)-connected simple graph with order \(n\) (\(n \geq 5\)) and minimum degree \(5\). This paper proves that if for any two vertices \(u,v\) of \(G\) at distance two there holds \(|N(u) \bigcup N(v)| \geq n – \delta\), then \(G\) is vertex-pancyclic with a few exceptions.