A class of graphs called generalized ladder graphs is defined. A sufficient condition for pairs of these graphs to be chromatically equivalent is proven. In addition, a formula for the chromatic polynomial of a graph of this type is proven. Finally, the chromatic polynomials of special cases of these graphs are explicitly computed.

Let \(k \geq 3\) be odd and \(G = (V(G), E(G))\) be a \(k\)-edge-connected graph. For \(X \subseteq V(G)\), \(e(X)\) denotes the number of edges between \(X\) and \(V(G) – X\). We here prove that if \(\{s_i, t_i\} \subseteq X_i \subseteq V(G)\), \(i = 1, 2\), \(X_1 \cap X_2 = \emptyset\), \(e(X_1) \leq 2k-2\) and \(e(X_2) < 2k-1\), then there exist paths \(P_1\) and \(P_2\) such that \(P_i\) joins \(s_i\) and \(t_i\), \(V(P_i) \subseteq X_i\) (\(i = 1, 2\)) and \(G – E(P_1 \cup P_2)\) is \((k-2)\)-edge-connected. And in fact, we give a generalization of this result and some other results about paths not containing given edges.

Optimal binary linear codes of length \(18\) containing the \([6, 5, 2]\otimes[ 3, 1, 3]\) product code are presented. It is shown that these are \([18, 9, 5]\) and \([18, 8, 6]\) codes. The soft-decision maximum-likelihood decoding complexity of these codes is determined. From this point of view, these codes are better than the \([18, 9, 6]\) code.

It is shown that the voltage-current duality in topological graph theory can be obtained as a consequence of a combinatorial description of the pair (an embedded graph, the embedded dual graph)without any reference to derived graphs and derived embeddings. In the combinatorial description the oriented edges of an embedded graph are labeled by oriented edges of the embedded dual graph.

We extend the work of Currie and Fitzpatrick [1] on circular words avoiding patterns by showing that, for any positive integer \(n\), the Thue-Morse word contains a subword of length \(n\) which is circular cube-free. This proves a conjecture of V. Linek.

Let \(G\) be a simple graph with the average degree \(d_{ave}\) and the maximum degree \(\Delta\). It is proved, in this paper, that \(G\) is not critical if \(d_{ave} \leq \frac{103}{12}\) and \(\Delta \geq 12\). It also improves the current result by L.Y. Miao and J.L. Wu [7] on the number of edges of critical graphs for \(\Delta \geq 12\).

A \(3\)-restricted edge cut is an edge cut that disconnects a graph into at least two components each having order at least \(3\). The cardinality \(\lambda_3\) of minimum \(3\)-restricted edge cuts is called \(3\)-restricted edge connectivity. Let \(G\) be a connected \(k\)-regular graph of girth \(g(G) \geq 4\) and order at least \(6\). Then \(\lambda_3 \leq 3k – 4\). It is proved in this paper that if \(G\) is a vertex transitive graph then either \(\lambda_3 = 3k – 4\) or \(\lambda_3\) is a divisor of \(|G|\) such that \(2k – 2 \leq \lambda_3 \leq 3k – 5\) unless \(k = 3\) and \(g(G) = 4\). If \(k = 3\) and \(g(G) = 4\), then \(\lambda_3 = 4\). The extreme cases where \(\lambda_3 = 2k – 2\) and \(\lambda_3 = 3k – 5\) are also discussed.

Some classes of neighbour balanced designs in two-dimensional blocks are constructed. Some of these designs are statistically optimal and others are highly efficient when errors arising from units within each block are correlated.

Let \(G = (V, E)\) be a simple graph. For any real-valued function \(f: V \to {R}\) and \(S \subseteq V\), let \(f(S) = \sum_{v \in S} f(v)\). Let \(c, d\) be positive integers such that \(\gcd(c, d) = 1\) and \(0 < \frac{c}{d} \leq 1\). A \(\frac{c}{d}\)-dominating function (partial signed dominating function) is a function \(f: V \to \{-1, 1\}\) such that \(f(N[v]) \geq c\) for at least \(c\) of the vertices \(v \in V\). The \(\frac{c}{d}\)-domination number (partial signed domination number) of \(G\) is \(\gamma_{\frac{c}{d}}(G) = \min \{f(V) | f \text{ is a } \frac{c}{d}\text{-dominating function on } G\}\). In this paper, we obtain a few lower bounds of \(\gamma_{\frac{c}{d}}(G)\).

The groups \(G^{k,l,m}\) have been extensively studied by H. S. M. Coxeter. They are symmetric groups of the maps \(\{k,l\}_m\) which are constructed from the tessellations \(\{k,l\}\) of the hyperbolic plane by identifying two points, at a distance \(m\) apart, along a Petrie path. It is known that \(\text{PSL}(2,q)\) is a quotient group of the Coxeter groups \(G^{(m)}\) if \(-1\) is a quadratic residue in the Galois field \({F}_q\), where \(q\) is a prime power. G. Higman has posed the question that for which values of \(k,l,m\), all but finitely many alternating groups \(A_k\) and symmetric groups \(S_k\) are quotients of \(G^{k,l,m}\). In this paper, we have answered this question by showing that for \(k=3,l=11\), all but finitely many \(A_n\) and \(S_n\) are quotients of \(G^{3,11,m}\), where \(m\) has turned out to be \(924\).