The alliance polynomial of a graph with order \(n\) and maximum degree \(\Delta\) is the polynomial \(A(\Gamma; x) = \sum_{k=-\delta_1}^{\delta_1}A_k(\Gamma) x^{n+k}\), where \(A_k(G)\) is the number of exact defensive \(k\)-alliances in \(G\). We provide an algorithm for computing the alliance polynomial. Furthermore, we obtain some properties of \(A(\Gamma; x)\) and its coefficients. In particular, we prove that the path, cycle, complete, and star graphs are characterized by their alliance polynomials. We also show that the alliance polynomial characterizes many graphs that are not distinguished by other usual polynomials of graphs.

Let \(a\), \(b\), and \(k\) be three nonnegative integers with \(a \geq 2\) and \(b \geq a(k+1)+2\). A graph \(G\) is called a \(k\)-Hamiltonian graph if \(G – U\) contains a Hamiltonian cycle for every subset \(U \subseteq V(G)\) with \(|U| = k\). An \([a, b]\)-factor \(F\) of \(G\) is called a Hamiltonian \([a, b]\)-factor if \(F\) contains a Hamiltonian cycle. If \(G – U\) has a Hamiltonian \([a, b]\)-factor for every subset \(U \subseteq V(G)\) with \(|U| = k\), then we say that \(G\) admits a \(k\)-Hamiltonian \([a, b]\)-factor. Suppose that \(G\) is a \(k\)-Hamiltonian graph of order \(n\) with \(n \geq a+k+2\). In this paper, it is proved that \(G\) includes a \(k\)-Hamiltonian \([a, b]\)-factor if \(\delta(G) \geq a+k\) and \(t(G) \leq a-1+\frac{(a-1)(k+1)}{b-2}\).

Graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. An embedding \(f\) of a guest graph \(G\) into a host graph \(H\) is a bijection on the vertices such that each edge of \(G\) is mapped into a path of \(H\). In this paper, we introduce a graph called the generalized book and the main results obtained are: (1) For \(r \geq 3\), the minimum wirelength of embedding \(r\)-dimensional hypercube \(Q_r\) into the generalized book \(\mathrm{GB}[2^{r_1}, 2^{r_2}, 2^{r_3}]\), where \(r_1 + r_2 + r_3 = r\). (2) A linear time algorithm to compute the exact wirelength of embedding hypercube into generalized book. (3) An algorithm for embedding hypercube into generalized book with dilation 3, proving that the lower bound obtained by Manuel et al. [28] is sharp.

In this paper, we present a new approach to the convolved Fibonacci numbers arising from the generating function of them and give some new and explicit identities for the convolved Fibonacci numbers.

The generalized Fibonacci cube \(Q_d(f)\) is the graph obtained from the hypercube \(Q_d\) by removing all vertices that contain a given binary word \(f\). A binary word \(f\) is called good if \(Q_d(f)\) is an isometric subgraph of \(Q_d\) for all \(d \geq 1\), and bad otherwise. A non-extendable sequence of contiguous equal digits in a word \(f\) is called a block of \(f\). The question to determine the good (bad) words consisting of at most three blocks was solved by Ilié, Klavžar, and Rho. This question is further studied in the present paper. All the good (bad) words consisting of four blocks are determined completely, and all bad \(2\)-isometric words among consisting of at most four blocks words are found to be \(1100\) and \(0011\).

In this paper, we provide a construction of \(\mathrm{PG}(2,4)\) by a collage of \(\mathrm{AG}(2,3)\) and its dual \(\mathrm{DAG}(2,3)\). Moreover, we prove that the construction is unique.

In this paper, we first present a combinatorial proof of the recurrence relation about the number of the inverse-conjugate compositions of \(2n+1\), \(n > 1\). And then we get some counting results about the inverse-conjugate compositions for special compositions. In particular, we show that the number of the inverse-conjugate compositions of \(4k+1\), \(k > 0\) with odd parts is \(2^k\), and provide an elegant combinatorial proof. Lastly, we give a relation between the number of the inverse-conjugate odd compositions of \(4k+1\) and the number of the self-inverse odd compositions of \(4k+1\).

In this study, by using Jacobsthal and Jacobsthal Lucas matrix sequences, we define \(k\)-Jacobsthal and \(k\)-Jacobsthal Lucas matrix sequences depending on one parameter \(k\). After that, by using two parameters \((s,t)\), we define \((s,t)\)-Jacobsthal and \((s,t)\)-Jacobsthal Lucas matrix sequences. And then, we establish combinatoric representations of all of these matrices.

A graph \(G\) is \(1\)-planar if it can be embedded in the plane \(\mathbb{R}^2\) so that each edge of \(G\) is crossed by at most one other edge. In this paper, we show that each \(1\)-planar graph of maximum degree \(\Delta\) at least \(7\) with neither intersecting triangles nor chordal \(5\)-cycles admits a proper edge coloring with \(\Delta\) colors.

Dirac showed that in a \((k-1)\)-connected graph there is a path through each \(k\) vertices. The path \(k\)-connectivity \(\pi_k(G)\) of a graph \(G\), which is a generalization of Dirac’s notion, was introduced by Hager in 1986. Recently, Mao introduced the concept of path \(k\)-edge-connectivity \(\omega_k(G)\) of a graph \(G\). Denote by \(G \circ H\) the lexicographic product of two graphs \(G\) and \(H\). In this paper, we prove that \(\omega_4(G \circ H) \geq \omega_4(G) |V(H)|\) for any two graphs \(G\) and \(H\). Moreover, the bound is sharp.