Source author record

Tingzeng Wu

Tingzeng Wu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Computational Complexity Discrete Mathematics

Catalog footprint

What is connected

6works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

On complexity of substructure connectivity and restricted connectivity of graphs

The connectivity of a graph is an important parameter to evaluate its reliability. $k$-restricted connectivity (resp. $R^h$-restricted connectivity) of a graph $G$ is the minimum cardinality of a set $S$ of vertices in $G$, if exists, whose deletion disconnects $G$ and leaves each component of $G-S$ with more than $k$ vertices (resp. $δ(G-S)\geq h$). In contrast, structure (substructure) connectivity of $G$ is defined as the minimum number of vertex-disjoint subgraphs whose deletion disconnects $G$. As generalizations of the concept of connectivity, structure (substructure) connectivity, restricted connectivity and $R^h$-restricted connectivity have been extensively studied from the combinatorial point of view. Very little is known about the computational complexity of these variants, except for the recently established NP-completeness of $k$-restricted edge-connectivity. In this paper, we prove that the problems of determining structure, substructure, restricted, and $R^h$-restricted connectivity are all NP-complete.

preprint2022arXiv

The characterizing properties of (signless) Laplacian permanental polynomials of bicyclic graphs

Let $G$ be a graph with $n$ vertices, and let $L(G)$ and $Q(G)$ be the Laplacian matrix and signless Laplacian matrix of $G$, respectively. The polynomial $π(L(G);x)={\rm per}(xI-L(G))$ (resp. $π(Q(G);x)={\rm per}(xI-Q(G))$) is called {\em Laplacian permanental polynomial} (resp. {\em signless Laplacian permanental polynomial}) of $G$. In this paper, we show that two classes of bicyclic graphs are determined by their (signless) Laplacian permanental polynomials.

preprint2020arXiv

Unpaired many-to-many disjoint path cover of balanced hypercubes

The balanced hypercube $BH_n$, a variant of the hypercube, was proposed as a desired interconnection network topology. It is known that $BH_n$ is bipartite. Assume that $S=\{s_1,s_2,\cdots,s_{2n-2}\}$ and $T=\{t_1,t_2,\cdots,t_{2n-2}\}$ are any two sets of vertices in different partite sets of $BH_n$ ($n\geq2$). It has been proved that there exists paired 2-disjoint path cover of $BH_n$. In this paper, we prove that there exists unpaired $(2n-2)$-disjoint path cover of $BH_n$ ($n\geq2$) from $S$ to $T$, which improved some known results. The upper bound $2n-2$ of the number of disjoint paths in unpaired $(2n-2)$-disjoint path cover is best possible.

preprint2019arXiv

Fractional matching preclusion for restricted hypercube-like graphs

The restricted hypercube-like graphs, variants of the hypercube, were proposed as desired interconnection networks of parallel systems. The matching preclusion number of a graph is the minimum number of edges whose deletion results in the graph with neither perfect matchings nor almost perfect matchings. The fractional perfect matching preclusion and fractional strong perfect matching preclusion are generalizations of the concept matching preclusion. In this paper, we obtain fractional matching preclusion number and fractional strong matching preclusion numbers of restricted hypercube-like graphs, which extend some known results.

preprint2016arXiv

On the permanental nullity and matching number of graphs

For a graph $G$ with $n$ vertices, let $ν(G)$ and $A(G)$ denote the matching number and adjacency matrix of $G$, respectively. The permanental polynomial of $G$ is defined as $π(G,x)={\rm per}(Ix-A(G))$. The permanental nullity of $G$, denoted by $η_{per}(G)$, is the multiplicity of the zero root of $π(G,x)$. In this paper, we use the Gallai-Edmonds structure theorem to derive a concise formula which reveals the relationship between the permanental nullity and the matching number of a graph. Furthermore, we prove a necessary and sufficient condition for a graph $G$ to have $η_{per}(G)=0$. As applications, we show that every unicyclic graph $G$ on $n$ vertices satisfies $n-2ν(G)-1 \le η_{per}(G) \le n-2ν(G)$, that the permanental nullity of the line graph of a graph is either zero or one, and that the permanental nullity of a factor critical graph is always zero.

preprint2014arXiv

Extremal matching energy of complements of trees

The matching energy is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph, which is proposed first by Gutman and Wagner [The matching energy of a graph, Discrete Appl. Math. 160 (2012) 2177--2187]. And they gave some properties and asymptotic results of the matching energy. In this paper, we characterize the trees with $n$ vertices whose complements have the maximal, second-maximal and minimal matching energy. Further, we determine the trees with a perfect matching whose complements have the second-maximal matching energy. In particular, show that the trees with edge-independence number number $p$ whose complements have the minimum matching energy for $p=1,2,\ldots, \lfloor\frac{n}{2}\rfloor$.