The half of an infinite lower triangular matrix \(G = (g_{n,k})_{n,k\geq 0}\) is defined to be the infinite lower triangular matrix \(G^{(1)} = (g^{(1)}_{n,k \geq 0})\) such that \(g^{(1)}_{n,k} = g_{2n-k,n}\) for all \(n \geq k \geq 0\). In this paper, we will show that if \(G\) is a Riordan array, then its half \(G^{(1)}\) is also a Riordan array. We use Lagrange inversion theorem to characterize the generating functions of \(G^{(1)}\) in terms of the generating functions of \(G\). Consequently, a tight relation between \(G^{(1)}\) and the initial array \(G\) is given, hence it is possible to invert the process and rebuild the original Riordan array \(G\) from the array \(G^{(1)}\). If the process of taking half of a Riordan array \(G\) is iterated \(r\) times, then we obtain a Riordan array \(G^{(r)}\). The further relation between the result array \(G^{(r)}\) and the initial array \(G\) is also considered. Some examples and applications are presented.

A graph \(G\) is list \(k\)-arborable if for any sets \(L(v)\) of cardinality at least \(k\) at its vertices, one can choose an element (color) for each vertex \(v\) from its list \(L(v)\) so that the subgraph induced by every color class is an acyclic graph (a forest). In the paper, it is proved that every planar graph with \(5\)-cycles not adjacent to \(3\)-cycles and \(4\)-cycles is list \(2\)-arborable.

For two vertices \(u\) and \(v\) in a strong digraph \(D\), the strong distance between \(u\) and \(v\) is the minimum number of arcs of a strong subdigraph of \(D\) containing \(u\) and \(v\). The strong eccentricity of a vertex \(v\) of \(D\) is the strong distance between \(v\) and a vertex farthest from \(v\). The strong diameter (strong radius) of \(D\) is the maximum (minimum) strong eccentricity among all vertices of \(D\). The lower orientable strong diameter (lower orientable strong radius), \(\mathrm{sdiam}(G)\) (\(\mathrm{srad}(G)\)), of a 2-edge-connected graph \(G\) is the minimum strong diameter (minimum strong radius) over all strong orientations of \(G\). In this paper, a conjecture of Chen and Guo is disproved by proving \(\mathrm{sdiam}(K_{3} \square K_{3}) = \mathrm{sdiam}(K_{3} \square K_{4}) = 5\), \(\mathrm{sdiam}(K_{m} \square P_{n})\) is determined, \(\mathrm{sdiam}(G)\) and \(\mathrm{srad}(G)\) for cycle vertex multiplications are computed, and some results concerning \(\mathrm{sdiam}(G)\) are described.

The aim of this note is to present a short proof of a result of Alaeiyan et al. [Bull. Austral. Math. Soc.\( 77 (2008) 315-323;\)
Proc. Indian Acad. Sci., Math. Sci. \(119 (2009) 647-653\)] concerning the non-existence of cubic semisymmetric graphs of order \(8p\) or \(8p^2\), where \(p\) is a prime. In those two papers, the authors choose the heavy weaponry of covering techniques. Our proof relies on the analysis of the subgroup structure of the full automorphism group of the graph and the normal quotient graph theory.

Let \(G\) be a graph of order \(n\) with adjacency matrix \(A(G)\) and diagonal degree matrix \(D(G)\). The generalized characteristic polynomial of \(G\) is defined to be \(f_G(x,t) = \det (xI_n – (A(G) – tD(G)))\). The \(R\)-graph of \(G\), denoted by \(R(G)\), is obtained by adding a new vertex for each edge of \(G\) and joining each new vertex to both end vertices of the corresponding edge. The generalized \(R\)-vertex corona, denoted by \(R(G) \boxdot \wedge _i^n H\), is the graph obtained from \(R(G)\) and \(H\) by joining the \(i\)-th vertex of \(V(G)\) to every vertex of \(H\). In this paper, we determine the generalized characteristic polynomial of \(R(G) \boxdot \wedge _i^n H\). As applications, we get infinitely many pairs of generalized cospectral graphs, the number of spanning trees and Kirchhoff index of \(R(G) \boxdot\wedge _i^n H\).

In this paper, we introduce an \(O(n^2)\) time algorithm to determine the cyclic edge connectivity of a planar graph, where \(n\) is the order of the planar graph. This is the first correct square time algorithm for cyclic edge connectivity of planar graphs.

Let \(G = (V, E)\), with \(|V| = n\), be a simple connected graph. An edge-colored graph \(G\) is rainbow edge-connected if any two vertices are connected by a path whose edges are colored by distinct colors. The rainbow connection number of a connected graph \(G\), denoted by \(rc(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow edge-connected. In this paper, we obtain tight bounds for \(rc(G)\). We use our results to generalize previous results for graphs with \(\delta(G) \geq 3\).

In this paper, we provide the 4-way combinatorial interpretations of some Rogers–Ramanujan type identities using partitions with “\(n + t\) copies of \(n\)”, lattice paths, \(k\)-partitions, and ordinary partitions.

In this paper, we study the Fibonacci polynomials modulo \(m\) such that \(x^2 = x + 1\) and then we obtain miscellaneous properties of these sequences. Also, we extend the Fibonacci polynomials to the ring of complex numbers. We define the Fibonacci Polynomial-type orbits \(F^R_{(a,b)}(x) = \{x_i\}\), where \(R\) is a 2-generator ring and \((a,b)\) is a generating pair of the ring \(R\). Furthermore, we obtain the periods of the Fibonacci Polynomial-type orbits \(F^R_{(a,b)}(x)\) in finite 2-generator rings of order \(p^2\).

A theta graph is the union of three internally disjoint paths that have the same two distinct end vertices. We show that every graph of order \(n \geq 12\) and size at least\(\max\left\{\left\lceil\frac{3n+79}{2}\right\rceil,\left\lfloor\frac{11n-33}{2}\right\rfloor\right\}\) contains three disjoint theta graphs. As a corollary, every graph of order \(n \geq 12\) and size at least \(\max\left\{\left\lceil\frac{3n+79}{2}\right\rceil ,\left\lfloor\frac{11n-33}{2}\right\rfloor\right\}\) contains three disjoint cycles of even length. The lower bound on the size is sharp in general.

A simple undirected graph is said to be semisymmetric if it is regular and edge-transitive but not vertex-transitive. A semisymmetric graph must be bipartite whose automorphism group has two orbits of the same size on the vertices. One of our long-term goals is to determine all the semisymmetric graphs of order \(2p^3\), for any prime \(p\). All these graphs \(\Gamma\) with the automorphism group \(Aut(\Gamma)\), are divided into two subclasses: (I) \(Aut(\Gamma)\) acts unfaithfully on at least one bipart; and (II) \(Aut(\Gamma)\) acts faithfully on both biparts. In [9],[19] and [20], a complete classification was given for Subclass (I). In this paper, a partial classification is given for Subclass (II), when \(Aut(\Gamma)\) acts primitively on one bipart.

The notions of \(L\)-tree-coloring and list vertex arboricity of graphs are introduced in the paper, while a sufficient condition for a plane graph admitting an \(L\)-tree-coloring is given. Further, it is proved that every graph without \(K_{5}\)-minors or \(K_{3,3}\)-minors has list vertex arboricity at most \(3\), and this upper bound is sharp.

A model for cleaning a graph with brushes was first introduced by Messinger, Nowakowski, and Pralat in 2008. Later, they focused on the problem of determining the maximum number of brushes needed to clean a graph. This maximum number of brushes needed to clean a graph in the model is called the broom number of the graph. In this paper, we show that the broom number of a graph is equal to the size of a maximum edge-cut of the graph, and prove the \(\mathcal{NP}\)-completeness of the problem of determining the broom number of a graph. As an application, we determine the broom number exactly for the Cartesian product of two graphs.

We give more results in mean cordial and harmonic mean labelings, such as: upper bounds for the number of edges of graphs of given orders for both labelings with direct results, labeling all trees of order \(\leq 9\) to be harmonic mean with the restriction of using the floor function of the definition, and labeling all graphs of order \(\leq 5\) that are harmonic mean graphs without using the label \(q + 1\) in labeling the vertices. Also, we give mean cordial labelings for some families of graphs.

Linkage is very important in Very Large Scale Integration (VLSI) physical design. In this paper, we mainly study the relationship between minors and linkages. Thomassen conjectured that every \((2k + 2)\)-connected graph is \(k\)-linked. For \(k \geq 4\), \(K_{3k-1}\) with \(k\) disjoint edges deleted is a counterexample to this conjecture, however, it is still open for \(k = 3\). Thomas and Wollan proved that every \(6\)-connected graph on \(n\) vertices with \(5n – 14\) edges is \(3\)-linked. Hence they obtain that every \(10\)-connected graph is \(3\)-linked. Chen et al. showed that every \(6\)-connected graph with \(K_{9}^-\) as a minor is \(3\)-linked, and every \(7\)-connected graph with \(K_{9}^-\) as a minor is \((2,2k-1)\)-linked. Using a similar method, we prove that every \(8\)-connected graph with \(K_{2k+3}^-\) as a minor is \(4\)-linked, and every \((2k + 1)\)-connected graph with \(K_{2k+3}^-\) as a minor is \((2,2k – 1)\)-linked. Our results extend Chen et al.’s conclusions, improve Thomas and Wollan’s results, and moreover, they give a class of graphs that satisfy Thomassen’s conjecture for \(k = 4\).

Consider any undirected and simple graph \(G = (V, E)\), where \(V\) and \(E\) denote the vertex set and the edge set of \(G\), respectively. Let \(|G| = |V| = n \geq 3\). The well-known Ore’s theorem states that if \(\deg_G(u) + \deg_G(v) \geq n + k\) holds for each pair of nonadjacent vertices \(u\) and \(v\) of \(G\), then \(G\) is traceable for \(k = -1\), Hamiltonian for \(k = 0\), and Hamiltonian-connected for \(k = 1\). In this paper, we investigate any graph \(G\) with \(\deg_G(u) + \deg_G(v) \geq n – 1\) for any nonadjacent vertex pair \(\{u,v\}\) of \(G\), in particular. We call it the \((*)\) condition. We derive four graph families, \(\mathcal{H}_i\), \(1 \leq i \leq 4\), and prove that all graphs satisfying \((*)\) are Hamiltonian-connected unless \(G \in \bigcup_{i=1}^{4} \mathcal{H}_i\). We also establish a comprehensive theorem for \(G\) satisfying \((*)\), which shows that \(G\) is traceable, Hamiltonian, pancyclic, or Hamiltonian-connected unless \(G\) belongs to different subsets of \(\{\mathcal{H}_i | 1 \leq i \leq 4\}\), respectively.

Given a group \(G\), we define the power graph \(P(G)\) as follows: the vertices are the elements of \(G\) and two vertices \(x\) and \(y\) are joined by an edge if \(\langle x\rangle \subseteq \langle y \rangle\) or \(\langle y\rangle \subseteq \langle x \rangle\). Obviously, the power graph of any group is always connected, because the identity element of the group is adjacent to all other vertices. In the present paper, among other results, we will find the number of spanning trees of the power graph associated with specific finite groups. We also determine, up to isomorphism, the structure of a finite group \(G\) whose power graph has exactly \(n\) spanning trees, for \(n < 5^{3}\). Finally, we show that the alternating group \(A_5\) is uniquely determined by the tree-number of its power graph among all finite simple groups.

Let \(G\) be a graph of order \(n\). The number of positive eigenvalues of \(G\) is called the positive inertia index of \(G\) and denoted by \(p(G)\). The minimum number of complete multipartite subgraphs in any complete multipartite graph edge decomposition of graph \(G\), in which the edge-induced subgraph of each edge subset of the decomposition is a complete multipartite graph, is denoted by \(\epsilon(G)\). In this paper, we prove \(\epsilon(G) \geq p(G)\) for any graph \(G\). Especially, if \(\epsilon(G) = 2\), then \(p(G) = 1\). We also characterize the graph \(G\) with \(p(G) = n – 2\).

The distance spectral gap of a connected graph is defined as the difference between its first and second distance eigenvalues. In this note, the unique \(n\)-vertex trees with minimal and maximal distance spectral gaps, and the unique \(n\)-vertex unicyclic graph with minimal distance spectral gap are determined.

A simple graph \(G = (V, E)\) admits an \(H\)-covering if every edge in \(E\) belongs to at least one subgraph of \(G\) isomorphic to a given graph \(H\). An \((a, d)\)-\(H\)-antimagic labeling of \(G\) admitting an \(H\)-covering is a bijective function \(f : V \cup E \rightarrow \{1, 2, \ldots, |V| + |E|\}\) such that, for all subgraphs \(H’\) of \(G\) isomorphic to \(H\), the \(H’\)-weights, \(wt(H’) = \sum_{v \in V(H’)} f(v) + \sum_{e \in E(H’)} f(e)\), constitute an arithmetic progression with the initial term \(a\) and the common difference \(d\). Such a labeling is called super if \(f(V) = \{1, 2, \ldots, |V|\}\). In this paper, we study the existence of super \((a, d)\)-\(H\)-antimagic labelings for graph operation \(G ^ H\), where \(G\) is a (super) \((b, d^*)\)-edge-antimagic total graph and \(H\) is a connected graph of order at least \(3\).

This article proves that the square of a Halin graph \(G\) with \(\Delta(G) = 5\) has the chromatic number \(6\). This gives a positive answer to an open problem in [Y. Wang, Distance two labelling of Halin graphs, Ars Combin. 114 (2014), 331–343].

There are many rectangular arrays whose \(n^{th}\) column is the \(n\)-fold convolution of the \(0^{th}\) column in combinatorics. For this type of rectangular arrays, we prove a formula for evaluating the determinant of certain submatrices, which was conjectured by Hoggatt and Bicknell. Our result unifies the determinant evaluation of submatrices of the rectangular arrays consisting of binomial coefficients, multinomial coefficients, Fibonacci numbers, Catalan numbers, generalized Catalan and Motzkin numbers.

In this paper, we obtain the following upper bounds for the largest Laplacian graph eigenvalue: \[\mu \leq \max\limits_{i} \left\{\sqrt{ 2d_i (m_i + d_i) + n – 2d_i – 2 \sum\limits_{j:j\sim i}{ |N_i \cap N_j|}} \right\}\] where \(d_i\) and \(m_i\) are the degree of vertex \(i\) and the average degree of vertex \(i\), respectively; \(|N_i \cap N_j|\) is the number of common neighbors of vertices \(i\) and \(j\). We also compare this bound with some known upper bounds.

A three-colored digraph \(D\) is primitive if and only if there exist nonnegative integers \(h\), \(k\), and \(v\) with \(h+k+v > 0\) such that for each pair \((i, j)\) of vertices there is an \((h, k, v)\)-walk in \(D\) from \(i\) to \(j\). The exponent of the primitive three-colored digraph \(D\) is defined to be the smallest value of \(h + k + v\) over all such \(h\), \(k\), and \(v\). In this paper, a class of special primitive three-colored digraphs with \(n\) vertices, consisting of one \(n\)-cycle and two \((n-1)\)-cycles, are considered. For the case \(a = c – 1\), some primitive conditions, the tight upper bound on the exponents, and the characterization of extremal three-colored digraphs are given.

Skew-quasi-cyclic codes over a finite field are viewed as skew-cyclic codes on a noncommutative ring of matrices over a finite field. This point of view gives a new construction of skew-quasi-cyclic codes. Let \(\mathbb{F}_q\) be the Galois field with \(q\) elements and \(\theta\) be an automorphism of \(\mathbb{F}_q\). We propose an approach to consider the relationship between left ideals in \(M_l(\mathbb{F}_q)[X, \theta]/(X^s – 1)\) and skew-quasi-cyclic codes of length \(ls\) and index \(l\) over \(\mathbb{F}_q\), under \(\theta\), which we denote by \(\theta\)-SQC codes (or SQC codes for short when there is no ambiguity). We introduce the construction of SQC codes from the reversible divisors of \(X^s – 1\) in \(M_l(\mathbb{F}_q)[X, \theta]\). In addition, we give an algorithm to search for the generator polynomials of general SQC codes.

In this paper, we investigate the concepts of \(k\)-limited packing and \(k\)-tuple domination in graphs and give several bounds on the size of them. These bounds involve many well-known parameters of graphs. Also, we establish a connection between these concepts that implies some new results in this area. Finally, we improve many bounds in the literature.

Let \(G = (V, E)\) be a simple graph. A paired-dominating set of a graph \(G\) is a dominating set whose induced subgraph contains a perfect matching. The paired domination number of a graph \(G\), denoted by \(\gamma_p(G)\), is the minimum cardinality of a paired-dominating set in \(G\). In this paper, we study the paired domination number of generalized Petersen graphs \(P(n,2)\) and prove that for any integer \(n \geq 6\), \(\gamma_p(P(n, 2)) = 2 \left\lfloor \frac{n}{3} \right\rfloor + n \pmod{3}\).

The Estrada index of a simple connected graph \(G\) of order \(n\) is defined as \(EE(G) = \sum_{i=1}^{n} e^{\lambda_i}\), where \(\lambda_1, \lambda_2, \ldots, \lambda_n\) are the eigenvalues of the adjacency matrix of \(G\). In this paper, we characterize all pentacyclic graphs of order \(n\) with maximal Estrada index.

Let \(\Pi\) be a finite polar space of rank \(n \geq 2\) fully embedded into a projective space \(\Sigma\). In this note, we determine all tight sets of \(\Pi\) of the form \((\Sigma_1 \cap \mathcal{P}) \cup (\Sigma_2 \cap \mathcal{P})\), where \(\mathcal{P}\) denotes the point set of \(\Pi\) and \(\Sigma_1, \Sigma_2\) are two mutually disjoint subspaces of \(\Sigma\). In this way, we find two families of \(2\)-tight sets of elliptic polar spaces that were not described before in the literature.

In this paper, we define a new matrix identity for bi-periodic Fibonacci and Lucas numbers. By using the matrix method, we give simple proofs of several properties of these numbers. Moreover, we obtain a new binomial sum formula for bi-periodic Fibonacci and Lucas numbers, which generalize the former results.

Hein and Sarvate show how to decompose \(\lambda\) copies of a complete graph \(K_n\), for some minimal value of \(\lambda\), into so-called LOE and OLE graphs. In this paper, we will show that for all possible values of \(\lambda\), the necessary conditions are sufficient for the LOE and OLE decompositions.