We consider two possible methods of embedding a (simple undirected) graph into a uniquely vertex colourable graph. The first method considered is to build a \(K\)-chromatic uniquely vertex colourable graph from a \(k\)-chromatic graph \(G\) on \(G\cup K_k\), by adding a set of new edges between the two components. This gives rise to a new parameter called fixing number (Daneshgar (1997)). Our main result in this direction is to prove that a graph is uniquely vertex colourable if and only if its fixing number is equal to zero (which is a counterpart to the same kind of result for defining numbers proved by Hajiabolhassan et al. (1996)).

In our second approach, we try a more subtle method of embedding which gives rise to the parameters \(t_r\)-fixer and \(\tau_r\)-index (\(r = 0, 1\)) for graphs. In this approach we show the existence of certain classes of \(u\)-cores, for which, the existence of an extremal graph provides a counter example for Xu’s conjecture.

Necessary and sufficient conditions are given for a Steiner triple system of order \(t\) admitting an automorphism consisting of one large cycle, cycles of length \(8\), and a fixed point, with \(t \leq 4\). Necessary conditions are given for all \(t \geq 1\).

In this note we prove that the bipartite Ramsey number for \(K_{2,n}\) with \(q\) colors does not exceed \((n-1)q^2+q+1-\left\lceil\sqrt{q}\right\rceil\), improving the previous upper bound by \(\left\lceil\sqrt{q}\right\rceil-2\).

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.

The inventory of a \(2 \times m\) array \(A = A(i,j)\) consisting of \(n\) not necessarily distinct positive integers \(\mathbb{I}(2,j)\) is the \(2 \times n\) array \(\mathbb{I}(A) = \mathbb{I}(i,j)\), where \(\mathbb{I}(i,j)\) is the number of occurrences of \(\mathbb{I}(1,j)\) in \(A\). Define \(\mathbb{I}^q(A) = I(\mathbb{I}^{q-1}(A))\) for \(q \geq 1\), with \(\mathbb{I}^0(A) = A\). For every \(A\), the chain \(\{\mathbb{I}^q(A)\}\) of inventories is eventually periodic, with period \(1, 2\), or \(3\). The proof depends on runlengths of partitions of integers. A final section is devoted to an open question about cumulative inventory chains.

A decomposition \(\mathcal{F} = \{F_1, \ldots, F_r\}\) of the edge set of a graph \(G\) is called a resolving \(r\)-decomposition if for any pair of edges \(e_1\) and \(e_2\), there exists an index \(i\) such that \(d(e_1, F_i) \neq d(e_2, F_i)\), where \(d(e, F)\) denotes the distance from \(e\) to \(F\). The decomposition dimension \(dec(G)\) of a graph \(G\) is the least integer \(r\) such that there exists a resolving \(r\)-decomposition. Let \(K_n\) be the complete graph with \(n\) vertices. It is proved that \(dec(K_n) \leq \frac{1}{2} (\log_2 n)^2 (1 + o(1)).\)

For a vertex \(v\) of a graph \(G = (V, E)\), the lower independence number \(i_v(G)\) of \(G\) relative to \(v\) is the minimum cardinality of a maximal independent set in \(G\) that contains \(v\). The average lower independence number of \(G\) is \(i_{av}(G) = \frac{1}{|V|} \sum_{v\in V} i_v(G)\). In this paper, we show that if \(G\) is a tree of order \(n\), then \(i_{av}(G) \geq {2}\sqrt{n} + O(1)\), while if \(G\) is an outer-planar graph of order \(n\), then \(i_{av}(G) \geq 2\sqrt{\frac{n}{3}} + O(1)\). Both bounds are asymptotically sharp.

We consider the partition function \(b’_p(n)\), which counts the number of partitions of the integer \(n\) into distinct parts with no part divisible by the prime \(p\). We prove the following: Let \(p\) be a prime greater than \(3\) and let \(r\) be an integer between \(1\) and \(p-1\), inclusively, such that \(24r+1\) is a quadratic nonresidue modulo \(p\). Then, for all nonnegative integers \(n\), \(b’_p{(pn+r)} \equiv 0 \pmod{2}.\)

We show that:(a) the special product of two cycles is Hamiltonian decomposable, and (b) if \(G_1\) and \(G_2\) are two Hamiltonian decomposable graphs and at least one of their complements is Hamiltonian decomposable, then the special product of \(G_1\) and \(G_2\) is Hamiltonian decomposable.

A vertex-magic total labeling on a graph \(G\) is a one-to-one map \(\lambda\) from \(V(G) \cup E(G)\) onto the integers \(1, 2, \ldots, |V(G) \cup E(G)|\) with the property that, given any vertex \(x\), \(\lambda(x) + \sum_{y \sim x} \lambda(y) = k\) for some constant \(k\).

In this paper, we completely determine which complete bipartite graphs have vertex-magic total labelings.

In this paper, the notions of \(c\)-Motzkin and \(d\)-Motzkin words are introduced, studied, and the cardinal numbers of their sets are evaluated. Finally, bijections between the sets of the introduced Motzkin words and certain sets of noncrossing partitions are exhibited.

Vizing conjectured that \(\gamma(G)\gamma(H) \leq \gamma(G \Box H)\) for all graphs \(G\) and \(H\), where \(\gamma(G)\) denotes the domination number of \(G\) and \(G \Box H\) is the Cartesian product of \(G\) and \(H\). We prove that if \(G\) and \(H\) are \(\delta\)-regular, then, with only a few possible exceptions, Vizing’s conjecture holds. We also prove that if \(\delta(G), \Delta(G), \delta(H)\), and \(\Delta(H)\) are in a certain range, then Vizing’s conjecture holds. In particular, we show that for graphs of order at most \(n\) with minimum degrees at least \(\sqrt{n} \ln n\), the conjecture holds.

The classification of Hadamard matrices of orders \(n \geq 32\) remains an open and difficult problem. The definition of equivalent Hadamard matrices gets increasingly complex as \(n\) grows larger. One efficient criterion (\(K\)-boxes) has been used for the construction of inequivalent Hadamard matrices in order \(28\).

In this paper, we use inequivalent projections of Hadamard matrices and their symmetric Hamming distances to check for inequivalent Hadamard matrices. Using this criterion, we have developed two algorithms. The first one achieves finding all inequivalent projections in \(k\) columns as well as classifying Hadamard matrices, and the second, which is faster than the first, uses the symmetric Hamming distance distribution of projections to classify Hadamard matrices. As an example, we apply the second algorithm to the known inequivalent Hadamard matrices of orders \(n = 4, 8, 12, 16, 20, 24\), and \(28\).

A composition of a positive integer \(n\) consists of an ordered sequence of positive integers whose sum is \(n\). A palindromic composition is one for which the sequence is the same from left to right as from right to left. This paper shows various ways of generating all palindromic compositions, counts the number of times each integer appears as a summand among all the palindromic compositions of \(n\), and describes several patterns among the numbers generated in the process of enumeration.

The study of the maximum size \(ex(n; K_{t,t})\) of a graph of order \(n\) not containing the complete bipartite graph \(K_{t,t}\) as a subgraph is the aim of this paper. We show an upper bound for this extremal function that is optimum for infinitely many values of \(n\) and \(t\). Moreover, we characterize the corresponding family of extremal graphs.

In this paper we extend the work of Bogart and Trenk [3] and Fishburn and Trotter [6] in studying different classes of bitolerance orders. We provide a more comprehensive list of classes of bitolerance orders and prove equality between some of these classes in general and other classes in the bipartite domain. We also provide separating examples between unequal classes of bitolerance orders.

We consider non-crossing trees and show that the height of node \(\rho n\) with \(0 < p < 1\) in a non-crossing tree of size \(n\) is asymptotically Maxwell-distributed. We also give an asymptotic formula for the expected height of node \(\rho n\).

Let \(G = (V(G), E(G))\) be a finite simple graph with \(p\) vertices and \(n\) edges. A labeling of \(G\) is an injection \(f: V(G) \to {Z}_n\). A labeling of \(G\) is called \(2\)-sequential if \(f(V(G)) = \{r, r+1, \ldots, r+p-1\}\) (\(0 \leq r <r+ p-1 \leq n-1\)) and the induced edge labeling \(f^*: E(G) \to \{0, 1, \ldots, n-1\}\) given by \[f^*(u,v) = f(u) + f(v), \quad \text{for every edge } (u,v) \] forms a sequence of distinct consecutive integers \(\{k, k+1, \ldots, n+k-1\}\) for some \(k\) (\(1 \leq k \leq n-2\)). By utilizing the graphs having \(2\)-sequential labeling, several new families of sequential graphs are presented.

A cycle \(C\) in a graph \(G\) is said to be a dominating cycle if every vertex of \(G\) has a neighbor on \(C\). Strengthening a result of Bondy and Fan [3] for tough graphs, we prove that a \(k\)-connected graph \(G\) (\(k \geq 2\)) of order \(p\) with \(t(G) > \frac{k}{k+1}\) has a dominating cycle if \(\sum_{x \in S} \geq p – 2k – 2\) for each \(S \subset V(G)\) of order \(k+1\) in which every pair of vertices in \(S\) have distance at least four in \(G\).