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 connected component has at least two vertices. A graph \(G\) is called \(\lambda’\)-optimal if \(\lambda'(G) = \min\{d_G(u)+d_G(v)-2: uv \text{ is an edge in } G\}\). This paper proves that for any \(d\) and \(n\) with \(d \geq 2\) and \(n\geq 1\) the Kautz undirected graph \(UK(d, 1)\) is \(\lambda’\)-optimal except \(UK(2,1)\) and \(UK(2,2)\) and, hence, is super edge-connected except \(UK(2, 2)\).

In a \((k, d)\)-relaxed coloring game, two players, Alice and Bob, take turns coloring the vertices of a graph \(G\) with colors from a set \(C\) of \(k\) colors. A color \(c\) is legal for an uncolored vertex (at a certain step) means that after coloring \(x\) with color \(i\), the subgraph induced by vertices of color \(i\) has maximum degree at most \(d\). Each player can only color a vertex with a legal color. Alice’s goal is to have all the vertices colored, and Bob’s goal is the opposite: to have an uncolored vertex without legal color. The \(d\)-relaxed game chromatic number of a graph \(G\), denoted by \(\chi^{(d)}_g(G)\) is the least number \(k\) so that when playing the \((k,d)\)-relaxed coloring game on \(G\), Alice has a winning strategy. This paper proves that if \(G\) is an outer planar graph, then \(\chi^{(d)}_g(G) \leq 7 – d\) for \(d = 0, 1, 2, 3, 4\).

A graph \(G\) is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let \(X\) be a 2-stratified graph with one fixed blue vertex \(v\) specified. We say that \(X\) is rooted at \(v\). The \(X\)-domination number of a graph \(G\) is the minimum number of red vertices of \(G\) in a red-blue coloring of the vertices of \(G\) such that every blue vertex \(uv\) of \(G\) belongs to a copy of \(X\) rooted at \(v\). In this paper we investigate the \(X\)-domination number of prisms when \(X\) is a 2-stratified 4-cycle rooted at a blue vertex.

The maximum possible volume of a simple, non-Steiner \((v, 3, 2)\) trade was determined for all \(v\) by Khosrovshahi and Torabi (Ars Combinatoria \(51 (1999), 211-223)\); except that in the case \(v \equiv 5\) (mod 6), \(v \geq 23\), they were only able to provide an upper bound on the volume. In this paper we construct trades with volume equal to that bound for all \(v \equiv 5\) (mod 6), thus completing the problem.

For a positive integer \(n\), let \(G\) be \(K_n\) if \(n\) is odd and \(K_n\) less a one-factor if \(n\) is even. In this paper it is shown that, for non-negative integers \(p\), \(q\) and \(r\), there is a decomposition of \(G\) into \(p\) \(4\)-cycles, \(q\) \(6\)-cycles and \(r\) \(8\)-cycles if \(4p + 6q + 8r = |E(G)|\), \(q = 0\) if \(n < 6\), and \(r = 0\) if \(n < 8\).

This paper introduces a bijection between RNA secondary structures and bicoloured ordered trees.

For a given triangle \(T\), consider the problem of finding a finite set \(S\) in the plane such that every two-coloring of \(S\) results in a monochromatic set congruent to the vertices of \(T\). We show that such a set \(S\) must have at least seven points. Furthermore, we show by an example that the minimum of seven is achieved.

The two games considered are mixtures of Searching and Cops and Robber. The cops have partial information, provided first via selected vertices of a graph, and then via selected edges. This partial information includes the robber’s position, but not the direction in which he is moving. The robber has perfect information. In both cases, we give bounds on the amount of such information required by a single cop to guarantee the capture of the robber on a cop-win graph.

Let \(K_v\) be the complete multigraph with \(v\) vertices. Let \(G\) be a finite simple graph. A \(G\)-design of \(K_v\), denoted by \(G\)-GD(\(v\)), is a pair of (\(X\), \(\mathcal{B}\)), where \(X\) is the vertex set of \(K_v\), and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly one block of \(\mathcal{B}\). In this paper, the discussed graphs are sixteen graphs with six vertices and seven edges. We give a unified method for constructing such \(G\)-designs.

Graceful labellings have both a mathematical beauty in their own right and considerable connections with pure and applied combinatorics (edge-decomposition of graphs, coding systems, communication networks, etc.). In the present paper, we exhibit a graceful labelling for each generalized Petersen graph \(P_{8t,3}\) with \(t \geq 1\). As a consequence, we obtain, for any fixed \(t\), a cyclic edge-decomposition of the complete graph \(K_{48t+1}\) into copies of \(P_{8t,3}\). Due to its extreme versatility, the technique employed looks promising for finding new graceful labellings, not necessarily involving generalized Petersen graphs.

A graph on \(n\) vertices having no vertex of degree greater than \(f\), \(2 \leq f \leq n – 2\), is called an \(f\)-graph of order \(n\). For a given \(f\), the vertices of degree less than \(f\) are called orexic. An \(f\)-graph to which no edge can be added without violating the \(f\)-degree restriction is called an edge maximal \(f\)-graph (EM \(f\)-graph). An upper bound, as a function of \(n\) and \(f\), for the number of orexic vertices in an EM \(f\)-graph and the structure of the subgraph induced by its orexic vertices is given. For any \(n\) and \(f\), the maximum size, minimum size, and realizations of extremal size EM \(f\)-graphs having \(m\) orexic vertices and order \(n\) are obtained. This is also done for any given \(n\) and \(f\) independent of \(m\). The number of size classes of EM \(f\)-graphs of order \(n\) and fixed \(m\) is determined. From this, the maximum number of size classes over all \(m\) follows. These results are related to the study of \((f + 1)\)-star-saturated graphs.

We give a decomposition formula for the edge zeta function of a regular covering \(\overrightarrow{G}\) of a graph \(G\). Furthermore, we present a determinant expression for some \(Z\)-function of an oriented line graph \(\overrightarrow{L}(G)\) of \(G\). As a corollary, we obtain a factorization formula for the edge zeta function of \(\overrightarrow{G}\) by \(L\)-functions of \(\overrightarrow{L}(G)\).

A hamiltonian graph \(G\) is panpositionable if for any two different vertices \(x\) and \(y\) of \(G\) and any integer \(k\) with \(d_G(x,y) \leq k \leq |V(G)|/2\), there exists a hamiltonian cycle \(C\) of \(G\) with \(d_C(x,y) = k\). A bipartite hamiltonian graph \(G\) is bipanpositionable if for any two different vertices \(x\) and \(y\) of \(G\) and for any integer \(k\) with \(d_G(x,y) \leq k \leq |V(G)|/2\) and \((k – d_G(x,y))\) is even, there exists a hamiltonian cycle \(C\) of \(G\) such that \(d_C(x,y) = k\). In this paper, we prove that the hypercube \(Q_n\) is bipanpositionable hamiltonian if and only if \(n \geq 2\). The recursive circulant graph \(G(n;1,3)\) is bipanpositionable hamiltonian if and only if \(n \geq 6\) and \(n\) is even; \(G(n; 1,2)\) is panpositionable hamiltonian if and only if \(n \in \{5,6,7,8,9, 11\}\), and \(G(n; 1, 2,3)\) is panpositionable hamiltonian if and only if \(n \geq 5\).

The lower domination number of a digraph \(D\), denoted by \(\gamma(D)\), is the least number of vertices in a set \(S\), such that \(O[S] = V(D)\). A set \(S\) is irredundant if for all \(x \in S\), \(|O[x] – O[S – x]| \geq 1\). The lower irredundance number of a digraph, denoted \(ir(D)\), is the least number of vertices in a maximal irredundant set. A Gallai-type theorem has the form \(x(G) + y(G) = n\), where \(x\) and \(y\) are parameters defined on \(G\), and \(n\) is the number of vertices in the graph. We characterize directed trees satisfying \(\gamma(D) + \Delta_+(D) = n\) and directed trees satisfying \(ir(D) + \Delta_+(D) = n\).

We introduce a new concept of strong domination and connected strong domination in hypergraphs. The relationships between strong domination number and other hypergraph parameters like domination, independence, strong independence and irredundant numbers of hypergraphs are considered. There are also some chains of inequalities generalizing the famous Cockayne, Hedetniemi and Miller chain for parameters of graphs. There are given some generalizations of well known theorems for graphs, namely Gallai type theorem generalizing Nieminen, Hedetniemi and Laskar theorems.

The vertex linear arboricity \(vla(G)\) of a graph \(G\) is the minimum number of subsets into which the vertex set \(V(G)\) can be partitioned so that each subset induces a subgraph whose connected components are paths. In this paper, we seek to convert vertex linear arboricity into its fractional analogues, i.e., the fractional vertex linear arboricity of graphs. Let \(\mathbb{Z}_n\) denote the additive group of integers modulo \(n\). Suppose that \(C \subseteq \mathbb{Z}_n \backslash 0\) has the additional property that it is closed under additive inverse, that is, \(-c \in C\) if and only if \(c \in C\). A circulant graph is the graph \(G(\mathbb{Z}_n, C)\) with the vertex set \(\mathbb{Z}_n\) and \(i, j\) are adjacent if and only if \(i – j \in C\). The fractional vertex linear arboricity of the complete \(n\)-partite graph, the cycle \(C_n\), the integer distance graph \(G(D)\) for \(D = \{1, 2, \ldots, m\}\), \(D = \{2, 3, \ldots, m\}\) and \(D = P\) the set of all prime numbers, the Petersen graph and the circulant graph \(G(\mathbb{Z}_a, C)\) with \(C = \{-a + b, \ldots, -b, b, \ldots, a – b\}\) (\(a – 2b \geq b – 3 \geq 3\)) are determined, and an upper and a lower bounds of the fractional vertex linear arboricity of Mycielski graph are obtained.

Deciding whether a graph can be partitioned into \(k\) vertex-disjoint paths is a well-known NP-complete problem. In this paper, we give new sufficient conditions for a bipartite graph to be partitionable into \(k\) vertex-disjoint paths. We prove the following results for a simple bipartite graph \(G = (V_1, V_2, E)\) of order \(n\):(i) For any positive integer \(k\), if \(\|V_1| – |V_2\| \leq k\) and \(d_G(x) + d_G(y) \geq \frac{n-k+1}{2}\) for every pair \(x \in V_1\) and \(y \in V_2\) of nonadjacent vertices of \(G\), then \(G\) can be partitioned into \(k\) vertex-disjoint paths, unless \(k = 1\), \(|V_1| = |V_2| = \frac{n}{2}\) and \(G = K_{s,s} \cup K_{\frac{n}{2} – s, \frac{n}{2} – s} \cup K_{2, 2}\), where \(1 \leq k \leq \frac{n}{2} – 1\);(ii) For any two positive integers \(p_1\) and \(p_2\) satisfying \(n = p_1 + p_2\), if \(G\) does not belong to some easily recognizable classes of exceptional graphs, \(\|V_1| – |V_2\| \leq 2\) and \(d_G(x) + d_G(y) = \frac{n-1}{2}\) for every pair \(x \in V_1\) and \(y \in V_2\) of nonadjacent vertices of \(G\), then \(G\) can be partitioned into two vertex-disjoint paths \(P_{1}\) and \(P_{2}\) of order \(p_1\) and \(p_2\), respectively.These results also lead to new sufficient conditions for the existence of a Hamilton path in a bipartite graph.

In this paper we compute the chirality group, the chirality index and the smallest regular coverings of the chiral Coxeter maps, the toroidal orientably regular maps described in Coxeter and Moser monograph [H.S.M.Coxeter and W.O.J.Moser,Generation and Relations Discrete Group(4th ed.),Springer-varlag,Berlin,1984]. We also compute the greatest regular maps covered by chiral Coxeter maps.

We observe that a lobster with diameter at least five has a unique path \(x_0, x_1, \ldots, x_{m}\) (called the central path) such that \(x_p\) and \(x_m\) are adjacent to the centers of at least one \(K_{1,s}\), \(s > 0\), and besides adjacencies in the central path each \(x_i\), \(1 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), \(s \geq 0\). In this paper we give graceful labelings to some new classes of lobsters with diameter at least five, in which the degree of the vertex \(x_m\) is odd and the degree of each of the remaining vertices on the central path is even. The main idea used to obtain these graceful lobsters is to form a diameter four tree \(T(L)\) from a lobster \(L\) of certain type, give a graceful labeling to \(T(L)\) and finally get a graceful labeling of \(L\) by applying component moving and inverse transformations.

A graph \(G = (V, E)\) is said to be super edge-magic if there exists a one-to-one correspondence \(A\) from \(V \cup E\) onto \(\{1, 2, 3, \ldots, |V| + |E|\}\) such that \(\lambda(V) = \{1, 2, \ldots, |V|\}\) and \(\lambda(x) + \lambda(xy) + \lambda(y)\) is constant for every edge \(xy\).In this paper, given a positive integer \(k\) (\(k \geq 6\)), we use the partitions of \(k\) having three distinct parts to construct infinitely many super edge-magic graphs without isolated vertices with edge magic number \(k\). Especially, we use this method to find graphs with the maximum number of edges among the super edge-magic graphs with \(v\) vertices. In addition, we investigate whether or not some interesting families of graphs are super edge-magic.

A vertex \(w\) in a di(graph) \(G\) is said to resolve a pair \(u, v\) of vertices of \(G\) if the distance from \(u\) to \(w\) does not equal the distance from \(v\) to \(w\). A set \(S\) of vertices of \(G\) is a resolving set for \(G\) if every pair of vertices of \(G\) is resolved by some vertex of \(S\). The smallest cardinality of a resolving set for \(G\), denoted by \(dim(G)\), is called the metric dimension for \(G\).

We show that if \(G\) is the Cayley digraph \(Cay(\Delta : \Gamma)\) where \(\Delta = \{ (1, 0, 0), (0, 1, 0), (0, 0, 1) \}\) and \(\Gamma =\mathbb{Z}_m \oplus \mathbb{Z}_n \oplus \mathbb{Z}_k\) with \(m \leq n \leq k\), then \(dim(G) = n\) if \(m < n\) and improve known upper bounds if \(m = n\). We use these results to establish improved upper bounds for the metric dimension of Cayley digraphs of abelian groups that are expressed as a direct product of four or more cyclic groups. Lower bounds for Cayley digraphs of groups that are multiple copies of \(\mathbb{Z}_n\) are established.

In this paper, the unimodality of \((r,\beta)\)-Stirling numbers and certain asymptotic approximation of \((r,\beta)\)-Bell numbers are established. Together with these results and the most general form of Central Limit Theorem, viz. Bounded Variance Normal Convergence Criterion, the \((r,\beta)\)-Stirling numbers are shown to be asymptotically normal.

The graph \(\mathcal{R}(d)\) of realizations of \(d\) is a graph whose vertices are the graphs with degree sequence \(d\), two vertices are adjacent in the graph \(\mathcal{R}(d)\) if one can be obtained from the other by a switching. It has been shown that the graph \(\mathcal{R}(d)\) is connected. Let \(\mathcal{CR}(d)\) be the set of connected graphs with degree sequence \(d\). Taylor \([13]\) proved that the subgraph of \(\mathcal{R}(d)\) induced by \(\mathcal{CR}(d)\) is connected. Several connected subgraphs of \(\mathcal{CR}(d)(3^n)\) are obtained in this paper. As an application, we are able to obtain the interpolation and extremal results for the number of maximum induced forests in the classes of connected subgraphs of \(\mathcal{CR}(d)(3^n)\).

Let \(T = (V, A)\) be a finite tournament with \(n \geq 2\) vertices. The dual of T is the tournament \(T^* = (V, A^*)\) defined by: for all \(x,y \in V, (x,y) \in A^*\) if and only if \((y,x) \in A\). The tournament \(T\) is critical if \(T\) is indecomposable and if for all \(x \in V\), the subtournament \(T(V – \{x\})\) is decomposable. A \(3\)-cycle is a tournament isomorphic to the tournament \(T, = ({0,1,2}, {(0, 1), (1, 2), (2, 0)})\). Let \(F\) be a set of non negative integers \(k < n\). The tournament \(T\) is \(F\)-selfdual if for every subset \(X\) of \(V\) such that \(|X |\in F\), the subtournaments \(T(X)\) and \(T^*(X)\) are isomorphic. In this paper, we study, for each integer \(k \geq 1\), the \(\{n – k\}\)-selfduality of the tournaments, with \(n \geq 4+k\) vertices, that are lexicographical sums of tournaments under a \(3\)-cycle or a critical tournament. As application, we determine for each integer \(k \geq 1\), the tournaments, with \(n \geq 4+ k\) vertices, that are \(\{4,n – k\}\)-selfdual.

This paper studies in detail the collection of closed sets of a matroid of arbitrary cardinality ordered by inclusion. The relation between the collection, in particular the collection of a simple matroid, and a finite length geometric lattice is dealt with. Finally, one obtains that up to isomorphism, a finite length geometric lattice is a simple matroid, and vice versa.

A vertex set \(D\) of a graph \(G\) is a dominating set if every vertex not in \(D\) is adjacent to some vertex in \(D\). The domination number \(\gamma\) of a graph \(G\) is the minimum cardinality of a dominating set in \(G\).

In 1975, Payan \([6]\) communicated without proof the inequality
\[2\gamma \leq {n} + 1 – \delta\]
for every connected graph not isomorphic to the complement of a one-regular graph, where \(n\) is the order and \(\delta\) the minimum degree of the graph. A first proof of (*) was published by Flach and Volkman \([3]\) in \(1980\).

In this paper, we firstly present a more transparent proof of (*). Using the idea of this proof, we show that

\[2\gamma \leq n – \delta\]

for connected graphs with exception of well-determined families of graphs.