Permutation tableaux were introduced in the study of totally positive Grassmannian cells, and are connected with the steady state of asymmetric exclusion process, which is an important model from statistical mechanics. In this paper, we firstly establish a shape-preserving involution on the set of permutation tableaux of length \(n\), which directly shows that the number of permutation tableaux of length \(n\) with \(k\) essential 1’s equals the number of permutation tableaux of length \(n\) with \(n-k\) unrestricted rows. In addition, we introduce three combinatorial structures, called free permutation tableaux, restricted set partitions, and labeled Dyck paths. We discuss the properties of their internal structures and present the correspondence between the set of free permutation tableaux of length \(n\) and the set of restricted set partitions of \(\{1,2,\ldots,n\}\), and we also give a bijection between the set of restricted set partitions of \(\{1,2,\ldots,n\}\) and the set of labeled Dyck paths of length \(2n\). Finally, we make a generalization of the latter bijection.

Let \(G = (V, E)\) be a connected multigraph with order \(n\). \(\delta(G)\) and \(\lambda(G)\) are the minimum degree and edge connectivity, respectively. The multigraph \(G\) is called maximally edge-connected if \(\lambda(G) = \delta(G)\) and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. A sequence \(D = (d_1, d_2, \ldots, d_n)\) with \(d_1 \geq d_2 \geq \ldots \geq d_n\) is called a multigraphic sequence if there is a multigraph with vertices \(v_1, v_2, \ldots, v_n\) such that \(d(v_i) = d_i\) for each \(i = 1, 2, \ldots, n\). The multigraphic sequence \(D\) is super edge-connected if there exists a super edge-connected multigraph \(G\) with degree sequence \(D\). In this paper, we present that a multigraphic sequence \(D\) with \(d_n = 1\) is super edge-connected if and only if \(\sum\limits_{i=1}^{n} d_i \geq 2n\) and give a sufficient and necessary condition for a multigraphic sequence \(D\) with \(d_n = 2\) to be super edge-connected. Moreover, we show that a multigraphic sequence \(D\) with \(d_n \geq 3\) is always super edge-connected.

The general sum-connectivity index is defined as \(\chi_\alpha(G) = \sum_{uv \in E(G)} (d_G(u) + d_G(v))^\alpha\). Let \(\mathcal{T}(n, \beta)\) be the class of trees of order \(n\) with given matching number \(\beta\). In this paper, we characterize the structure of the trees with a given order and matching number that have maximum general sum-connectivity index for \(0 < \alpha < 1\) and give a sharp upper bound for \(\alpha \geq 1\).

The hyper-Wiener index is a graph invariant that is used as a structure descriptor for predicting physicochemical properties of organic compounds. We determine the n-vertex unicyclic graphs with the third smallest and the third largest hyper-Wiener indices for \(n\geq 5\).

A graph \(G\) with no isolated vertex is total restrained domination vertex critical if for any vertex \(v\) of \(G\) that is not adjacent to a vertex of degree one, the total restrained domination number of \(G – v\) is less than the total restrained domination number of \(G\). We call these graphs \(\gamma_{tr}\)-vertex critical. If such a graph \(G\) has total restrained domination number \(k\), we call it \(k\)-\(\gamma_{tr}\)-vertex critical. In this paper, we study matching properties in \(4\)-\(\gamma_{tr}\)-vertex critical graphs of minimum degree at least two.

A generalized weighted digraph \(G = (V, E)\) is a digraph with \(n\) vertices and \(m\) arcs without loops and multiarcs, where each arc is assigned a weight that is a non-negative and symmetric matrix of order \(p\). In this paper, we give a sharp upper bound for the spectral radius of generalized weighted digraphs (see Theorem 2.7), which generalizes some other results on the spectral radius of weighted digraphs in [4], [11], and [16].

It has been shown by Bennett et al. in 1998 that a holey Schröder design with \(n\) holes of size 2 and one hole of size \(u\), i.e., of type \(2^n u\), exists if \(1 \leq u \leq 4\) and \(n \geq u+1\) with the exception of \((n,u) \in \{(2, 1), (3, 1), (3, 2)\}\), or \(u \geq 16\) and \(n \geq \left\lceil \frac{5u}{4} \right\rceil + 14\). In this paper, we extend this result by showing that, for \(1 \leq u \leq 16\), a holey Schröder design of type \(2^n u\) exists if and only if \(n \geq u+1\), with the exception of \((n,u) \in \{(2, 1), (3, 1), (3, 2)\}\) and with the possible exception of \((n,u) \in \{(7,5), (7,6), (11,9), (11,10)\}\). For general \(u\), we prove that there exists an HSD(\(2^n u\)) for all \(u \geq 17\) and \(n \geq \left\lceil \frac{5u}{4} \right\rceil + 4\). Moreover, if \(u \geq 35\), then an HSD(\(2^n u\)) exists for all \(n \geq \left\lceil \frac{5u}{4} \right\rceil + 1\); if \(u \geq 95\), then an HSD(\(2^n u\)) exists for all \(n \geq \left\lceil \frac{5u}{4} \right\rceil – 2\). We also improve a well-known result on the existence of holey Schröder designs of type \(h^n\) by removing the remaining possible exception of type \(64\).

A vertex of a graph is said to be total domination critical if its deletion decreases the total domination number. A graph is said to be total domination vertex critical if all of its vertices, except the supporting vertices, are total domination vertex critical. We show that if \(G\) is a connected total domination vertex critical graph with total domination number \(k \geq 4\), then the diameter of \(G\) is at most \(\lfloor \frac{5k-7}{3}\rfloor\).

By computer-assisted approaches and inductive arguments, two curious sums of triple multiplication of binomial coefficients are established in the present paper. The two curious sums arise in proving Melham’s conjecture on odd power sums of Fibonacci numbers, which was confirmed by Xie, Yang and the present author. However, being different from their’s technical way, the method used in the paper is more elementary.

Let \(G\) be a graph and \(u\) be a vertex of \(G\). The transmission index of \(u\) in \(G\), denoted by \(T_G(u)\), is the sum of distances from \(u\) to all the other vertices in graph \(G\), i.e., \(T(u) = T_G(u) = \sum_{v \in V} d_G(u,v)\). The Co-PI index [1] is defined as \(Co\text{-}PI(G) = \sum_{uv \in E(G)} |T(u) – T(v)|\). In this paper, we give some upper bounds for the Co-PI indices of the join, composition, disjunction, symmetric difference, and corona graph \(G_1 \circ G_2\).