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.