Researcher profile

Huishu Lian

Huishu Lian contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.CO Computational Complexity

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author

11works

0followers

2topics

3close collaborators

Actions

Decide how to stay connected

Follow researcher0

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

preprint2015arXiv

A survey on the skew energy of oriented graphs

Let $G$ be a simple undirected graph with adjacency matrix $A(G)$. The energy of $G$ is defined as the sum of absolute values of all eigenvalues of $A(G)$, which was introduced by Gutman in 1970s. Since graph energy has important chemical applications, it causes great concern and has many generalizations. The skew energy and skew energy-like are the generalizations in oriented graphs. Let $G^σ$ be an oriented graph of $G$ with skew adjacency matrix $S(G^σ)$. The skew energy of $G^σ$, denoted by $\mathcal{E}_S(G^σ)$, is defined as the sum of the norms of all eigenvalues of $S(G^σ)$, which was introduced by Adiga, Balakrishnan and So in 2010. In this paper, we summarize main results on the skew energy of oriented graphs. Some open problems are proposed for further study. Besides, results on the skew energy-like: the skew Laplacian energy and skew Randić energy are also surveyed at the end.

preprint2014arXiv

Lower bounds of the skew spectral radii and skew energy of oriented graphs

Let $G$ be a graph with maximum degree $Δ$, and let $G^σ$ be an oriented graph of $G$ with skew adjacency matrix $S(G^σ)$. The skew spectral radius $ρ_s(G^σ)$ of $G^σ$ is defined as the spectral radius of $S(G^σ)$. The skew spectral radius has been studied, but only few results about its lower bound are known. This paper determines some lower bounds of the skew spectral radius, and then studies the oriented graphs whose skew spectral radii attain the lower bound $\sqrtΔ$. Moreover, we apply the skew spectral radius to the skew energy of oriented graphs, which is defined as the sum of the norms of all the eigenvalues of $S(G^σ)$, and denoted by $\mathcal{E}_s(G^σ)$. As results, we obtain some lower bounds of the skew energy, which improve the known lower bound obtained by Adiga et al.

preprint2014arXiv

Solution to a conjecture on the maximum skew-spectral radius of odd-cycle graphs

Let $G$ be a simple graph with no even cycle, called an odd-cycle graph. Cavers et al. [Cavers et al. Skew-adjacency matrices of graphs, Linear Algebra Appl. 436(2012), 4512--1829] showed that the spectral radius of $G^σ$ is the same for every orientation $σ$ of $G$, and equals the maximum matching root of $G$. They proposed a conjecture that the graphs which attain the maximum skew spectral radius among the odd-cycle graphs $G$ of order $n$ are isomorphic to the odd-cycle graph with one vertex degree $n-1$ and size $m=\lfloor 3(n-1)/2\rfloor$. This paper, by using the Kelmans transformation, gives a proof of the conjecture. Moreover, sharp upper bounds of the maximum matching roots of the odd-cycle graphs with given order $n$ and size $m$ are given and extremal graphs are characterized.

preprint2014arXiv

The matching energy of random graphs

The matching energy of a graph was introduced by Gutman and Wagner, which is defined as the sum of the absolute values of the roots of the matching polynomial of the graph. For the random graph $G_{n,p}$ of order $n$ with fixed probability $p\in (0,1)$, Gutman and Wagner [I. Gutman, S. Wagner, The matching energy of a graph, Discrete Appl. Math. 160(2012), 2177--2187] proposed a conjecture that the matching energy of $G_{n,p}$ converges to $\frac{8\sqrt{p}}{3π}n^{\frac{3}{2}}$ almost surely. In this paper, using analysis method, we prove that the conjecture is true.

preprint2013arXiv

More on the skew-spectra of bipartite graphs and Cartesian products of graphs

Given a graph $G$, let $G^σ$ be an oriented graph of $G$ with the orientation $σ$ and skew-adjacency matrix $S(G^σ)$. Then the spectrum of $S(G^σ)$ is called the skew-spectrum of $G^σ$, denoted by $Sp_S(G^σ)$. It is known that a graph $G$ is bipartite if and only if there is an orientation $σ$ of $G$ such that $Sp_S(G^σ)=iSp(G)$. In [D. Cui, Y. Hou, On the skew spectra of Cartesian products of graphs, Electron. J. Combin. 20(2013), #P19], Cui and Hou conjectured that such orientation of a bipartite graph is unique under switching-equivalence. In this paper, we prove that the conjecture is true. Moreover, we give an orientation of the Cartesian product of a bipartite graph and a graph, and then determine the skew-spectrum of the resulting oriented product graph, which generalizes Cui and Hou's result, and can be used to construct more oriented graphs with maximum skew energy.

preprint2013arXiv

Note on packing of edge-disjoint spanning trees in sparse random graphs

The \emph{spanning tree packing number} of a graph $G$ is the maximum number of edge-disjoint spanning trees contained in $G$. Let $k\geq 1$ be a fixed integer. Palmer and Spencer proved that in almost every random graph process, the hitting time for having $k$ edge-disjoint spanning trees equals the hitting time for having minimum degree $k$. In this paper, we prove that for any $p$ such that $(\log n+ω(1))/n\leq p\leq (1.1\log n)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is equal to the minimum degree. Note that this bound for $p$ will allow the minimum degree to be a function of $n$, and in this sense we improve the result of Palmer and Spencer. Moreover, we also obtain that for any $p$ such that $p\geq (51\log n)/n$, almost surely the random graph $G(n,p)$ satisfies that the spanning tree packing number is less than the minimum degree.

preprint2013arXiv

Skew-spectra and skew energy of various products of graphs

Given a graph $G$, let $G^σ$ be an oriented graph of $G$ with the orientation $σ$ and skew-adjacency matrix $S(G^σ)$. Then the spectrum of $S(G^σ)$ consisting of all the eigenvalues of $S(G^σ)$ is called the skew-spectrum of $G^σ$, denoted by $Sp(G^σ)$. The skew energy of the oriented graph $G^σ$, denoted by $\mathcal{E}_S(G^σ)$, is defined as the sum of the norms of all the eigenvalues of $S(G^σ)$. In this paper, we give orientations of the Kronecker product $H\otimes G$ and the strong product $H\ast G$ of $H$ and $G$ where $H$ is a bipartite graph and $G$ is an arbitrary graph. Then we determine the skew-spectra of the resultant oriented graphs. As applications, we construct new families of oriented graphs with maximum skew energy. Moreover, we consider the skew energy of the orientation of the lexicographic product $H[G]$ of a bipartite graph $H$ and a graph $G$.

preprint2013arXiv

The skew energy of random oriented graphs

Given a graph $G$, let $G^σ$ be an oriented graph of $G$ with the orientation $σ$ and skew-adjacency matrix $S(G^σ)$. The skew energy of the oriented graph $G^σ$, denoted by $\mathcal{E}_S(G^σ)$, is defined as the sum of the absolute values of all the eigenvalues of $S(G^σ)$. In this paper, we study the skew energy of random oriented graphs and formulate an exact estimate of the skew energy for almost all oriented graphs by generalizing Wigner's semicircle law. Moreover, we consider the skew energy of random regular oriented graphs $G_{n,d}^σ$, and get an exact estimate of the skew energy for almost all regular oriented graphs.

preprint2012arXiv

Rainbow $k$-connectivity of random bipartite graphs

A path in an edge-colored graph $G$ is called a rainbow path if no two edges of the path are colored the same. The minimum number of colors required to color the edges of $G$ such that every pair of vertices are connected by at least $k$ internally vertex-disjoint rainbow paths is called the rainbow $k$-connectivity of the graph $G$, denoted by $rc_k(G)$. For the random graph $G(n,p)$, He and Liang got a sharp threshold function for the property $rc_k(G(n,p))\leq d$. In this paper, we extend this result to the case of random bipartite graph $G(m,n,p)$.

preprint2011arXiv

Further hardness results on the rainbow vertex-connection number of graphs

A vertex-colored graph $G$ is {\it rainbow vertex-connected} if any pair of vertices in $G$ are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The {\it rainbow vertex-connection number} of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. In a previous paper we showed that it is NP-Complete to decide whether a given graph $G$ has $rvc(G)=2$. In this paper we show that for every integer $k\geq 2$, deciding whether $rvc(G)\leq k$ is NP-Hard. We also show that for any fixed integer $k\geq 2$, this problem belongs to NP-class, and so it becomes NP-Complete.

preprint2010arXiv

Nordhaus-Gaddum-type theorem for rainbow connection number of graphs

An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of $G$, denoted $rc(G)$, is the minimum number of colors that are used to make $G$ rainbow connected. In this paper we give a Nordhaus-Gaddum-type result for the rainbow connection number. We prove that if $G$ and $\bar{G}$ are both connected, then $4\leq rc(G)+rc(\bar{G})\leq n+2$. Examples are given to show that the upper bound is sharp for all $n\geq 4$, and the lower bound is sharp for all $n\geq 8$. For the rest small $n=4,5,6,7,$ we also give the sharp bounds.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint