In this paper, we consider the relationships between the sums of the generalized order-\(k\) Fibonacci and Lucas numbers and \(1\)-factors of bipartite graphs.

The current paper deals with two special matrices \(T_n\) and \(W_n\) related to the Pascal, Vandermonde, and Stirling matrices. As a result, various properties of the entries of \(T_n\) and \(W_n\) are obtained, including the generating functions, recurrence relations, and explicit expressions. Some additional results are also presented.

There are some results and many conjectures with the conclusion that a graph \(G\) contains all trees of given size \(k\). We prove some new results of this type.

In \([3]\), we gave a factorization of the generalized Lah matrix.In this short note, we show its another factorization. From this factorization, several interesting combinatorial identities involving the Fibonacci numbers are obtained.

Let \(\lambda K_v\) be the complete multigraph with \(v\) vertices. Let \(G\) be a finite simple graph. A \(G\)-decomposition of \(K_v\), denoted by \(G-GD_\lambda(v)\), is a pair \((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, nine graphs \(G_i\) with six vertices and nine edges are discussed, and the existence of \(G_i-GD_\lambda(v)\) is given, \(1 \leq i \leq 9\).

Let \(G = (V, E)\) be a graph. A set \(S \subseteq V\) is a restrained dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V – S\). The restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the smallest cardinality of a restrained dominating set of \(G\). It is known that if \(T\) is a tree of order \(n\), then \(\gamma_r(T) \geq \left\lceil \frac{n+2}{3} \right\rceil\). In this note, we provide a simple constructive characterization of the extremal trees \(T\) of order \(n\) achieving this lower bound.

Given non-negative integers \(r, s\), and \(t\), an \([r, s, t]\)-coloring of a graph \(G = (V(G), E(G))\) is a mapping \(c\) from \(V(G) \cup E(G)\) to the color set \(\{0, 1, \ldots, k-1\}\) such that \(|c(v_i) – c(v_j)| \geq r\) for every two adjacent vertices \(v_i, v_j\), \(|c(e_i) – c(e_j)| \geq s\) for every two adjacent edges \(e_i, e_j\), and \(|c(v_i) – c(e_i)| \geq t\) for all pairs of incident vertices and edges, respectively. The \([r, s, t]\)-chromatic number \(\chi_{r,s,t}(G)\) of \(G\) is defined to be the minimum \(k\) such that \(G\) admits an \([r, s, t]\)-coloring. We prove that \(\chi_{1,1,2}(K_5) = 7\) and \(\chi_{1,1,2}(K_6) = 8\).

We determine a recursive formula for the number of rooted complete \(N\)-ary trees with \(n\) leaves, which generalizes the formula for the sequence of Wedderburn-Etherington numbers. The diagonal sequence of our new sequences equals the sequence of numbers of rooted trees with \(N + 1\) vertices.

In this paper, we determine the conics characterizing the generalized Fibonacci and Lucas sequences with indices in arithmetic progressions, generalizing work of Melham and McDaniel.

A graph \(G = (V, E)\) is a mod sum graph if there exists a positive integer \(z\) and a labeling, \(\lambda\), of the vertices of \(G\) with distinct elements from \(\{1, 2, \ldots, z-1\}\) such that \(uv \in E\) if and only if the sum, modulo \(z\), of the labels assigned to \(u\) and \(v\) is the label of a vertex of \(G\). The mod sum number \(\rho(G)\) of a connected graph \(G\) is the smallest nonnegative integer \(m\) such that \(G \cup mK_1\), the union of \(G\) and \(m\) isolated vertices, is a mod sum graph. In Section \(2\), we prove that \(F_n\) is not a mod sum graph and give the mod sum number of \(F_n\) (\(n \geq 6\) is even). In Section \(3\), we give the mod sum number of the symmetric complete graph.

In this paper, we consider the effect of edge contraction on the domination number and total domination number of a graph. We define the (total) domination contraction number of a graph as the minimum number of edges that must be contracted in order to decrease the (total) domination number. We show that both of these two numbers are at most three for any graph. In view of this result, we classify graphs by their (total) domination contraction numbers and characterize these classes of graphs.

In this paper, connected graphs with the largest Laplacian eigenvalue at most \(\frac{5+\sqrt{13}}{2}\) are characterized. Moreover, we prove that these graphs are determined by their Laplacian spectrum.

An extended directed triple system of order \(v\) with an idempotent element (EDTS(\(v, a\))) is a collection of triples of the type \([x, y, z]\), \([x, y, x]\) or \((x, x, x)\) chosen from a \(v\)-set, such that every ordered pair (not necessarily distinct) belongs to only one triple and there are \(a\) triples of the type \((x, x, x)\). If such a design with parameters \(v\) and \(a\) exists, then it will have \(b_{v,a}\) blocks, where \(b_{v,a} = (v^2 + 2a)/3\). A necessary and sufficient condition for the existence of EDTS(\(v, 0\)) and EDTS(\(v, 1\)) are \(v \equiv 0 \pmod{3}\) and \(v \not\equiv 0 \pmod{3}\), respectively. In this paper, we have constructed two EDTS(\(v, a\))’s such that the number of common triples is in the set \(\{0, 1, 2, \ldots, b_{v,a} – 2, b_{v,a}\}\), for \(a = 0, 1\).

As applications of the Anzahl theorems in finite orthogonal spaces, we study the critical problem of totally isotropic subspaces, and obtain the critical exponent.

Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is chromatically unique if for any graph \(H\), \(P(H,\lambda) = P(G, \lambda)\) implies H is isomorphic to \(G\). In this paper, we study the chromaticity of Turén graphs with deleted edges that induce a matching or a star. As a by-product, we obtain new families of chromatically unique graphs.

Let \(\{w_n\}\) be a second-order recurrent sequence. Several identities about the sums of products of second-order recurrent sequences were obtained and the relationship between the second-order recurrent sequences and the recurrence coefficient revealed. Some identities about Lucas sequences, Lucas numbers, and Fibonacci numbers were also obtained.

In this paper, we prove that for any positive integers \(k,n\) with \(k \geq 2\) , the graph \(P_k^n\) is a divisor graph if and only if \(n \leq 2k + 2\) , where \(P^k_n\) is the \(k\) th power of the path \(P_n\). For powers of cycles we show that \(C^k_n\) is a divisor graph when \(n \leq 2k + 2\), but is not a divisor graph when \(n \geq 2k + 2\),but is not a divisor graph when \(n\geq 2k+\lfloor \frac{k}{2}\rceil,\) where \(C^k_n\) is the \(k\)th power of the cycle \(C_n\). Moreover, for odd \(n\) with \(2k+2 < n < 2k + \lfloor\frac{k}{2}\rfloor + 3\), we show that the graph \(C^k_n\) is not a divisor graph.

The Wiener index of a graph \(G\) is defined as \(W(G) = \sum_{u,v \in V(G)} d_G(u,v),\) where \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G\) and the sum goes over all pairs of vertices. In this paper, we investigate the Wiener index of unicyclic graphs with given girth and characterize the extremal graphs with the minimal and maximal Wiener index.

In this paper, we consider a random mapping, \(\hat{T}_n\), of the finite set \(\{1,2,\ldots,n\}\) into itself for which the digraph representation \(\hat{G}_n\) is constructed by:\((1)\) selecting a random number, \(\hat{L}_n\), of cyclic vertices,\((2)\) constructing a uniform random forest of size \(n\) with the selected cyclic vertices as roots, and \((3)\) forming `cycles’ of trees by applying a random permutation to the selected cyclic vertices.We investigate \(\hat{k}_n\), the size of a `typical’ component of \(\hat{G}_n\), and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of \(k\), conditioned on \(\hat{L}_n = m(n)\). As an application of our results, we show in Section \(3\) that provided \(\hat{L}_n\) is of order much larger than \(\sqrt{n}\), then the joint distribution of the normalized order statistics of the component sizes of \(\hat{G}_n\) converges to the Poisson-Dirichlet \((1)\) distribution as \(n \to \infty\). Other applications and generalizations are also discussed in Section \(3\).

De Bruijn digraphs and shuffle-exchange graphs are useful models for interconnection networks. They can be represented as group action graphs of the wrapped butterfly graph and the cube-connected cycles, respectively. The Kautz digraph has similar definitions and properties to de Bruijn digraphs. It is \(d\)-regular and strongly \(d\)-connected, thus it is a group action graph. In this paper, we use another representation of the Kautz digraph and settle the open problem posed by M.-C. Heydemann in \([6]\).

We discuss the use of \(K\)-terminal networks to represent arbitrary clutters. A given clutter has many different representations, and there does not seem to be any set of simple transformations that can be used to transform one representation of a clutter into any other. We observe that for \(t \geq 2\) the class of clutters that can be represented using no more than \(t\) terminals is closed under minors, and has infinitely many forbidden minors.

Brenti (J. Combin. Theory Ser. A \(91 (2000))\) considered a \(q\)-analogue of the Eulerian polynomials by enumerating permutations in the symmetric group \(S_n\) with respect to the numbers of excedances and cycles. Here we establish a connection between these \(q\)-Eulerian polynomials and some infinite generating functions.

Let \(K_k, C_k, T_k\), and \(P_k\) denote a complete graph on \(k\) vertices, a cycle on \(k\) vertices, a tree on \(k+1\) vertices, and a path on \(k+1\) vertices, respectively. Let \(K_m-H\) be the graph obtained from \(K_m\) by removing the edges set \(E(H)\) of the graph \(H\) (\(H\) is a subgraph of \(K_m\)). A sequence \(S\) is potentially \(K_m-H\)-graphical if it has a realization containing a \(K_m-H\) as a subgraph. Let \(\sigma(K_m-H,n)\) denote the smallest degree sum such that every \(n\)-term graphical sequence \(S\) with \(\sigma(S) \geq \sigma(K_m-H,n)\) is potentially \(K_m-H\)-graphical. In this paper, we determine the values of \(\sigma(K_{r+1}-H,n)\) for \(n \geq 4r+10, r \geq 3, r+1 \geq k \geq 4\) where \(H\) is a graph on \(k\) vertices which contains a tree on \(4\) vertices but not contains a cycle on \(3\) vertices. We also determine the values of \(\sigma(K_{r+1}-P_{2},n)\) for \(n \geq 4r+8, r \geq 3\).

In this paper, the class of \((m,n)\)-ary hypermodules is introduced and several properties and examples are found. \((m,n)\)-ary hypermodules are a generalization of hypermodules. On the other hand, we can consider \((m,n)\)-ary hypermodules as a good generalization of \((m,n)\)-ary modules. We define the fundamental relation \(\epsilon^*\) on the \((m,n)\)-ary hypermodules \(M\) as the smallest equivalence relation such that \(M/\epsilon^*\) is an \((m,n)\)-ary module, and then some related properties are investigated.

For given graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1, G_2)\) is defined to be the least positive integer \(n\) such that every graph \(G\) on \(n\) vertices, either \(G\) contains a copy of \(G_1\) or the complement of \(G\) contains a copy of \(G_2\). In this note, we show that \(R(C_m, B_n) = 2m-1\) for \(m \geq 2n-1 \geq 7\). With the help of computers, we obtain the exact values of \(14\) small cycle-book Ramsey numbers.

For positive integers \(c \geq 0\) and \(k \geq 1\), let \(n = R(c, k)\) be the least integer, provided it exists, such that every \(2\)-coloring of the set \([1,n] = \{1,\ldots,n\}\) admits a monochromatic solution to the equation \(x + y+c = 4z\) with \(x, y, z \in [1,n]\). In this paper, the precise value of \(R(c, 4)\) is shown to be \(\left\lceil{3c + 2}/{8}\right\rceil\) for all even \(c \geq 34\).

Given a positive integer \(n\) such that \(-1\) is a quadratic residue mod \(n\), we give an algorithm that computes the integers \(u\) and \(v\) which satisfy the equation \(n = u^2 + v^2\). To do this, we use the group structure of the Modular group \(\Gamma= \text{PSL}(2,\mathbb{Z})\).

For a graph \(G = (V(G),E(G))\), a set \(S \subseteq V(G)\) is called a dominating set if \(N_G[S] = V(G)\). A dominating set \(S\) is said to be minimal if no proper subset \(S’ \subset S\) is a dominating set. Let \(\gamma(G)\) (called the domination number) and \(\Gamma(G)\) (called the upper domination number) be the minimum cardinality and the maximum cardinality of a minimal dominating set of \(G\), respectively. For a tree \(T\) of order \(n \geq 2\), it is obvious that \(1 = \gamma(K_{1,n-1}) \leq \gamma(T) \leq \Gamma(T) \leq \Gamma(K_{1,n-1}) = n-1\). Let \(t(n) = \min_{|T|=n}(\Gamma(T)-\gamma(T))\). In this paper, we determine \(t(n)\) for all natural numbers \(n\). We also characterize trees \(T\) with \(\Gamma(T) – \gamma(T) = t(n)\).

The signless \(r\)-associated Stirling numbers of the first kind \(d_r(n, k)\) counts the number of permutations of the set \(\{1,2,\ldots,n\}\) that have exactly \(k\) cycles, each of which is of length greater than or equal to \(r\), where \(r\)is a fixed positive integer. F. Brenti obtained that the generating polynomials of the numbers \(d_r(n, k)\) have only real zeros. Here we consider the location of zeros of these polynomials.

A kite-design of order \(n\) is a decomposition of the complete graph \(K_n\) into kites. Such systems exist precisely when \(n \equiv 0,1 \pmod{8}\). Two kite systems \((X,\mathcal{K}_1)\) and \((X,\mathcal{K}_2)\) are said to intersect in \(m\) pairwise disjoint blocks if \(|\mathcal{K}_1 \cap \mathcal{K}_2| = m\) and all blocks in \(\mathcal{K}_1 \cap \mathcal{K}_2\) are pairwise disjoint. In this paper, we determine all the possible values of \(m\) such that there are two kite-designs of order \(n\) intersecting in \(m\) pairwise disjoint blocks, for all \(n \equiv 0,1 \pmod{8}\).

In this note, we present some upper bounds for the \(k\)th largest eigenvalue of the adjacency matrix as well as the Laplacian matrix of graphs. Special attention is paid to the Laplacian matrix of trees.

Let \(P(G, \lambda)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent, written \(G \sim H\), if \(P(G, \lambda) = P(H, \lambda)\). A graph \(G\) is chromatically unique, written \(x\)-unique, if for any graph \(H\), \(G \sim H\) implies that \(G\) is isomorphic with \(H\). In this paper, we prove that the graph \(\theta(a_1, a_2, \ldots, a_6)\) is \(x\)-unique for exactly two distinct values of \(a_1, a_2, \ldots, a_6\).

In this paper, we give an explicit expression of the genus distributions of \(M_j^n\), for \(j = 1, 2, \ldots, 11\), which are introduced in the previous paper “Orientable embedding distributions by genus for certain types of non-planar graphs”. For a connected graph \(G = (V, E)\) with a cycle, let \(e\) be an edge on a cycle. By adding \(2n\) vertices \(u_1, u_2,u_3 \ldots, u_n, v_1, v_2,v_3 \ldots, v_n\) on \(e\) in sequence and connecting \(u_k, v_k\) for \(1 \leq k \leq n\), a non-planar graph \(G_n\) is obtained for \(n \geq 3\). Thus, the orientable embedding distribution of \(G_n\) by genus is obtained via the genus distributions of \(M_j^n\).

A graph \(G\) is \(N^m\)-locally connected if for every vertex \(v\) in \(G\), the vertices not equal to \(v\) and with distance at most \(m\) to \(v\) induce a connected subgraph in \(G\). In this note, we first present a counterexample to the conjecture that every \(3\)-connected, \(N^2\)-locally connected claw-free graph is hamiltonian and then show that both connected \(N^2\)-locally connected claw-free graph and connected \(N^3\)-locally connected claw-free graph with minimum degree at least three have connected even \([2, 4]\)-factors.

In J.-P. Serre’s \(Lettre \;à\; M. Tsfasman\) \([3]\), an interesting bound for the maximal number of points on a hypersurface of the \(n\)-dimensional projective space \(PG(n,q)\) over the Galois field \(GF(q)\) with \(q\) elements is given. Using essentially the same combinatorial technique as in \([3]\), we provide a bound which is relative to the maximal dimension of a subspace of \(PG(n,q)\) which is completely contained in the hypersurface. The lower that dimension, the better the bound. Next, by using a different argument, we derive a bound which is again relative to the maximal dimension of a subspace of \(PG(n, q)\) which is completely contained in the hypersurface, If that dimension increases for the latter case, the bound gets better.
As such, the bounds are complementary.

In this paper, it is shown that a variation of banana trees is odd graceful, and it is also proved that the variation of banana is graceful and \(\hat{p}\)-labeling in some cases.

In this paper, we consider the generalized Fibonacci and Pell Sequences and then show the relationships between the generalized Fibonacci and Pell sequences, and the Hessenberg permanents and determinants.

In this paper, a sequence representation of Dyck paths is presented, which yields a sequence representation of the Dyck path poset \({D}\) ordered by pattern containment. This representation makes it clear that the Dyck path poset \({D}\) takes the composition poset investigated by Sagan and Vatter as a subposet, and that the pattern containment order on Dyck paths exactly agrees with a generalized subword order also presented by Sagan and Vatter. As applications of the representation, we describe the Möbius function of \({D}\) and establish the Möbius inverse of the rank function of \({D}\) in terms of Dyck sequences. In the end, a Sperner and unimodal subposet of \({D}\) is given.

A graph is said to be determined by its adjacency spectrum (or to be a DS graph, for short) if there is no other non-isomorphic graph with the same adjacency spectrum. Although all connected graphs of index less than \(2\) are known to be determined by their adjacency spectra, the classification of DS graphs of index less than \(2\) is not complete yet. The purpose of this paper is to characterize all DS graphs of index less than \(2\) with no \(Z_n\) as a component.

Let \(B\) be a bipartite graph. We obtain two new results as follows:(1) Suppose that \(u \in V(B)\) is a vertex such that \(N_B(u)\) contains at least \(|N_B(u)| – 1\) odd vertices. Let \(f : V(B) \to \mathbb{N}\) be the function such that \(f(u) = 1\) and \(f(v) = \lceil d_B(v)/2 \rceil + 1\) for \(v \in V(B) \setminus u\). Then \(B\) is \(f\)-choosable.(2) Suppose that \(u \in V(B)\) is a vertex such that every vertex in \(N_B(u)\) is odd, and \(v \in V(B)\) is an odd vertex that is not adjacent to \(u\). Let \(f : V(B) \to \mathbb{N}\) be the function such that \(f(u) = 1\), \(f(v) = \lceil d_B(v)/2 \rceil\), and \(f(w) = \lceil d_B(w)/2 \rceil + 1\) for \(w \in V(B) \setminus \{u, v\}\). Then \(B\) is \(f\)-choosable.

Assume that \(G = (V, E)\) is an undirected and connected graph, and consider \(C \subseteq V\). For every \(v \in V\), let \(I_r(v) = \{u \in C: d(u,v) \leq r\}\), where \(d(u,v)\) denotes the number of edges on any shortest path between \(u\) to \(v\) in \(G\). If all the sets \(I_r(v)\) for \(v \in V\) are pairwise different, and none of them is the empty set, \(C\) is called an \(r\)-identifying code. In this paper, we consider \(t\)-vertex-robust \(r\)-identifying codes of level \(s\), that is, \(r\)-identifying codes such that they cover every vertex at least \(s\) times and the code is vertex-robust in the sense that \(|I_r(u) \Delta I_r(v)| \geq 2t+1\) for any two different vertices \(u\) and \(v\). Vertex-robust identifying codes of different levels are examined, in particular, of level \(3\). We give bounds (sometimes exact values) on the density or cardinality of the codes in binary hypercubes and in some infinite grids.

A clique \(C\) is an extreme clique of an interval graph \(G\) if there exists some interval model of \(G\) in which \(C\) is the first clique. A graph \(G\) is homogeneously clique-representable if all cliques of \(G\) are extreme cliques. In this paper, we present characterizations of extreme cliques and homogeneously clique-representable graphs.

In this note, we show that there is no \((945, 177, 33)\)-difference set in any group \(G\) of order \(945\) with a normal subgroup \(K\) such that \(G/K \cong \mathbb{C}_{27} \times \mathbb{C}_5\), and hence no cyclic difference set with such parameters exists. This fills one entry of Baumert and Gordon’s table with “No”.

The study of patterns in permutations is a very active area of current research. Klazar defined and studied an analogous notion of pattern for set partitions. We continue this work, finding exact formulas for the number of set partitions which avoid certain specific patterns. In particular, we enumerate and characterize those partitions avoiding any partition of a 3-element set. This allows us to conclude that the corresponding sequences are P-recursive. Finally, we define a second notion of pattern in a set partition, based on its restricted growth function. Related results are obtained for this new definition.

Let \(G = (V(G), E(G))\) be a graph with \(\delta(G) \geq 1\). A set \(D \subseteq V(G)\) is a paired-dominating set if \(D\) is a dominating set and the induced subgraph \(G[D]\) contains a perfect matching. The paired domination number of \(G\), denoted by \(\gamma_p(G)\), is the minimum cardinality of a paired-dominating set of \(G\). The paired bondage number, denoted by \(b_p(G)\), is the minimum cardinality among all sets of edges \(E’ \subseteq E\) such that \(\delta(G – E’) \geq 1\) and \(\gamma_p(G – E’) > \gamma_p(G)\). For any \(b_p(G)\) edges \(E’ \subseteq E\) with \(\delta(G – E’) \geq 1\), if \(\gamma_p(G – E’) > \gamma_p(G)\), then \(G\) is called uniformly pair-bonded graph. In this paper, we prove that there exists uniformly pair-bonded tree \(T\) with \(b_p(T) = k\) for any positive integer \(k\). Furthermore, we give a constructive characterization of uniformly pair-bonded trees.

A new construction of a B-T unital using Hermitian curves and certain hypersurfaces of \(\text{PG}(3,q^2)\) is presented. Some properties of an algebraic curve containing all points of a B-T unital are also examined.

A construction of optimal quaternary codes from symmetrical Balanced Incomplete Block (BIB) design \((4t – 1, 2t – 1, t – 1)\) is described.

For integers \(s,t \geq 1\), the Ramsey number \(R(s, t)\) is defined to be the least positive integer \(n\) such that every graph on \(n\) vertices contains either a clique of order \(s\) or an independent set of order \(t\). In this note, we derive new lower bounds for the Ramsey numbers: \(R(6,8) \geq 129\), \(R(7,9) \geq 235\) and \(R(8,17) \geq 937\). The new bounds are obtained with a constructive method proposed by Xu and Xie et al. and the help of computer algorithm.

We pursue the problem of counting the imbeddings of a graph in each of the orientable surfaces. We demonstrate how to achieve this for an iterated amalgamation of arbitrarily many copies of any graph whose genus distribution is known and further analyzed into a partitioned genus distribution. We introduce the concept of recombinant strands of face-boundary walks, and we develop the use of multiple production rules for deriving simultaneous recurrences. These two ideas are central to a broad-based approach to calculating genus distributions for graphs synthesized from smaller graphs.

The super (resp., edge-) connectivity of a connected graph is the minimum cardinality of a vertex-cut (resp., an edge-cut) whose removal does not isolate a vertex. In this paper, we consider the two parameters for a special class of graphs \(G(G_p,G_1; M)\), proposed by Chen et al [Applied Math. and Computation, \(140 (2003), 245-254]\), obtained from two \(k\)-regular \(k\)-connected graphs \(G_p\) and \(G_1\), with the same order by adding a perfect matching between their vertices. Our results improve ones of Chen et al. As applications, the super connectivity and the super edge-connectivity of the \(n\)-dimensional hypercube, twisted cube, cross cube, Möbius cube and locally twisted cube are all \(2n – 2\).