Let \(\delta_k\) denote the minimum degree of the \(k^{th}\)-iterated line graph \(L^k(G)\). For any connected graph \(G\) that is not a path, the inequality \(\delta_k \geq 2\delta_k – 2\) holds. Niepel, Knor, and Soltés [5] have conjectured that there exists an integer \(K\) such that, for all \(k \geq K\), equality holds; that is, the minimum degree \(\delta_k\) attains the least possible growth. We prove this conjecture by extending the methods we used in [2] for a similar conjecture about the maximum degree.

A set of Knights covers a board if a Knight attacks every unoccupied square. What is the minimum number of Knights in a cover of an \(n\times n\) board? For \(n \leq 10\), we give a non-computational proof that the widely accepted answers are correct. For \(n \leq 14\), fractional Knight packings are used in an exhaustive branch-and-bound program. This gives the first enumeration of minimum Knight covers for \(11 \leq n \leq 14\). For \(n \geq 15\), integer programs are used to find small (though not necessarily minimum) symmetric covers. This yields smaller covers for \(16 \leq n \leq 19\), and new covers when \(21 \leq n \leq 25\). Simulated annealing discovered yet smaller covers for \(n = 19\) and \(n = 21\). Guess work improved the results for \(n = 20\) and \(n = 25\).

It has been shown that if \(G = (V, E)\) is a simple graph with \(n\) vertices, \(m\) edges, an average (per edge) of \(t\) triangles occurring on the edges, and \(J = \max_{uv \in E} |N(u) \cup N(v)|\), then \(4m \leq n(J+t)\). The extremal graphs for this inequality for \(J = n\) and \(J = n – 1\) have been determined. For \(J = n\), the extremal graphs are the Turán graphs with parts of equal size; notice that these are the complements of the strongly regular graphs with \(\mu = 0\). For \(J = n-1\), the extremal graphs are the complements of the strongly regular graphs with \(\mu = 1\). (The only such graphs known to exist are the Moore graphs of diameter \(2\)).

For \(J = n-2\) and \(t = 0\), it has recently been shown that the only extremal graph (except when \(n = 8, 10\)) is \(K_{n/2,n/2} – (1\text{-factor})\). Here, we use a well-known theorem of Andrásfai, Erdős, and Sós to characterize the extremal graphs for \(t = 0\), any given value of \(n-J\), and \(n\) sufficiently large (they are the regular bipartite graphs). Then we give some examples of extremal non-bipartite graphs for smaller values of \(n\).

Let \(G = (V, E)\) be a graph. Let \(\Phi: V \to {R}\), where \({R}\) is the set of all reals (\({R}\) can be replaced by any chain). We say that \(u\) \(\Phi\)-strongly dominates \(v\) and \(v\) \(\Phi\)-weakly dominates \(u\) if \(uv \in E\) and \(\Phi(u) \geq \Phi(v)\). When \(\Phi\) is a constant function, we have the usual domination and when \(\Phi\) is the degree function of the graph, we have the strong (weak) domination studied by Sampathkumar et al. In this paper, we extend the results of O. Ore regarding minimal dominating sets of a graph. We also extend the concept of fully domination balance introduced by Sampathkumar et al and obtain a lower bound for strong domination number of a graph.

A function \(f: V \to \{-1, 1\}\) defined on the vertices of a graph \(G = (V, E)\) is a signed \(2\)-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every \(v \in V\), \(f(N[v]) \leq 1\), where \(N[v]\) consists of \(v\) and every vertex adjacent to \(v\). The weight of a signed \(2\)-independence function is \(f(V) = \sum f(v)\). The signed \(2\)-independence number of a graph \(G\), denoted \(\alpha^2_s(G)\), is the maximum weight of a signed \(2\)-independence function of \(G\). In this article, we give some new upper bounds on \(\alpha^2_s(G)\) of \(G\), and establish a sharp upper bound on \(\alpha^2_s(G)\) for an \(r\)-partite graph.

Let \(G\) be a graph with a perfect matching \(M_0\). It is proved that \(G\) is \(1\)-extendable if and only if for any pair of vertices \(x\) and \(y\) with an \(M_0\)-alternating path \(P_y\) of length three which starts with an edge that belongs to \(M_0\), there exists an \(M_0\)-alternating path \(P\) connecting \(x\) and \(y\), of which the starting and the ending edges do not belong to \(M_0\). With this theorem, we develop a polynomial algorithm that determines whether the input graph \(G\) is \(1\)-extendable, the time complexity of the algorithm is \(O(|E|^2)\).

Let \(G\) be a graph on \(p\) vertices and denote by \(L(G) = D(G) – A(G)\) the difference between the diagonal matrix of vertex degrees and the adjacency matrix. It is not difficult to see that \(L(G)\) is positive semidefinite symmetric and its second smallest eigenvalue, \(a(G) > 0\), if and only if \(G\) is connected. This observation led M. Fiedler to call \(a(G)\) the algebraic connectivity of \(G\).

The algebraic connectivity of the line graph, the middle graph, and the total graph of a regular graph are given.

The minimum number of incomplete blocks required to cover, exactly \(A\) times, all \(t\)-element subsets from a set \(V\) of cardinality \(v\) (\(v \geq t\)) is denoted by \(g(\lambda,t;v)\). The value of \(g(2,2;v)\) is known for \(v = 3, 4, \ldots, 11\). It was previously known that \(14 \leq g(2, 2; 12) \leq 16\). We prove that \(g(2,2;12) \geq 15\).

A computer program for finding knight coverings of a chessboard is described, and some improved coverings for boards of sizes \(16\times 16\) through \(25\times 25\) are shown.

Let \(G\) be a graph and \(d, d’\) be positive integers, \(d’ \geq d\). An \(m\)-\((d, d’)\)-circular distance two labeling is a function \(f\) from \(V(G)\) to \(\{0, 1, 2, \ldots, m-1\}\) such that:\(|f(u) – f(v)|_m \geq d\) if \(u\) and \(v\) are adjacent; and \(|f(u) – f(v)|_m \geq d’\) if \(u\) and \(v\) are distance two apart, where \(|x|_m := \min\{|x|, m – |x|\}\) .The minimum \(m\) such that there exists an \(m\)-\((d, d’)\)-circular labeling for \(G\) is called the \(\sigma_{d, d’}\)-number of \(G\) and denoted by \(\sigma_{d, d’}(G)\). The \(\sigma_{d, d’}\)-numbers for trees can be obtained by a first-fit algorithm. In this article, we completely determine the \(\sigma_{d, 1}\)-numbers for cycles. In addition, we show connections between generalized circular distance labeling and circular chromatic number.