In this paper, by using the generating function method, we obtain a series of identities involving the generalized Fibonacci and Lucas numbers.

This paper introduces the problem of finding a permutation \(\phi\) on the vertex set \(V(G)\) of a graph \(G\) such that the sum of the distances from each vertex to its image under \(\phi\) is maximized. We let \(\mathcal{S}(G) = \max \sum_{v\in V(G)} d(v, \phi(v))\), where the maximum is taken over all permutations \(\phi\) of \(V(G)\). Explicit formulae for several classes of graphs as well as general bounds are presented.

The local-edge-connectivity \((u,v)\) of two vertices \(u\) and \(v\) in a graph or digraph \(D\) is the maximum number of edge-disjoint \(u-v\) paths in \(D\), and the edge-connectivity of \(D\) is defined as \(\lambda(D) = \min\{\lambda(u, v) | u,v \in V(D)\}\). Clearly, \(\lambda(u,v) \leq \min\{d^+(u),d^-(v)\}\) for all pairs \(u\) and \(v\) of vertices in \(D\). We call a graph or digraph \(D\) maximally local-edge-connected when

\[\lambda(u, v) = \min\{d^+(u),d^-(v)\}\]

for all pairs \(u\) and \(v\) of vertices in \(D\).

Recently, Fricke, Oellermann, and Swart have shown that some known sufficient conditions that guarantee equality of \(\lambda(G)\) and minimum degree \(\delta(G)\) for a graph \(G\) are also sufficient to guarantee that \(G\) is maximally local-edge-connected.
In this paper we extend some results of Fricke, Oellermann, and Swart to digraphs and we present further sufficient conditions for
graphs and digraphs to be maximally local-edge-connected.

We show that every hamiltonian claw-free graph with a vertex \(x\) of degree \(d(x) \geq 7\) has a \(2\)-factor consisting of exactly two cycles.

This paper presents two new algorithms for generating \((n,2)\) de Bruijn sequences which possess certain properties. The sequences generated by the proposed algorithms may be useful for experimenters to systematically investigate intertrial repetition effects. Characteristics are compared with those of randomly sampled \((n,2)\) de Bruijn sequences.

Let \(\alpha(G)\) and \(\tau(G)\) denote the independence number and matching number of a graph \(G\), respectively. The tensor product of graphs \(G\) and \(H\) is denoted by \(G \times H\). Let \(\underline{\alpha}(G \times H) = \max \{\alpha(G) \cdot n(H), \alpha(H) \cdot n(G)\}\) and \(\underline{\tau}(G \times H) = 2\tau(G) \cdot \tau(H)\), where \(\nu(G)\) denotes the number of vertices of \(G\). It is easy to see that \(\alpha(G \times H) \geq \underline{\alpha}(G \times H)\) and \(\beta(G \times H) \geq \underline{\tau}(G \times H)\). Several sufficient conditions for \(\alpha(G \times H) > \underline{\alpha}(G \times H)\) are established. Further, a characterization is established for \(\alpha(G \times H) = \underline{\tau}(G \times H)\). We have also obtained a necessary condition for \(\alpha(G \times H) = \underline{\alpha}(G \times H)\). Moreover, it is shown that neither the hamiltonicity of both \(G\) and \(H\) nor large connectivity of both \(G\) and \(H\) can guarantee the equality of \(\alpha(G \times H)\) and \(\underline{\alpha}(G \times H)\).

A graphoidal cover of a graph \(G\) is a collection \(\psi\) of (not necessarily open) paths in \(G\) such that every vertex of \(G\) is an internal vertex of at most one path in \(\psi\) and every edge of \(G\) is an exactly one path in \(\psi\). If further no member of \(\psi\) is a cycle, then \(\psi\) is called an acyclic graphoidal cover of \(G\). The minimum cardinality of an acyclic graphoidal cover is called the acyclic graphoidal covering number of \(G\) and is denoted by \(\eta_a\). In this paper, we characterize the class of graphs for which \(\eta_a = q – p\), where \(p\) and \(q\) denote respectively the order and size of \(G\).

The dissociation number of a graph \(G\) is the number of vertices in a maximum size induced subgraph of \(G\) with vertex degrees at most \(1\). The problem of finding the dissociation number was introduced by Yannakakis, who proved it is NP-hard on the class of bipartite graphs. In this paper, we analyze the dissociation number problem restricted to the class of bipartite graphs in more detail. We strengthen the result of Yannakakis by reducing the problem, in polynomial time, from general bipartite graphs to some particular classes, such as bipartite graphs with maximum degree \(3\) or \(C_4\)-free bipartite graphs. Besides the negative results, we prove that finding the dissociation number is polynomially solvable for bipartite graphs containing no induced subgraph isomorphic to a tree with exactly three vertices of degree \(1\) of distances \(1\), \(2\), and \(3\) from the only vertex of degree \(3\).

The induced matching number of a graph \(G\) is the number of edges in a maximum size induced subgraph of \(G\) with vertex degrees equal to \(1\). Analogous results hold for the induced matching number.

A vertex \(k\)-coloring of a graph \(G\) is acyclic if no cycle is bichromatic. The minimum integer \(k\) such that \(G\) admits an acyclic \(k\)-coloring is called the acyclic chromatic number of \(G\), denoted by \(\chi_a(G)\). In this paper, we discuss some properties of maximal acyclic \(k\)-colorable graphs, prove a sharp lower bound of the \(\chi_a(G)\) and get some results about the relation between \(\chi(G)\) and \(\chi_a(G)\). Furthermore, a conjecture of B. Grünbaum that \(\chi_a(G) \leq \Delta+1\) is proved for maximal acyclic \(k\)-colorable graphs.

In this paper, we focus on the existence of \(2\)-critical sets in the latin square corresponding to the elementary abelian \(2\)-group of order \(2^n\). It has been shown by Stinson and van Rees that this latin square contains a \(2\)-critical set of volume \(4^n – 3^n\). We provide constructions for \(2\)-critical sets containing \(4^n – 3^n + 1 – \left(2^{k-1} + 2^{m-1} + 2^{n-(k+m+1)}\right)\) entries, where \(1 \leq k \leq n\) and \(1 \leq m \leq n – k\). That is, we construct \(2\)-critical sets for certain values less than \(4^n – 3^n + 1 – 3\cdot 2^{\lfloor n/3\rfloor – 1}\). The results raise the interesting question of whether, for the given latin square, it is possible to construct \(2\)-critical sets of volume \(m\), where \(4^n – 3^n + 1 – 3\cdot 2^{\lfloor n/3\rfloor – 1} < m < 4^n – 3^n\).

In this paper, we find explicit formulas, or recurrences, in terms of generating functions for the cardinalities of the sets \(S_{n}(T; \tau)\) of all permutations in \(S_n\) that contain \(\tau \in S_k\) exactly once and avoid a subset \(T \subseteq S_3\) where \(|T| \geq 2\).

A digraph \(T\) is called strongly connected if for every pair of vertices \(u\) and \(v\) there exists a directed path from \(u\) to \(v\) and a directed path from \(v\) to \(u\). Denote the in-degree and out-degree of a vertex \(v\) of \(T\) by \(d^-(v)\) and \(d^+(v)\), respectively. We define \(\delta^- = \min_{v\in V(T)} \{d^-(v)\}\), and \(\delta_+ = \min_{v\in V(T)} \{d^+(v)\}\). Let \(T_0\) be a \(7\)-tournament which contains no transitive \(4\)-subtournament. Let \(T\) be a strong tournament, \(T \ncong T_0\) and \(k \geq 2\). In this paper, we show that if \(\delta^+ + \delta^- \geq \frac{k-2}{k-1}n+3k(k-1)\), then \(T\) can be partitioned into \(k\) cycles. When \(n \geq 3k(k-1)\) a regular strong \(n\)-tournament can be partitioned into \(k\) cycles and a almost regular strong \(n\)-tournament can be partitioned into \(k\) cycles when \(n \geq (3k+1)(k-1)\). Finally, if a strong tournament \(T\) can be partitioned into \(k\) cycles, \(q\) is an arbitrary positive integer not larger than \(k\). We prove that \(T\) can be partitioned into \(q\) cycles.

Let \(G = (V, E)\) be a simple graph. Let \(\alpha\) and \(\mathrm{IR}\) be the independence number and upper irredundance number of \(G\), respectively. In this paper, we prove that for any graph \(G\) of order \(n\) with maximum degree \(\Delta \geq 1\), \(\mathrm{IR}(G) – \alpha(G) \leq \frac{\Delta -2}{2\Delta }n\). When \(\Delta = 3\), the result was conjectured by Rautenbach.

We first establish the relationship between the largest eigenvalue of the Laplacian matrix of a graph and its bipartite density. Then, we present lower and upper bounds for the largest Laplacian eigenvalue of a graph in terms of its largest degree and diameter.

In this paper, we prove the gracefulness of the class of graphs denoted by \(\mathcal{P}_{a,b}\).

Let \(D\) be a dominating set of a simple graph \(G = (V, E)\). If the subgraph \((V – D)_G\)induced by the set \(V – D\) is disconnected, then \(D\) is called a split dominating set of \(G\), and if \(\langle D\rangle_G\) has no edges, then \(D\) is an independent dominating set of \(G\). If every vertex in \(V\) is adjacent to some vertex of \(D\) in \(G\), then \(D\) is a total dominating set of \(G\). The split domination number \(\gamma_s(G)\), independent domination number \(i(G)\), and total domination number \(\gamma_t(G)\) equal the minimum cardinalities of a split, independent, and total dominating set of \(G\), respectively. The concept of split domination was first defined by Kulli and Janakiram in 1997 [4], while total domination was introduced by Cockayne, Dawes, and Hedetniemi in 1980 [2].

In this paper, we study the split, independent, and total domination numbers of corona \(G \circ H\) and generalized coronas \(kG \circ H\) of graphs.

A set of points in a Steiner triple system (STS(\(v\))) is said to be independent if no three of these points occur in the same block. In this paper, we derive for each \(k \leq 8\) a closed formula for the number of independent sets of cardinality \(k\) in an STS(\(v\)). We use the formula to prove that every STS(21) has an independent set of cardinality eight and is, as a consequence, \(4\)-colourable.

Let \(G\) be a graph with \(n\) vertices and let \(D\) be a minimum dominating set of \(G\). If \(V – D\) contains a dominating set \(D’\) of \(G\), then \(D’\) is called an inverse dominating set of \(G\) with respect to \(D\). The inverse domination number \(\gamma'(G)\) of \(G\) is the cardinality of a smallest inverse dominating set of \(G\). In this paper, we characterise graphs for which \(\gamma(G) + \gamma'(G) = n\). We give a lower bound for the inverse domination number of a tree and give a constructive characterisation of those trees which achieve this lower bound.

Siri and Gvozdjak proved in [9] that the bananas surface, the pseudosurface consisting in the \(2\)-amalgamation of two spheres, does not admit a finite Kuratowski Theorem.

In this paper we prove that pseudosurfaces arising from the \(n\)-amalgamation of two closed surfaces, \(n \geq 2\), do not admit a finite Kuratowski Theorem, by showing an infinite family of minimal non-embeddable graphs.

We denote by \(K(l*r)\) the complete \(r\)-partite graph with \(l\) vertices in each part, and denote \(K(l*v)+K(m*s)+K(n*t)+\cdots\) by \(K(l*r,m*s,n*t,\ldots)\). Kierstead showed that the choice number of \(K(3*r)\) is exactly \(\left\lceil\frac{4r-1}{3}\right\rceil\). In this paper, we shall determine the choice number of \(K(3*r,1*t)\), and consider the choice number of \(K(3*r,2*s,1*t)\).

For any prime power \(q\), there exists an affine plane of order \(q\). The complement of an affine plane is a balanced incomplete block design (BIBD) with block size \(q^2-q\). In this note, a proof is given that the blocks can be split into sub-blocks to form a nested BIBD with parameters \((q^2, q^2+q, q^3+q^2, q^2-1,q-1)\). Alternatively, this is a generalized tournament design with one game each round, involving \(q\) teams, each team with \(q-1\) players.

Let \(\mathcal{F}\) be a family of \(k\)-graphs. A \(k\)-graph \(G\) is called \(\mathcal{F}\)-saturated if it is a maximal graph not containing any member of \(\mathcal{F}\) as a subgraph. We investigate the smallest number of edges that an \(\mathcal{F}\)-saturated graph on \(n\) vertices can have. We present new results and open problems for different instances of \(\mathcal{F}\).

A strongly regular vertex with parameters \((\lambda, \mu)\) in a graph is a vertex \(x\) such that the number of neighbors any other vertex \(y\) has in common with \(x\) is \(\lambda\) if \(y\) is adjacent to \(x\), and is \(\mu\) if \(y\) is not adjacent to \(x\). In this note, we will prove some basic properties of these vertices and the graphs that contain them, as well as provide some simple constructions of regular graphs that are not necessarily strongly regular, but do contain many strongly regular vertices. We also make several conjectures and find all regular graphs on at most ten vertices with at least one strongly regular vertex.

Given \(S\) a benzenoid system, we find an expression of the second order Randić index, denoted by \(\mathop{^2\chi}(S)\), in terms of inlet features of \(S\). As a consequence, we classify benzenoid systems with equal \(\mathop{^2\chi}\) and then find the minimal and maximal value over the set of catacondensed systems.

Let \(m_1, m_2, \ldots, m_r\) be positive integers with \(m_i \geq 3\) for all \(i\). An \((m_1, m_2, \ldots, m_r)\)-cycle is defined as the edge-disjoint union of \(r\) cycles of lengths \(2m_1, 2m_2, \ldots, 2m_r\). An \((m_1, m_2, \ldots, m_r)\)-cycle system of the complete graph \(K_n\) is a decomposition of \(K_n\) into \((m_1, m_2, \ldots, m_r)\)-cycles.

In this paper, the necessary and sufficient conditions for the existence of an \((m_1, m_2, \ldots, m_r)\)-cycle system of \(K_n\) are given, where \(m_i\) \((1 \leq i \leq r)\) are odd integers with \(3 \leq m_i \leq n\) and \(\sum_{i=1}^r m_i = 2^k\) for \(k \geq 3\). Moreover, the complete graph with a \(1\)-factor removed \(K_n – F\) has a similar result.

We refer to a labeling of a plane graph as a d-antimagic labeling if the vertices, edges and faces of the graph are labeled in such a way that the label of a face and the labels of vertices and edges surrounding that face add up to a weight of the face and the weights
of faces constitute an arithmetical progression of difference \(d\). In this paper we deal with \(d\)-antimagic labeling of prisms.

We show that the classical Ramsey number \(R(3,3,3,3)\) is no greater than \(62\). That is, any edge coloring with four colors of a complete graph on \(62\) vertices must contain a monochromatic triangle. Basic notions and a historical overview are given along with the theoretical framework underlying the main result. The algorithms for the computational verification of the result are presented along with a brief discussion of the software tools that were utilized.

We show that certain subsets of \(\mathbf{F}_q\)-rational points of the curve \(XZ^{n-1} = Y^n\) are dense sets in \(\mathbf{P}^2(\mathbf{F}_q)\).

H. Kharaghani, in “Arrays for orthogonal designs” \((2000)\), \(\textit{J. Combin. Designs}\), \(8 (2000), 166-173\), showed how to use amicable sets of matrices to construct orthogonal designs in orders divisible by eight. We show how amicable orthogonal designs can be used to make amicable sets and so obtain infinite families of orthogonal designs in six variables in orders divisible by eight.

Let \(G\) and \(H\) be a pair of non-isomorphic graphs on fewer than \(m\) vertices. In this paper, we introduce several new problems about decomposing the complete graph \(K_m\) into copies of \(G\) and \(H\). We will assume that at least one of \(G\) or \(H\) is not a cycle. We also begin to examine variations to the problems of subgraph packing, covering, and factorization.

For vertices \(u\) and \(v\) in a connected graph \(G\) with vertex set \(V\), the distance \(d(u,v)\) is the length of a shortest \(u – v\) path in \(G\). A \(u – v\) path of length \(d(u,v)\) is called a \(u – v\) geodesic. The closed interval \(I[u,v]\) consists of \(u\), \(v\), and all vertices that lie in some \(u – v\) geodesic of \(G\); while for \(S \subseteq V\), \(I[S]\) is the union of closed intervals \(I[u,v]\) for all \(u,v \in S\). A set \(S\) of vertices is a geodetic set if \(I[S] = V\), and the minimum cardinality of a geodetic set is the geodetic number \(g(G)\). For vertices \(x\) and \(y\) in \(G\), the detour distance \(D(x, y)\) is the length of a longest \(x – y\) path in \(G\). An \(x – y\) path of length \(D(x, y)\) is called an \(x – y\) detour. The closed detour interval \(I_D[x,y]\) consists of \(x\), \(y\), and all vertices in some \(x – y\) detour of \(G\). For \(S \subseteq V\), \(I_D[S]\) is the union of \(I_D[x,y]\) for all \(x,y \in S\). A set \(S\) of vertices is a detour set if \(I_D[S] = V\), and the minimum cardinality of a detour set is the detour number \(dn(G)\). We study relationships that can exist between minimum detour sets and minimum geodetic sets in a graph. A graph \(F\) is a minimum detour subgraph if there exists a graph \(G\) containing \(F\) as an induced subgraph such that \(V(F)\) is a minimum detour set in \(G\). It is shown that \(K_3\) and \(P_3\) are minimum detour subgraphs. It is also shown that for every pair \(a,b \geq 2\) of integers, there exists a connected graph \(G\) with \(dn(G) = a\) and \(g(G) = b\).