A connected graph is said to be super edge-connected if every minimum edge-cut isolates a vertex. The restricted edge-connectivity \(\lambda’\) of a connected graph is the minimum number of edges whose deletion results in a disconnected graph such that each component has at least two vertices. It has been shown by A. H. Esfahanian and S. L. Hakimi (On computing a conditional edge-connectivity of a graph. Information Processing Letters, 27(1988), 195-199] that \(\lambda'(G) \leq \xi(G)\) for any graph of order at least four that is not a star, where \(\xi(G) = \min\{d_G(u) + d_G(v) – 2: uv \text{ is an edge in } G\}\). A graph \(G\) is called \(\lambda’\)-optimal if \(\lambda'(G) = \xi(G)\). This paper proves that the de Bruijn undirected graph \(UB(d,n)\) is \(\lambda’\)-optimal except \(UB(2,1)\), \(UB(3,1)\), and \(UB(2,3)\), and hence, is super edge-connected for \(n\geq 1\) and \(d\geq 2\).

The problem of graceful labeling of a particular class of trees called quasistars is considered. Such a quasistar is a tree \(Q\) with \(k\) distinct paths with lengths \(1, d+1, 2d+1, \ldots, (k-1)d+1\) joined at a unique vertex \(\theta\).

Thus, \(Q\) has \(1 + [1 + (d+1) + (2d+1) + \ldots + (k-1)d+1)] = 1+k +\frac{k(k-1)d}{2}\) vertices. The \(k\) paths of \(Q\) have lengths in arithmetic progression with common difference \(d\). It is shown that \(Q\) has a graceful labeling for all \(k \leq 6\) and all values of \(d\).

The average distance \(\mu(D)\) of a strong digraph \(D\) is the average of the distances between all ordered pairs of distinct vertices of \(D\). Plesnik \([3]\) proved that if \(D\) is a strong tournament of order \(n\), then \(\mu(D) \leq \frac{n+4}{6} + \frac{1}{n}\). In this paper we show that, asymptotically, the same inequality holds for strong bipartite tournaments. We also give an improved upper bound on the average distance of a \(k\)-connected bipartite tournament.

To measure the efficiency of a routing in network, Chung et al. [The forwarding index of communication networks. IEEE Trans. Inform. Theory, 33 (2) (1987), 224-232] proposed the notion of forwarding index and established an upper bound \((n – 1)(n – 2)\) of this parameter for a connected graph of order \(n\). This note improves this bound as \((n – 1)(n – 2) – (2n – 2 – \Delta\lfloor1+\frac{n-1}{\Delta}\rfloor)\) \(\lfloor \frac{n-1}{\Delta}\rfloor\) , where \(\Delta\) is the maximum degree of the graph \(G\). This bound is best possible in the sense that there is a graph \(G\) attaining it.

We study the spectral radius of unicyclic graphs with \(n\) vertices and edge independence number \(q\). In this paper, we show that of all unicyclic graphs with \(n\) vertices and edge independence number \(q\), the maximal spectral radius is obtained uniquely at \(\Delta_n(q)\), where \(\Delta_n(q)\) is a graph on \(n\) vertices obtained from the cycle \(C_3\) by attaching \(n – 2q + 1\) pendant edges and \(q – 2\) paths of length \(2\) at one vertex.

Let \(q\) be an odd prime power and \(p\) be an odd prime with \(gcd(p, g) = 1\). Let the order of \(g\) modulo \(p\) be \(f\) and \(gcd(\frac{p-1}{f}, q) = 1\). Here explicit expressions for all the primitive idempotents in the ring \(R_{2p^n} = GF(q)[x]/(x^{2p^n} – 1)\), for any positive integer \(n\), are obtained in terms of cyclotomic numbers, provided \(p\) does not divide \(\frac{q^f-1}{2p}\), if \(n \geq 2\). Some lower bounds on the minimum distances of irreducible cyclic codes of length \(2p^n\) over \(GF(q)\) are also obtained.

Let \(G\) be a connected multigraph with an even number of edges and suppose that the degree of each vertex of \(G\) is even. Let \((uv, G)\) denote the multiplicity of edge \((u,v)\) in \(G\). It is well known that we can obtain a halving of \(G\) into two halves \(G_1\) and \(G_2\), i.e. that \(G\) can be decomposed into multigraphs \(G_1\) and \(G_2\), where for each vertex \(v\), \(\deg(v, G_1) = \deg(v, G_2) = \frac{1}{2}\deg(v,G)\). It is also easy to see that if the edges with odd multiplicity in \(G\) induce no components with an odd number of edges, then we can obtain such a halving of \(G\) into two halves \(G_1\) and \(G_2\) that is well-spread, i.e. for each edge \((u,v)\) of \(G\), \(|\mu(uv, G_1) – \mu(uv, G_2)| \leq 1\). We show that if \(G\) is a \(\Delta\)-regular multigraph with an even number of vertices and with \(\Delta\) being even, then even if the edges with odd multiplicity in \(G\) induce components with an odd number of edges, we can still obtain a well-spread halving of \(G\) provided that we allow the addition/removal of a Hamilton cycle to/from \(G\). We give an application of this result to obtaining sports schedules such that multiple encounters between teams are well-spread throughout the season.

A fractional edge coloring of graph \(G\) is an assignment of a nonnegative weight \(w_M\) to each matching \(M\) of \(G\) such that for each edge \(e\) we have \(\sum_{M\ni e} w_M \geq 1\). The fractional edge coloring chromatic number of a graph \(G\), denoted by \(\chi’_f(G)\), is the minimum value of \(\sum_{M} w_M\) (where the minimum is over all fractional edge colorings \(w\)). It is known that for any simple graph \(G\) with maximum degree \(\Delta\), \(\Delta < \chi'_f(G) \leq \Delta+1\). And \(\chi'_f(G) = \Delta+1\) if and only if \(G\) is \(K_{2n+1}\). In this paper, we give some sufficient conditions for a graph \(G\) to have \(\chi'_f(G) = \Delta\). Furthermore, we show that the results in this paper are the best possible.

A subset \(D\) of the vertex set \(V\) of a graph is called an open odd dominating set if each vertex in \(V\) is adjacent to an odd number of vertices in \(D\) (adjacency is irreflexive). In this paper we solve the existence and enumeration problems for odd open dominating sets (and analogously defined even open dominating sets) in the \(m \times n\) grid graph and prove some structural results for those that do exist. We use a combination of combinatorial and linear algebraic methods, with particular reliance on the sequence of Fibonacci polynomials over \({GF}(2)\).

By introducing \(4\) colour classes in projective planes with non-Fano quads, discussion of the planes of small order is simplified.