Let \(P(G)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent, written \(G \sim H\), if \(P(G) = P(H)\). A graph \(G\) is chromatically unique if for any graph \(H\), \(G \sim H\) implies that \(G\) is isomorphic with \(H\). In “Chromatic Equivalence Classes of Certain Generalized Polygon Trees”, Discrete Mathematics Vol. \(172, 108–114 (1997)\), Peng \(et\; al\). studied the chromaticity of certain generalized polygon trees. In this paper, we present a chromaticity characterization of another big family of such graphs.

The step domination number of all graphs of diameter two is determined.

We use generator matrices \(G\) satisfying \(GG^T = aI + bJ\) over \(\mathbb{Z}_k\) to obtain linear self-orthogonal and self-dual codes. We give a new family of linear self-orthogonal codes over \(\text{GF}(3)\) and \(\mathbb{Z}_4\) and a new family of linear self-dual codes over \(\text{GF}(3)\).

Let \(S\) be a simply connected orthogonal polygon in the plane. Assume that the vertex set of \(S\) may be partitioned into sets \(A, B\) such that for every pair \(x, y\) in \(A\) (in \(B\)), \(S\) contains a staircase path from \(x\) to \(y\). Then \(S\) is a union of two or three orthogonally convex sets. If \(S\) is star-shaped via staircase paths, the number two is best, while the number three is best otherwise. Moreover, the simple connectedness requirement cannot be removed. An example shows that the segment visibility analogue of this result is false.

For a graph \(G\) of size \(m \geq 1\) and edge-induced subgraphs \(F\) and \(H\) of size \(r\) (\(1 \leq r \leq m\)), the subgraph \(Z\) is said to be obtained from \(F\) by an edge jump if there exist four distinct vertices \(u, v, w\), and \(x\) in \(G\) such that \(uv \in E(F)\), \(wx \in E(G) – E(F)\), and \(H = F – uv + wx\). The minimum number of edge jumps required to transform \(F\) into \(H\) is the jump distance from \(F\) to \(H\). For a graph \(G\) of size \(m \geq 1\) and an integer \(r\) with \(1 \leq r \leq m\), the \(r\)-jump graph \(J_r(G)\) is that graph whose vertices correspond to the edge-induced subgraphs of size \(r\) of \(G\) and where two vertices of \(J_r(G)\) are adjacent if and only if the jump distance between the corresponding subgraphs is \(1\). For \(k \geq 2\), the \(k\)th iterated jump graph \(J^k(G)\) is defined as \(J_r(J^{k-1}_{r}(G))\), where \(J^1_r(G) = J_r(G)\). An infinite sequence \(\{G_i\}\) of graphs is planar if every graph \(G_i\) is planar; while the sequence \(\{G_i\}\) is nonplanar otherwise. It is shown that if \(\{J^k_2(G)\}\) is a nonplanar sequence, then \(J^k_2(G)\) is nonplanar for all \(k \geq 3\) and there is only one graph \(G\) such that \(J^2_2(G)\) is planar. Moreover, for each integer \(r \geq 3\), if \(G\) is a connected graph of size at least \(r + 2\) for which \(\{J^k_r(G)\}\) is a nonplanar sequence, then \(J^k_r(G)\) is nonplanar for all \(k \geq 3\).

Let \(G\) be a finite group written additively and \(S\) a non-empty subset of \(G\). We say that \(S\) is \(e-exhaustive\) if \(G = S + \cdots + S\) (\(e\) times). The minimal integer \(e > 0\), if it exists, such that \(S\) is \(e-exhaustive\), is called the exhaustion number of the set \(S\) and is denoted by \(e(S)\). In this paper, we completely determine the exhaustion numbers of subsets of Abelian groups which are in arithmetic progression. The exhaustion numbers of various subsets of Abelian groups which are not in arithmetic progression are also determined.

Given graphs \(G\) and \(H\), an edge coloring of \(G\) is called an \((H,q)\)-coloring if the edges of every copy of \(H \subset G\) together receive at least \(q\) colors. Let \(r(G,H,q)\) denote the minimum number of colors in a \((H,q)\)-coloring of \(G\). In [6] Erdős and Gyárfás studied \(r(K_n,K_p,q)\) if \(p\) and \(q\) are fixed and \(n\) tends to infinity. They determined for every fixed \(p\) the smallest \(q\) for which \(r(K_n,K_p,q)\) is linear in \(n\) and the smallest \(q\) for which \(r(K_n,K_p,q)\) is quadratic in \(n\). In [9] we studied what happens between the linear and quadratic orders of magnitude. In [2] Axenovich, Füredi, and Mubayi generalized some of the results of [6] to \(r(K_{n,n},K_{p,p},q)\). In this paper, we adapt our results from [9] to the bipartite case, namely we study \(r(K_{n,n},K_p,p,q)\) between the linear and quadratic orders of magnitude. In particular, we show that we can have at most \(\log p + 1\) values of \(q\) which give a linear \(r(K_{n,n},K_{p,p},q)\).

In this paper, we define the concept of generalized Fibonacci polynomial of a graph \(G\) which gives the total number of all \(k\)-stable sets in generalized lexicographical products of graphs. This concept generalizes the Fibonacci polynomial of a graph introduced by G. Hopkins and W. Staton in [3].

A Fibonacci string of order \(n\) is a binary string of length \(n\) with no two consecutive ones. The Fibonacci cube \(\Gamma_n\) is the subgraph of the hypercube \(Q_n\) induced by the set of Fibonacci strings of order \(n\). For positive integers \(i, n\), with \(n \geq i\), the \(i\)th extended Fibonacci cube is the vertex-induced subgraph of \(Q_n\) for which \(V(\Gamma_{i}^{n}) = V_i\) is defined recursively by

\[V_{n+2}^{i} = 0 V_{n+1}^{i} + 10V_n^{i},\]

with initial conditions \(V_i^i = B_i, V_{i+1}^{i} = B_{i+1}\), where \(B_k\) denotes the set of binary strings of length \(k\). In this study, we answer in the affirmative a conjecture of Wu [10] that the sequences \(\{|V_n^i|\}_{i={1+2}}^\infty\) are pairwise disjoint for all \(i \geq 0\), where \(V_n^0 = V(\Gamma_n)\).