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\).

The purpose of this article is to give combinatorial proofs of some binomial identities which were given by Z. Zhang.

Given \(t\geq 2\) cycles \(C_n\) of length \(n \geq 3\), each with a fixed vertex \(v^i_0\), \(i=1,2,\ldots,t\), let \(C^(t)_n\) denote the graph obtained from the union of the \(t\) cycles by identifying the \(t\) fixed vertices (\(v^1_0 = v^2_0 = \cdots = v^t_0\)). Koh et al. conjectured that \(C^(t)^n\) is graceful if and only if \(nt \equiv 0, 3 \pmod{4}\). The conjecture has been shown true for \(t = 3, 6, 4k\). In this paper, the conjecture is shown to be true for \(n = 5\).

Let \(G\) be a finite abelian group of exponent \(m\). By \(s(G)\) we denote the smallest integer \(c\) such that every sequence of \(t\) elements in \(G\) contains a zero-sum subsequence of length \(m\). Among other results, we prove that, let \(p\) be a prime, and let \(H = C_{p^{c_1}} \oplus \ldots C_{p^{c_l}}\) be a \(p\)-group. Suppose that \(1+\sum_{i=1}^{l}(p^{c_i}-1)=p^k\) for some positive integer \(k\). Then,\(4p^k – 3 \leq s(C_{p^k} \oplus H) \leq 4p^k – 2.\)

A connected dominating set \(D\) of a graph \(G\) has the property that not only does \(D\) dominate the graph but the subgraph induced by the vertices of \(D\) is also connected. We generalize this concept by allowing the subgraph induced by \(D\) to contain at most \(k\) components and examine the minimum possible order of such a set. In the case of trees, we provide lower and upper bounds and a characterization for those trees which achieve the former.

Let \(\sigma(K_{r,s}, n)\) denote the smallest even integer such that every \(n\)-term positive graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) with term sum \(\sigma(\pi) = d_1 + d_2 + \cdots + d_n \geq \sigma(K_{r,s}, n)\) has a realization \(G\) containing \(K_{r,s}\) as a subgraph, where \(K_{r,s}\) is the \(r \times s\) complete bipartite graph. In this paper, we determine \(\sigma(K_{2,3}, n)\) for \(m \geq 5\). In addition, we also determine the values \(\sigma(K_{2,s}, n)\) for \(s \geq 4\) and \(n \geq 2[\frac{(s+3)^2}{4}]+5\).

Formulas for vertex eccentricity and radius for the tensor product \(G \otimes H\) of two arbitrary graphs are derived. The center of \(G \otimes H\) is characterized as the union of three vertex sets of form \(A \times B\). This completes the work of Suh-Ryung Kim, who solved the case where one of the factors is bipartite. Kim’s result becomes a corollary of ours.

Let \(v, k,\lambda\) and \(n\) be positive integers. \((x_1, x_2, \ldots, x_k)\) is defined to be \(\{(x_i, x_j) : i \neq j, i,j =1,2,\ldots,k\},\) in which the ordered pair \((x_i, x_j)\) is called \((j-i)\)-apart for \(i > j\) and \((k+j-i)\)-apart for \(i > j\), and is called a cyclically ordered \(k\)-subset of \(\{x_1, x_2, \ldots, x_k\}\).

A perfect Mendelsohn design, denoted by \((v, k, \lambda)\)-PMD, is a pair \((X, B)\), where \(X\) is a \(v\)-set (of points), and \(B\) is a collection of cyclically ordered \(k\)-subsets of \(X\) (called blocks), such that every ordered pair of points of \(X\) appears \(t\)-apart in exactly \(\lambda\) blocks of \(B\) for any \(t\), where \(1 \leq t \leq k-1\).

If the blocks of a \((v, k, \lambda)\)-PMD for which \(v \equiv 0 \pmod{k}\) can be partitioned into \(\lambda(v-1)\) sets each containing \(v/k\) blocks which are pairwise disjoint, the \((v, k, \lambda)\)-PMD is called resolvable, denoted by \((v, k, \lambda)\)-RPMD.

In the paper [14], we have showed that a \((v, 4, 1)\)-RPMD exists for all \(v \equiv 0 \pmod{4}\) except for \(4, 8\) and with at most \(49\) possible exceptions of which the largest is \(336\).

In this article, we shall show that a \((v, 4, 1)\)-RPMD for all \(v \equiv 0 \pmod{4}\) except for \(4, 8, 12\) and with at most \(27\) possible exceptions of which the largest is \(188\).

The independence number of Cartesian product graphs is considered. An upper bound is presented that covers all previously known upper bounds. A construction is described that produces a maximal independent set of a Cartesian product graph and turns out to be a reasonably good lower bound for the independence number. The construction defines an invariant of Cartesian product graphs that is compared with its independence number. Several exact independence numbers of products of bipartite graphs are also obtained.

Multi-loop digraphs are widely studied mainly because of their symmetric properties and their applications to loop networks. A multi-loop digraph, \(G = G(N; s_1, \ldots, s_\Delta)\) with \(1 \leq s_1 < \cdots < s_\Delta \leq N-1\) and \(\gcd(N, s_1, \ldots, s_\Delta) = 1\), has set of vertices \(V ={Z}_N\) and adjacencies given by \(v \mapsto v + s_i \mod N, i = 1, \ldots, \Delta\). For every fixed \(N\), an usual extremal problem is to find the minimum value \[D_\Delta(N)=\min\limits_{s_1,\ldots,s_\Delta \in Z_N}(N; s_1, \ldots, s_\Delta)\] where \(D(N; s_1, \ldots, s_\Delta)\) is the diameter of \(G\). A closely related problem is to find the maximum number of vertices for a fixed value of the diameter. For \(\Delta = 2\), all optimal families have been found by using a geometrical approach. For \(\Delta = 3\), only some dense families are known. In this work, a new dense family is given for \(\Delta = 3\) using a geometrical approach. This technique was already adopted in several papers for \(\Delta = 2\) (see for instance [5, 7]). This family improves the dense families recently found by several authors.

Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1 (1999), 387-400) considered a variation of the classical Turén-type extremal problems as follows: for a given graph \(H\), determine the smallest even integer \(\sigma (H,n)\) such that every \(n\)-term positive graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) with term sum \(\sigma(\pi) = d_1 + d_2 + \cdots + d_n \geq \sigma(H,n)\) has a realization \(G\) containing \(H\) as a subgraph. In particular, they pointed out that \(3n – 2 \leq \sigma(K_{4} – e, n) \leq 4n – 4\), where \(K_{r+1} – e\) denotes the graph obtained by removing one edge from the complete graph \(K_{r+1}\) on \(r+1\) vertices. Recently, Lai determined the values of \(\sigma(K_4 – e, n)\) for \(n \geq 4\). In this paper, we determine the values of \(\sigma(K_{r+1} – e, n)\) for \(r \geq 3\) and \(r+1 \leq n \leq 2r\), and give a lower bound of \(\sigma(K_{r+1} – e, n)\). In addition, we prove that \(\sigma(K_5 – e, n) = 5n – 6\) for even \(n\) and \(n \geq 10\) and \(\sigma(K_5 – e, n) = 5n – 7\) for odd \(n\) and \(n \geq 9\).

We show that if \(G\) is a \(3\)-connected graph of order at least \(5\), then there exists a longest cycle \(C\) of \(G\) such that the number of contractible edges of \(G\) which are on \(C\) is greater than or equal to \(\frac{|V(C)| + 9}{8}.\)

We obtain lower bounds for the number of elements dominated by a subgroup in a Cayley graph. Let \(G\) be a finite group and let \(U\) be a generating set for \(G\) such that \(U = U^{-1}\) and \(1 \in U\). Let \(A\) be an independent subgroup of \(G\). Let \(r\) be a positive integer, and suppose that, in the Cayley graph \((G,U)\), any two non-adjacent vertices have at most \(r\) common neighbours. Let \(N[H]\) denote the set of elements of \(G\) which are dominated by the elements of \(H\). We prove that

1. \(|N[A]| \geq \lceil\frac{|U|^2}{r(|H \cup U^2|-1)+|U|}\rceil.\)
2. \(|N[A]| \geq |U||H| -\frac{|H|r}{2}(|H \cup U^2|-1).\)

An interesting example illustrating these results is the graph on the symmetric group \(S_n\), in which two permutations are adjacent if one can be obtained from the other by moving one element. For this graph we show that \(r = 4\) and illustrate the inequalities.

Shapiro [8] asked what simple family of circuits will have resistances \(C_{2n}/{C_{2n}-1}\) (or something similar) where \(C_m=\frac{1}{m+1}\binom{2m}{m}\) is the \(m\)th Catalan number. In this paper, we give a construction of such circuits; we also discuss some related problems.

The two-dimensional bandwidth problem is to determine an embedding of graph \(G\) in a grid graph in the plane such that the longest edges are as short as possible. In this paper, we study the problem under the distance of \(L_\infty\)-norm.

Domination graphs of directed graphs have been defined and studied in a series of papers by Fisher, Lundgren, Guichard, Merz, and Reid. A tie in a tournament may be represented as a double arc in the tournament. In this paper, we examine domination graphs of tournaments, tournaments with double arcs, and more general digraphs.

In this paper, we consider the problem of decomposing complete multigraphs into multistars (a multistar is a star with multiple edges allowed). We obtain a criterion for the decomposition of the complete multigraph \(\lambda K_n\), into multistars with prescribed number of edges, but the multistars in the decomposition with the same number of edges are not necessarily isomorphic. We also consider the problem of decomposing \(\lambda K_n\) into isomorphic multistars and propose a conjecture about the decomposition of \(2K_n\) into isomorphic multistars.

For edges \(e\) and \(f\) in a connected graph \(G\), the distance \(d(e, f)\) between \(e\) and \(f\) is the minimum nonnegative integer \(n\) for which there exists a sequence \(e = e_0, e_1, \ldots, e_l = f\) of edges of \(G\) such that \(e_i\) and \(e_{i+1}\) are adjacent for \(i = 0, 1, \ldots, l-1\). Let \(c\) be a proper edge coloring of \(G\) using \(k\) distinct colors and let \(D = \{C_1, C_2, \ldots, C_k\}\) be an ordered partition of \(E(G)\) into the resulting edge color classes of \(c\). For an edge \(e\) of \(G\), the color code \(c_D(e)\) of \(e\) is the \(k\)-tuple \((d(e, C_1), d(e, C_2), \ldots, d(e, C_k))\), where \(d(e, C_i) = \min\{d(e, f): f \in C_i\}\) for \(1 \leq i \leq k\). If distinct edges have distinct color codes, then \(c\) is called a resolving edge coloring of \(G\). The resolving edge chromatic number \(\chi_{re}(G)\) is the minimum number of colors in a resolving edge coloring of \(G\). Bounds for the resolving edge chromatic number of a connected graph are established in terms of its size and diameter and in terms of its size and girth. All nontrivial connected graphs of size \(m\) with resolving edge chromatic number \(3\) or \(m\) are characterized. It is shown that for each pair \(k, m\) of integers with \(3 \leq k \leq m\), there exists a connected graph \(G\) of size \(m\) with \(\chi_{re}(G) = k\). Resolving edge chromatic numbers of complete graphs are studied.

A decomposition of optimal linear block codes with minimum distance \(d = 4\) and length \(4L\) into two subcodes is given such that one of the subcodes is an optimal length \(L\) code with minimum Hamming distance \(4\) and the other is a quasi-cyclic code of index \(4\). It is shown that the \(L\)-section minimal trellis diagram of the code is the product of the minimal trellis diagrams of the subcodes.

We consider the rank of the adjacency matrix of some classes of regular graphs that are transformed under certain unary operations. In particular, we study the ranks of the subdivision graph, the connected cycle graph, the connected subdivision graph, and the total graph of the following families of graphs: cycles, complete graphs, complete bipartite and multipartite graphs, circulant graphs of degrees three and four, and some Cartesian graph products.