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.