Let \(G\) be a simple graph with vertex set \(V\) and edge set \(E\). A vertex labeling \(f: V \to \{0,1\}\) induces an edge labeling \(\overline{f}: E \to \{0,1\}\) defined by \(\overline{f}(uv) = |f(u) – f(v)|\). Let \(v_f(0), v_f(1)\) denote the number of vertices \(v\) with \(f(v) = 0\) and \(f(v) = 1\) respectively. Let \(e_f(0), e_f(1)\) be similarly defined. A graph is said to be cordial if there exists a vertex labeling \(f\) such that \(|v_f(0) – v_f(1)| \leq 1\) and \(|e_f(0) – e_f(1)| \leq 1\).

In this paper, we give necessary and sufficient conditions for the cordiality of the \(t\)-ply \(P_t(u,v)\), i.e. a thread of ply number \(t\).

A Jacobi polynomial was introduced by Ozeki. It corresponds to the codes over \(\mathbb{F}_2\). Later, Bannai and Ozeki showed how to construct Jacobi forms with various index using a Jacobi polynomial corresponding to the binary codes. It generalizes Broué-Enguehard map. In this paper, we study Jacobi polynomial which corresponds to the codes over \(\mathbb{F}_{2f}\). We show how to construct Jacobi forms with various index over the totally real field. This is one of extension of Broué-Enguehard map.

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.