Source author record

Fu-Tao Hu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity math.SP

Catalog footprint

Research overview

15works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Spectra of weighted uniform hypertrees

Let $T$ be a $k$ -tree equipped with a weighting function $\w: V(T)\cup E(T)\rightarrow \C$, where $k \geq 3$ . The weighted matching polynomial of the weighted $k$ -tree $(T,\w)$ is defined to be $$ μ(T,\w,x)= \sum_{M \in \mathcal{M}(T)}(-1)^{|M|}\prod_{e \in E(M)}\mathbf{w}(e)^k \prod_{v \in V(T)\backslash V(M)}(x-\w(v)), $$ where $\mathcal{M}(T)$ denotes the set of matchings (including empty set) of $T$ . In this paper, we investigate the eigenvalues of the adjacency tensor $\A(T,\w)$ of the weighted $k$ -tree $(T,\w)$. The main result provides that $\w(v)$ is an eigenvalue of $\A(T,\w)$ for every $v\in V(T)$ , and if $λ\neq \w(v)$ for every $v\in V(T)$ , then $λ$ is an eigenvalue of $\A(T,\w)$ if and only if there exists a subtree $T'$ of $T$ such that $λ$ is a root of $μ(T',\w,x)$. Moreover, the spectral radius of $\A(T,\w)$ is equal to the largest root of $μ(T,\w,x)$ when $\w$ is real and nonnegative. The result extends a work by Clark and Cooper ({\em On the adjacency spectra of hypertrees, Electron. J. Combin., 25 (2)(2018) $\#$ P2.48}) to weighted $k$ -trees. As applications, two analogues of the above work for the Laplacian and the signless Laplacian tensors of $k$ -trees are obtained.

preprint2015arXiv

Resistance distances in corona and neighborhood corona graphs with Laplacian generalized inverse approach

Let $G_1$ and $G_2$ be two graphs on disjoint sets of $n_1$ and $n_2$ vertices, respectively. The corona of graphs $G_1$ and $G_2$ , denoted by $G_1\circ G_2$ , is the graph formed from one copy of $G_1$ and $n_1$ copies of $G_2$ where the $i$ -th vertex of $G_1$ is adjacent to every vertex in the $i$ -th copy of $G_2$ . The neighborhood corona of $G_1$ and $G_2$ , denoted by $G_1\diamond G_2$ , is the graph obtained by taking one copy of $G_1$ and $n_1$ copies of $G_2$ and joining every neighbor of the $i$ -th vertex of $G_1$ to every vertex in the $i$ -th copy of $G_2$ by a new edge. In this paper, the Laplacian generalized inverse for the graphs $G_1\circ G_2$ and $G_1\diamond G_2$ are investigated, based on which the resistance distances of any two vertices in $G_1\circ G_2$ and $G_1\diamond G_2$ can be obtained. Moreover, some examples as applications are presented, which illustrate the correction and efficiency of the proposed method.

preprint2014arXiv

Asymptotic Laplacian-Energy-Like Invariant of Lattices

Let $μ_1\ge μ_2\ge\cdots\geμ_n$ denote the Laplacian eigenvalues of $G$ with $n$ vertices. The Laplacian-energy-like invariant, denoted by $LEL(G)= \sum_{i=1}^{n-1}\sqrt{μ_i}$ , is a novel topological index. In this paper, we show that the Laplacian-energy-like per vertex of various lattices is independent of the toroidal, cylindrical, and free boundary conditions. Simultaneously, the explicit asymptotic values of the Laplacian-energy-like in these lattices are obtained. Moreover, our approach implies that in general the Laplacian-energy-like per vertex of other lattices is independent of the boundary conditions.

preprint2014arXiv

The Algorithmic Complexity of Bondage and Reinforcement Problems in bipartite graphs

Let $G=(V,E)$ be a graph. A subset $D\subseteq V$ is a dominating set if every vertex not in $D$ is adjacent to a vertex in $D$ . The domination number of $G$ , denoted by $γ(G)$ , is the smallest cardinality of a dominating set of $G$ . The bondage number of a nonempty graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with domination number larger than $γ(G)$ . The reinforcement number of $G$ is the smallest number of edges whose addition to $G$ results in a graph with smaller domination number than $γ(G)$ . In 2012, Hu and Xu proved that the decision problems for the bondage, the total bondage, the reinforcement and the total reinforcement numbers are all NP-hard in general graphs. In this paper, we improve these results to bipartite graphs.

preprint2014arXiv

The Laplacian polynomial of graphs derived from regular graphs and applications

Let $R(G)$ be the graph obtained from $G$ by adding a new vertex corresponding to each edge of $G$ and by joining each new vertex to the end vertices of the corresponding edge. Let $RT(G)$ be the graph obtained from $R(G)$ by adding a new edge corresponding to every vertex of $G$ , and by joining each new edge to every vertex of $G$ . In this paper, we determine the Laplacian polynomials of $RT(G)$ of a regular graph $G$ . Moreover, we derive formulae and lower bounds of Kirchhoff index of the graphs. Finally we also present the formulae for calculating the Kirchhoff index of some special graphs as applications, which show the correction and efficiency of the proposed results.

preprint2012arXiv

On the diameter of the Kronecker product graph

Let $G_1$ and $G_2$ be two undirected nontrivial graphs. The Kronecker product of $G_1$ and $G_2$ denoted by $G_1\otimes G_2$ with vertex set $V(G_1)\times V(G_2)$ , two vertices $x_1x_2$ and $y_1y_2$ are adjacent if and only if $(x_1,y_1)\in E(G_1)$ and $(x_2,y_2)\in E(G_2)$ . This paper presents a formula for computing the diameter of $G_1\otimes G_2$ by means of the diameters and primitive exponents of factor graphs.

preprint2012arXiv

On the p-reinforcement and the complexity

Let $G=(V,E)$ be a graph and $p$ be a positive integer. A subset $S\subseteq V$ is called a $p$ -dominating set if each vertex not in $S$ has at least $p$ neighbors in $S$ . The $p$ -domination number $\g_p(G)$ is the size of a smallest $p$ -dominating set of $G$ . The $p$ -reinforcement number $r_p(G)$ is the smallest number of edges whose addition to $G$ results in a graph $G'$ with $\g_p(G')<\g_p(G)$. In this paper, we give an original study on the $p$ -reinforcement, determine $r_p(G)$ for some graphs such as paths, cycles and complete $t$ -partite graphs, and establish some upper bounds of $r_p(G)$ . In particular, we show that the decision problem on $r_p(G)$ is NP-hard for a general graph $G$ and a fixed integer $p\geq 2$ .

preprint2012arXiv

On the Roman bondage number of a graph

A Roman dominating function on a graph $G=(V,E)$ is a function $f:V\rightarrow\{0,1,2\}$ such that every vertex $v\in V$ with $f(v)=0$ has at least one neighbor $u\in V$ with $f(u)=2$ . The weight of a Roman dominating function is the value $f(V(G))=\sum_{u\in V(G)}f(u)$ . The minimum weight of a Roman dominating function on a graph $G$ is called the Roman domination number, denoted by $γ_{R}(G)$ . The Roman bondage number $b_{R}(G)$ of a graph $G$ with maximum degree at least two is the minimum cardinality of all sets $E'\subseteq E(G)$ for which $γ_{R}(G-E')>γ_R(G)$ . In this paper, we first show that the decision problem for determining $b_{\rm R}(G)$ is NP-hard even for bipartite graphs and then we establish some sharp bounds for $b_{\rm R}(G)$ and characterizes all graphs attaining some of these bounds.

preprint2011arXiv

Complexity of Bondage and Reinforcement

Let $G=(V,E)$ be a graph. A subset $D\subseteq V$ is a dominating set if every vertex not in $D$ is adjacent to a vertex in $D$ . A dominating set $D$ is called a total dominating set if every vertex in $D$ is adjacent to a vertex in $D$ . The domination (resp. total domination) number of $G$ is the smallest cardinality of a dominating (resp. total dominating) set of $G$ . The bondage (resp. total bondage) number of a nonempty graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with larger domination (resp. total domination) number of $G$ . The reinforcement number of $G$ is the smallest number of edges whose addition to $G$ results in a graph with smaller domination number. This paper shows that the decision problems for bondage, total bondage and reinforcement are all NP-hard.

preprint2011arXiv

Roman Bondage Number of a Graph

The Roman dominating function on a graph $G=(V,E)$ is a function $f: V\rightarrow\{0,1,2\}$ such that each vertex $x$ with $f(x)=0$ is adjacent to at least one vertex $y$ with $f(y)=2$ . The value $f(G)=\sum\limits_{u\in V(G)} f(u)$ is called the weight of $f$ . The Roman domination number $γ_{\rm R}(G)$ is defined as the minimum weight of all Roman dominating functions. This paper defines the Roman bondage number $b_{\rm R}(G)$ of a nonempty graph $G=(V,E)$ to be the cardinality among all sets of edges $B\subseteq E$ for which $γ_{\rm R}(G-B)>γ_{\rm R}(G)$ . Some bounds are obtained for $b_{\rm R}(G)$ , and the exact values are determined for several classes of graphs. Moreover, the decision problem for $b_{\rm R}(G)$ is proved to be NP-hard even for bipartite graphs.

preprint2011arXiv

Roman Bondage Numbers of Some Graphs

A Roman dominating function on a graph $G=(V,E)$ is a function $f: V\to \{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ with $f(v)=2$ . The weight of a Roman dominating function is the value $f(G)=\sum_{u\in V} f(u)$ . The Roman domination number of $G$ is the minimum weight of a Roman dominating function on $G$ . The Roman bondage number of a nonempty graph $G$ is the minimum number of edges whose removal results in a graph with the Roman domination number larger than that of $G$ . This paper determines the exact value of the Roman bondage numbers of two classes of graphs, complete $t$ -partite graphs and $(n-3)$ -regular graphs with order $n$ for any $n\ge 5$ .

preprint2011arXiv

The bondage number of $(n-3)$ -regular graphs of order $n$

Let $G=(V,E)$ be a graph. A subset $D\subseteq V$ is a dominating set if every vertex not in $D$ is adjacent to a vertex in $D$ . The domination number of $G$ is the smallest cardinality of a dominating set of $G$ . The bondage number of a nonempty graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with larger domination number of $G$ . In this paper, we determine that the exact value of the bondage number of $(n-3)$ -regular graph $G$ of order $n$ is $n-3$ .

preprint2011arXiv

The Bondage Number of Mesh Networks

The bondage number $b(G)$ of a nonempty graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with domination number greater than that of $G$ . Denote $P_n\times P_m$ be the Cartesian product of two paths $P_n$ and $P_m$ . This paper determines that the exact value of $b(P_n\times P_2)$ , $b(P_n\times P_3)$ and $b(P_n\times P_4)$ for $n\ge 2$ .

preprint2011arXiv

The total bondage number of grid graphs

The total domination number of a graph $G$ without isolated vertices is the minimum number of vertices that dominate all vertices in $G$ . The total bondage number $b_t(G)$ of $G$ is the minimum number of edges whose removal enlarges the total domination number. This paper considers grid graphs. An $(n,m)$ -grid graph $G_{n,m}$ is defined as the cartesian product of two paths $P_n$ and $P_m$ . This paper determines the exact values of $b_t(G_{n,2})$ and $b_t(G_{n,3})$ , and establishes some upper bounds of $b_t(G_{n,4})$ .

preprint2011arXiv

Total and paired domination numbers of toroidal meshes

Let $G$ be a graph without isolated vertices. The total domination number of $G$ is the minimum number of vertices that can dominate all vertices in $G$ , and the paired domination number of $G$ is the minimum number of vertices in a dominating set whose induced subgraph contains a perfect matching. This paper determines the total domination number and the paired domination number of the toroidal meshes, i.e., the Cartesian product of two cycles $C_n$ and $C_m$ for any $n\ge 3$ and $m\in\{3,4\}$ , and gives some upper bounds for $n, m\ge 5$ .

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.

Fu-Tao Hu

Research overview

Is this your work?

15 publications

Spectra of weighted uniform hypertrees

Resistance distances in corona and neighborhood corona graphs with Laplacian generalized inverse approach

Asymptotic Laplacian-Energy-Like Invariant of Lattices

The Algorithmic Complexity of Bondage and Reinforcement Problems in bipartite graphs

The Laplacian polynomial of graphs derived from regular graphs and applications

On the diameter of the Kronecker product graph

On the p-reinforcement and the complexity

On the Roman bondage number of a graph

Complexity of Bondage and Reinforcement

Roman Bondage Number of a Graph

Roman Bondage Numbers of Some Graphs

The bondage number of $(n-3)$ -regular graphs of order $n$

The Bondage Number of Mesh Networks

The total bondage number of grid graphs

Total and paired domination numbers of toroidal meshes

See the researcher in context

Building this map preview

Fu-Tao Hu

Research overview

Is this your work?

15 publications

Spectra of weighted uniform hypertrees

Resistance distances in corona and neighborhood corona graphs with Laplacian generalized inverse approach

Asymptotic Laplacian-Energy-Like Invariant of Lattices

The Algorithmic Complexity of Bondage and Reinforcement Problems in bipartite graphs

The Laplacian polynomial of graphs derived from regular graphs and applications

On the diameter of the Kronecker product graph

On the p-reinforcement and the complexity

On the Roman bondage number of a graph

Complexity of Bondage and Reinforcement

Roman Bondage Number of a Graph

Roman Bondage Numbers of Some Graphs

The bondage number of (n−3)(n-3)(n−3)-regular graphs of order nnn

The Bondage Number of Mesh Networks

The total bondage number of grid graphs

Total and paired domination numbers of toroidal meshes

See the researcher in context

Building this map preview

The bondage number of $(n-3)$ -regular graphs of order $n$