The proof of gracefulness for the Generalised Petersen Graph \(P_{8t,3}\) for every \(t \geq 1\), written by the same author (Graceful labellings for an infinite class of generalised Petersen graphs, Ars Combinatoria \(81 (2006)\), pp. \(247-255)\), requires the change of just one label, for the only case \(t = 5\).

For words of length \(n\), generated by independent geometric random variables, we study the average initial and end heights of the last descent in the word. In addition, we compute the average initial and end height of the last descent in a random permutation of \(n\) letters.

We construct a record-breaking binary code of length \(17\), minimal distance \(6\), constant weight \(6\), and containing \(113\) codewords.

The purpose of this note is to give the power formula of the generalized Lah matrix and show \(\mathcal{L}[x,y] = \mathcal{FQ}[x,y]\), where \(\mathcal{F}\) is the Fibonacci matrix and \(\mathcal{Q}[x,y]\) is the lower triangular matrix. From it, several combinatorial identities involving the Fibonacci numbers are obtained.

A graph is called set reconstructible if it is determined uniquely (up to isomorphism) by the set of its vertex-deleted subgraphs. We prove that some classes of separable graphs with a unique endvertex are set reconstructible and show that all graphs are set reconstructible if all \(2\)-connected graphs are set reconstructible.

We prove the following extension of the Erdős-Ginzburg-Ziv Theorem. Let \(m\) be a positive integer. For every sequence \(\{a_i\}_{i\in I}\) of elements from the cyclic group \(\mathbb{Z}_m\), where \(|I| = 4m – 5\) (where \(|I| = 4m – 3\)), there exist two subsets \(A, B \subseteq I\) such that \(|A \cap B| = 2\) (such that \(|A \cap B| = 1\)), \(|A| = |B| = m\), and \(\sum\limits_{i\in b} a_i = \sum\limits_{i\in b} b_i = 0\).

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.

Let \(G = (V, E)\) be a \(k\)-connected graph. For \(t \geq 3\), a subset \(T \subset V\) is a \((t,k)\)-shredder if \(|T| = k\) and \(G – T\) has at least \(t\) connected components. It is known that the number of \((t,k)\)-shredders in a \(k\)-connected graph on \(n\) nodes is less than \(\frac{2n}{2t – 3}\). We show a slightly better bound for the case \(k \leq 2t – 3\).

Let \(L\) and \(R\) be two graphs. For any positive integer \(n\), the Ehrenfeucht-Fraissé game \(G_n(L, R)\) is played as follows: on the \(i\)-th move, with \(1 \leq i \leq n\), the first player chooses a vertex on either \(L\) or \(R\), and the second player responds by choosing a vertex on the other graph. Let \(l_i\) be the vertex of \(L\) chosen on the \(i^{th}\) move, and let \(r_i\) be the vertex of \(R\) chosen on the \(i^{th}\) move. The second player wins the game iff the induced subgraphs \(L\{l_1,l_2,…,l_n\}\) and \(R\{r_1,r_2,…,r_n\}\) are isomorphic under the mapping sending \(l_i\) to \(r_i\). It is known that the second player has a winning strategy if and only if the two graphs, viewed as first-order logical structures (with a binary predicate E), are indistinguishable (in the corresponding first-order theory) by sentences of quantifier depth at most \(n\). In this paper we will give the first complete description of when the second player has a winning strategy for \(L\) and \(R\) being both paths or both cycles. The results significantly improve previous partial results.

By applying the method of generating function, the purpose of this paper is to give several summations of reciprocals related to \(l-th\) power of generalized Fibonacci sequences. As applications, some identities involving Fibonacci, Lucas numbers are obtained.

Bricks are polyominoes with labelled cells. The problem whether a given set of bricks is a code is undecidable in general. We consider sets consisting of square bricks only. We have shown that in this setting, the codicity of small sets (two bricks) is decidable, but \(15\) bricks are enough to make the problem undecidable. Thus the step from words to even simple shapes changes the algorithmic properties significantly (codicity is easily decidable for words). In the present paper we are interested whether this is reflected by quantitative properties of words and bricks. We use their combinatorial properties to show that the proportion of codes among all sets is asymptotically equal to \(1\) in both cases.

Let \(G_{n,m} = C_n \times P_m\), be the cartesian product of an \(n\)-cycle \(C_n\) and a path \(P_m\) of length \(m-1\). We prove that \(\chi'(G_{n,m}) = \chi'(G_{n,m}) = 4\) if \(m \geq 3\), which implies that the list-edge-coloring conjecture (LLECC) holds for all graphs \(G_{n,m}\).

Various authors have defined statistics on Dyck paths that lead to generalizations of the Catalan numbers. Three such statistics are area, maj, and bounce. Haglund, whe introduced the bounce statistic, gave an algebraic proof that \(n(n – 1)/2+\) area — bounce and maj have the same distribution on Dyck paths of order \(n\). We give an explicit bijective proof of the same result.

We develop a new type of a vertex labeling of graphs, namely \(2n\)-cyclic blended labeling, which is a generalization of some previously known labelings. We prove that a graph with this labeling factorizes the complete graph on \(2nk\) vertices, where \(k\) is odd and \(n, k > 1\).

Let \(D = (V, E)\) be a primitive digraph. The exponent of \(D\) at a vertex \(u \in V\), denoted by \(\text{exp}_D(u)\), is defined to be the least integer \(k\) such that there is a walk of length \(k\) from \(u\) to \(v\) for each \(v \in V\). Let \(V = \{v_1,v_2,\ldots ,v_n\}\). The vertices of \(V\) can be ordered so that \(\text{exp}_D(v_{i_1}) \leq \text{exp}_D(v_{i_2}) \leq \ldots \leq \text{exp}_D(v_{i_n})\). The number \(\text{exp}_D(v_{i_k})\) is called \(k\)-exponent of \(D\), denoted by \(\text{exp}_D(k)\). In this paper, we completely characterize \(1\)-exponent set of primitive, minimally strong digraphs with \(n\) vertices.

In \([4]\) H. Galana-Sanchez introduced the concept of kernels by monochromatic paths which generalize the concept of kernels. In \([6]\) they proved the necessary and sufficient conditions for the existence of kernels by monochromatic paths of the duplication of a subset of vertices of a digraph, where a digraph is without monochromatic directed circuits. In this paper we study independent by monochromatic paths sets and kernels by monochromatic paths of the duplication. We generalize result from \([6]\) for an arbitrary edge coloured digraph.

Let \(D = (V, E)\) be a primitive, minimally strong digraph. In \(1982\), J. A. Ross studied the exponent of \(D\) and obtained that \(\exp(D) \leq n + s(n – 8)\), where \(s\) is the length of a shortest circuit in \(D\) \([D]\). In this paper, the \(k\)-exponent of \(D\) is studied. Our principle result is that
\[
\exp_D(k) \leq \begin{cases}
k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\
k + s(n-3), & \text{if } s+1 \leq k \leq n,\\
\end{cases} \\.
\]
with equality if and only if \(D\) isomorphic to the diagraph \(D_{s,n}\) with vertex set \(V(D_{s,n})=\{v_1,v_2,\ldots,v_n\}\) and arc set \(E(D_{s,n})=\{(v_i,v_{i+1}):1\leq i\leq n-1\}\cap \{(v_s,v_1),(v_n,v_2)\}\). If \((s,n-1)\neq 1\),then
\[
\exp_D(k)< \begin{cases} k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\ k + s(n-3), & \text{if } s+1 \leq k \leq n, \end{cases} \\ \] and if \((s,n-1)=1\), then \(D_{s, n}\) is a primitive, minimally strong digraph on \(n\) vertices with the \(k\)-exponent \[ \exp_D(k)= \begin{cases} k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\ k + s(n-3), & \text{if } s+1 \leq k \leq n, \end{cases} \\ \] Moreover, we provide a new proof of Theorem \(1\) in \([6]\) and Theorem \(2\) in \([14]\) by applying this result.

Given a finite projective plane of order \(n\). A quadrangle consists of four points \(A, B, C, D\), no three collinear. If the diagonal points are non-collinear, the quadrangle is called a non-Fano quad. A general sum of squares theorem is proved for the distribution of points in a plane containing a non-Fano quad, whenever \(n \geq 7\). The theorem implies that the number of possible distributions of points in a plane of order \(n\) is bounded for all \(n \geq 7\). This is used to give a simple combinatorial proof of the uniqueness of \(PP(7)\).

Let \(G = (V, E)\) be a graph with \(n\) vertices. The clique graph of \(G\) is the intersection graph \(K(G)\) of the set of all (maximal) cliques of \(G\) and \(K\) is called the clique operator. The iterated clique graphs \(K^*(G)\) are recursively defined by \(K^0(G) = G\) and \(K^i(G) = K(K^{i-1}(G))\), \(i > 0\). A graph is \(K\)-divergent if the sequence \(|V(K^i(G))|\) of all vertex numbers of its iterated clique graphs is unbounded, otherwise it is \(K\)-convergent. The long-run behaviour of \(G\), when we repeatedly apply the clique operator, is called the \(K\)-behaviour of \(G\).

In this paper, we characterize the \(K\)-behaviour of the class of graphs called \(p\)-trees, that has been extensively studied by Babel. Among many other properties, a \(p\)-tree contains exactly \(n – 3\) induced \(4\)-cycles. In this way, we extend some previous results about the \(K\)-behaviour of cographs, i.e., graphs with no induced \(P_4\)s. This characterization leads to a polynomial-time algorithm for deciding the \(K\)-convergence or \(K\)-divergence of any graph in the class.

In this paper, we obtain a general enumerating functional equation about rooted pan-fan maps on nonorientable surfaces. Based on this equation, an explicit expression of rooted pan-fan maps on the Klein bottle is given. Meanwhile, some simple explicit expressions with up to two parameters: the valency of the root face and the size for rooted one-vertexed maps on surfaces (Klein bottle, Torus, \(N_3\)) are provided.

Let us denote by \({EX}(m,n; \{C_4,\ldots,C_{2t}\})\) the family of bipartite graphs \(G\) with \(m\) and \(n\) vertices in its classes that contain no cycles of length less than or equal to \(2t\) and have maximum size. In this paper, the following question is proposed: does always such an extremal graph \(G\) contain a \((2t + 2)\)-cycle? The answer is shown to be affirmative for \(t = 2,3\) or whenever \(m\) and \(n\) are large enough in comparison with \(t\). The latter asymptotical result needs two preliminary theorems. First, we prove that the diameter of an extremal bipartite graph is at most \(2t\), and afterwards we show that its girth is equal to \(2t + 2\) when the minimum degree is at least \(2\) and the maximum degree is at least \(t + 1\).