The paper contains two main results. First, we obtain the chromatic polynomial on the \(n \times m\) section of the square lattice, solving a problem proposed by Read and Tutte \([5]\), the chromatic polynomial of the bracelet square lattice, and we find a recurrent-constructive process for the matrices of the \(k\)-colourings. The key concept for obtaining the inductive method is the compatible matrix.

Our second main result deals with the compatible matrix as the adjacency matrix of a graph. This represents a family of graphs, which is described.

Let \(G = (V, E)\) be a simple graph. For any real valued function \(f: V \to \mathbb{R}\), the weight of \(f\) is defined as \(f(V) = \sum f(v)\), over all vertices \(v \in V\). For positive integer \(k\), a total \(k\)-subdominating function (TkSF) is a function \(f: V \to \{-1,1\}\) such that \(f(N(v)) \geq k\) for at least \(k\) vertices \(v\) of \(G\). The total \(k\)-subdomination number \(\gamma^t_{ks}(G)\) of a graph \(G\) equals the minimum weight of a TKSF on \(G\). In the special case where \(k = |V|\), \(\gamma^t_{ks}(G)\) is the signed total domination number \([5]\). We research total \(k\)-subdomination numbers of some graphs and obtain a few lower bounds of \(\gamma^t_{ks}(G)\).

A convex hull of a set of points \(X\) is the minimal convex set containing \(X\). A box \(B\) is an interval \(B = \{x | x \in [a,b], a,b \in \mathbb{R}^n\}\). A box hull of a set of points \(X\) is defined to be the minimal box containing \(X\). Because both convex hulls and box hulls are closure operations of points, classical results for convex sets can naturally be extended for box hulls. We consider here the extensions of theorems by Carathéodory, Helly, and Radon to box hulls and obtain exact results.

The point-distinguishing chromatic index of a graph \(G = (V, E)\) is the smallest number of colors assigned to \(E\) so that no two different points are incident with the same color set. In this paper, we discuss the bounds of the point-distinguishing chromatic indices of graphs resulting from the graph operations. We emphasize that almost all of these bounds are best possible.

If \(G\) is a bipartite graph with bipartition \((X,Y)\), a subset \(S\) of \(X\) is called a one-sided dominating set if every vertex \(y \in Y\) is adjacent to some \(x \in S\). If \(S\) is minimal as a one-sided dominating set (i.e., if it has no proper subset which is also a one-sided dominating set), it is called a bipartite dominating set (see \([4], [5]\), and \([6]\)). We study bipartite dominating sets in hypercubes.

Let \(u,v\) be distinct vertices of a multigraph \(G\) with degrees \(d_u\) and \(d_v\), respectively. The number of edge-disjoint \(u,v\)-paths in \(G\) is bounded above by \(\min\{d_u,d_v\}\). A multigraph \(G\) is optimally edge-connected if for all pairs of distinct vertices \(u\) and \(v\) this upper bound is achieved. If \(G\) is a multigraph with degree sequence \(D\), then we say \(G\) is a realisation of \(D\). We characterise degree sequences of multigraphs that have an optimally edge-connected realisation as well as those for which every realisation is optimally edge-connected.

The \(associated \;graph \;of\; a\) \((0,1)\)-\(matrix\) has as its vertex set the lines of the matrix with vertices adjacent whenever their lines intersect at \(a\) \(1\). This association relates the \((0,1)\)-matrix and bipartite graph versions of the König-Egervary Theorem. We extend this graph association to higher dimensional matrices. We characterize these graphs, modulo isolated vertices, using a coloring in which every path between each pair of vertices contains the same two colors. We rely on previous results about \(p\)-dimensional gridline graphs, where vertices are \(1\)’s in a higher dimensional matrix and vertices are adjacent whenever they are on a common line. Also important is the dual property that the doubly iterated clique graph of a diamond- and simplicial vertex-free graph is isomorphic to the original.

Since Cohen introduced the notion of competition graph in \(1968\), various variations have been defined and studied by many authors. Using the combinatorial properties of the adjacency matrices of digraphs, Cho \(et\; al\). \([2]\) introduced the notion of a \(m\)-step competition graph as a generalization of the notion of a competition graph. Then they \([3]\) computed the \(2\)-step competition numbers of complete graphs, cycles, and paths. However, it seems difficult to compute the \(2\)-step competition numbers even for the trees whose competition numbers can easily be computed. Cho \(et\; al\). \([1]\) gave a sufficient condition for a tree to have the \(2\)-step competition number two. In this paper, we show that this sufficient condition is also a necessary condition for a tree to have the \(2\)-step competition number two, which completely characterizes the trees whose \(2\)-step competition numbers are two. In fact, this result turns out to characterize the connected triangle-free graphs whose \(2\)-step competition numbers are two.

In this paper, we are interested in lexicographic codes which are greedily constructed codes. For an arbitrary length \(n\), we shall find the basis of quaternary lexicographic codes, for short, lexicodes, with minimum distance \(d_m = 4\). Also, using a linear nim sum of some bases (such a vector is called the testing vector), its decoding algorithm will be found.

A maximal-clique partition of a graph is a family of its maximal complete sub-graphs that partitions its edge set. Many graphs do not have a maximal-clique partition, while some graphs have more than one. It is harder to find graphs in which maximal-clique partitions have different sizes. \(L(K_5)\) is a well-known example. In \(1982\), Pullman, Shank, and Wallis \([9]\) asked if there is a graph with fewer vertices than \(L(K_5)\) with this property. This paper confirms that there is no such graph.