FHFu-Tao Hu

Fu-Tao Hu

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Fu-Tao Hu has a total of 20 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs

    by Fu-Tao Hu, Chang-Xu Zhang, Shu-Cheng Yang

    Let G = V , E be a simple graph. A subset D ⊆ 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 domination subdivision number sd γ G of G is the minimum number of edges that must be subdivided (each edge can be subdivided at most once) in order to increase the domination number. In 2000, Haynes et al. showed that sd γ G ≤ d G v + d G v − 1 for any edge u v ∈ E G with d G u ≥ 2 and d G v ≥ 2 where G is a connected graph with order no less than 3. In this paper, we improve the above bound to sd γ G ≤ d G u + d G v − N G u ∩ N G v − 1 , and furthermore, we show the decision problem for determining whether sd γ G = 1 is NP-hard. Moreover, we show some bounds or exact values for domination subdivision numbers of some graphs.

  • Open Access

    On the (total) Roman domination in Latin square graphs

    by Chang-Xu Zhang, Fu-Tao Hu, Shu-Cheng Yang

    Latin square, also known as Latin square matrix, refers to a kind of $ n\times n $ matrix, in which there are exactly $ n $ different symbols and each symbol appears exactly once in each row and column. A Latin square graph $ \Gamma(L) $ is a simple graph associated with a Latin square $ L $. This paper studied the relationships between the (total) Roman domination number and (total) domination number of Latin square graph $ \Gamma(L) $. We showed that $ \gamma_{R}(\Gamma(L)) = 2\gamma(\Gamma(L)) $ or $ \gamma_{R}(\Gamma(L)) = 2\gamma(\Gamma(L))-1 $, and $ \gamma_{tR}(\Gamma(L))\ge \frac{8\gamma_t(\Gamma(L))}{5} $ for $ n\ge 2 $. In 2021, Pahlavsay et al. proved $ \gamma(\Gamma(L))\ge \lceil \frac{n}{2}\rceil $ and $ \gamma_t(\Gamma(L))\ge \lceil \frac{4n-2}{7}\rceil $ for $ n\ge 2 $. In this paper, we showed that $ \gamma_R(\Gamma(L))\ge 2\lceil \frac{n}{2}\rceil $ (equality holds if, and only if, $ \gamma(\Gamma(L)) = \lceil \frac{n}{2}\rceil $) and $ \gamma_t(\Gamma(L)) > \frac{4n}{7} $ for $ n\ge 2 $. Since $ \gamma_R(G)\le 2\gamma(G) $ and $ \gamma_{tR}(G)\le 2\gamma_t(G) $ for any graph $ G $, our results can deduce or improve Pahlavsay et al.'s results. Moreover, we characterized these Latin squares for $ \gamma_R(\Gamma(L)) = 2\lceil \frac{n}{2}\rceil $, which is equal to $ \gamma(\Gamma(L)) = \lceil \frac{n}{2}\rceil $.


  • Open Access

    On extremal spectral radius of blow-up uniform hypergraphs

    by Shao-Han Xu, Fu-Tao Hu, Yi Wang

    Let $G$ be an $r$-uniform hypergraph of order $t$ and $ρ(G)$ is the spectral radius of $\mathcal{A}(G)$, where $\mathcal{A}(G)$ is the adjacency tensor of $G$. A blow-up of $G$ respected to a positive integer vector $(n_{1}, n_{2},\ldots,n_{t})$, denoted by $G \circ (n_{1}, n_{2},\ldots,n_{t})$, is an $r$-uniform hypergraph obtained from $G$ by replacing each vertex $j$ of $G$ with a class of vertices $V_{j}$ of size $n_{j}\ge 1$ and if $\{j_{1},j_{2},\ldots,j_{r}\}\in E(G)$, then $\{v_{i_1},v_{i_2},\ldots,v_{i_r}\}\in E(H)$ for every $v_{i_{1}}\in V_{j_{1}}, v_{i_{2}}\in V_{j_{2}},\ldots, v_{i_{r}}\in V_{j_{r}}$. Let $\mathcal{B}_{n}(G)$ be the set of all the blow-ups of $G$ such that each $n_i\ge 1$ and $\sum_{i=1}^n n_i=n$. Let $K_{t}^{r}$ be the complete $r$-uniform hypergraph of order $t$, and let $SH(m,q,r)$ be the $r$-uniform sunflower hypergraph with $m$ petals and a kernel of size $r-q$ on $t$ vertices. For any $H\in \mathcal{B}_{n}(K_{t}^{r})$, we prove that $$ρ(K_{t}^{r}\circ(n-t+1,1,1,\ldots,1))\leqρ(H)\leq ρ(T_{t}^{r}(n)),$$ with the left equality holds if and only if $H\cong K_{t}^{r}\circ(n-t+1,1,1,\ldots,1)$, and the right equality holds if and only if $H\cong T_{t}^{r}(n)$, where $T_{t}^{r}(n)$ is the complete $t$-partite $r$-uniform hypergraph of order $n$, with parts of size $\lfloor n / k\rfloor$ or $\lceil n / k \rceil$. For any $H\in \mathcal{B}_{n}(H(m,q,r))$, we determine the exact value of the spectral radius of $H$ and characterize the hypergraphs with maximum spectral radius and minimum spectral radius in $\mathcal{B}_{n}(H(m,q,r))$, respectively.

  • Open Access

    Induced subgraph and eigenvalues of some signed graphs

    by Fu-Tao Hu, Mei-Yu Sun

    Hao Huang proved the Sensitivity Conjecture in [Induced graphs of the hypercube and a proof of the Sensitivity Conjecture, Annals of Mathematics, 190 (2019), 949-955] by signed graph spectral method. The main result of that paper is every (2n−1+1)-vertex induced subgraph of n-dimensional hypercube Qn has maximum degree at least n by proving that Qn has just two distinct adjacency eigenvalues n and −n with a signature. In this paper, we consider the eigenvalues of signed Cartesian product of bipartite graph Ka,b and hypercube Qn, signed Cartesian product of complete graph Km and hypercube Qn which contain Huang’s result when a=b=1 or m = 2. Let f(G) be the minimum of the maximum degree of an induced subgraph of G on α(G)+1 vertices where α(G) is the independent number of G. Huang also asked the following question: Given a graph G with high symmetry, what can we say about f(G)? We study this question for k-ary n-cubes Qnk, where 2-ary n-cube is Qn. In this paper, we show that every (22n−1+1)-vertex induced subgraph of Qn4 has maximum degree at least 2n ( f(Qn4)≥2n) by proving that Qn4 has two eigenvalues which are either 2n or −2n with a signature.


  • Open Access

    Characterization of trees with Roman bondage number 1

    by Fu-Tao Hu, Xing Wei Wang, Ning Li

    Let G = (V, E) be a simple undirected graph. A Roman dominating function on G is a function f : V -> {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) = Sigma(u is an element of 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. Rad and Volkmann [9] proposed a problem that is to determine the trees T with Roman bondage number 1. In this paper, we characterize trees with Roman bondage number 1.

  • Open Access

    Maximum Independent Sets Partition of (n, k)‐Star Graphs

    by Fu-Tao Hu

    The (n, k)‐star graph is a very important computer modelling. The independent number and chromatic number of a graph are two important parameters in graph theory. However, we have not known the values of these two parameters of the (n, k)‐star graph since it was proposed. In this paper, we show a maximum independent sets partition of (n, k)‐star graph. From that, we can immediately deduce the exact value of the independent number and chromatic number of (n, k)‐star graph.

  • Open Access

    Maximum Independent Sets Partition of (n,k)-Star Graphs

    by Fu-Tao Hu

    The (n,k)-star graph is a very important computer modelling. The independent number and chromatic number of a graph are two important parameters in graph theory. However, we did not know the values of this two parameters of the (n,k)-star graph since it was proposed. In [18], Wei et. al. declared that they determined the independent number of the (n,k)-star graph, unfortunately their proof is wrong. This paper generalize their result and present a maximum independent sets partition of (n,k)-star graph. From that we can immediately deduce the exact value of the independent number and chromatic number of (n,k)-star graph.