BZPEER

preprint2022arXiv

Hermitian adjacency matrix of the second kind for mixed graphs

This contribution gives an extensive study on spectra of mixed graphs via its Hermitian adjacency matrix of the second kind { ( $N$ -matrix for short)} introduced by Mohar \cite{0001}. This matrix is indexed by the vertices of the mixed graph, and the entry corresponding to an arc from $u$ to $v$ is equal to the sixth root of unity $ω=\frac{1+{\bf i}\sqrt{3}}{2}$ (and its symmetric entry is $\barω=\frac{1-{\bf i}\sqrt{3}}{2}$ ); the entry corresponding to an undirected edge is equal to 1, and 0 otherwise. The main results of this paper include the following: {equivalent} conditions for a mixed graph that shares the same spectrum of its $N$ -matrix with its underlying graph are given. A sharp upper bound on the spectral radius is established and the corresponding extremal mixed graphs are identified. Operations which are called two-way and three-way switchings are discussed--they give rise to some cospectral mixed graphs. We extract all the mixed graphs whose rank of its $N$ -matrix is $2$ (resp. 3). Furthermore, we show that {if $M_G$ is a connected mixed graph with rank $2,$ then $M_G$ is switching equivalent to each connected mixed graph to which it is cospectral}. However, this does not hold for some connected mixed graphs with rank $3$ . We identify all mixed graphs whose eigenvalues of its $N$ -matrix lie in the range $(-α,\, α)$ for $α\in\left\{\sqrt{2},\,\sqrt{3},\,2\right\}$ .

preprint2022arXiv

Sharp bounds on the $A_α$ -index of graphs in terms of the independence number

Given a graph $G$ , the adjacency matrix and degree diagonal matrix of $G$ are denoted by $A(G)$ and $D(G)$ , respectively. In 2017, Nikiforov \cite{0007} proposed the $A_α$ -matrix: $A_α(G)=αD(G)+(1-α)A(G),$ where $α\in [0, 1]$ . The largest eigenvalue of this novel matrix is called the $A_α$ -index of $G$ . In this paper, we characterize the graphs with minimum $A_α$ -index among $n$ -vertex graphs with independence number $i$ for $α\in[0,1)$ , where $i=1,\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil,{\lfloor\frac{n}{2}\rfloor+1},n-3,n-2,n-1,$ whereas for $i=2$ we consider the same problem for $α\in [0,\frac{3}{4}{]}.$ Furthermore, we determine the unique graph (resp. tree) on $n$ vertices with given independence number having the maximum $A_α$ -index with $α\in[0,1)$ , whereas for the $n$ -vertex bipartite graphs with given independence number, we characterize the unique graph having the maximum $A_α$ -index with $α\in[\frac{1}{2},1).$

preprint2021arXiv

An arithmetic criterion for graphs being determined by their generalized $A_α$ -spectrum

Let $G$ be a graph on $n$ vertices, its adjacency matrix and degree diagonal matrix are denoted by $A(G)$ and $D(G)$ , respectively. In 2017, Nikiforov \cite{0007} introduced the matrix $A_α(G)=αD(G)+(1-α)A(G)$ for $α\in [0, 1].$ The $A_α$ -spectrum of a graph $G$ consists of all the eigenvalues (including the multiplicities) of $A_α(G).$ A graph $G$ is said to be determined by the generalized $A_α$ -spectrum (or, DGA $_α$ S for short) if whenever $H$ is a graph such that $H$ and $G$ share the same $A_α$ -spectrum and so do their complements, then $H$ is isomorphic to $G$ . In this paper, when $α$ is rational, we present a simple arithmetic condition for a graph being DGA $_α$ S. More precisely, put $A_{c_α}:={c_α}A_α(G),$ here ${c_α}$ is the smallest positive integer such that $A_{c_α}$ is an integral matrix. Let $\tilde{W}_{α}(G)=\left[{\bf 1},\frac{A_{c_α}{\bf 1}}{c_α},\ldots, \frac{A_{c_α}^{n-1}{\bf 1}}{c_α}\right]$ , where ${\bf 1}$ denotes the all-ones vector. We prove that if $\frac{\det \tilde{W}_{α}(G)}{2^{\lfloor\frac{n}{2}\rfloor}}$ is an odd and square-free integer and the rank of $\tilde{W}_{α}(G)$ is full over $\mathbb{F}_p$ for each odd prime divisor $p$ of $c_α$ , then $G$ is DGA $_α$ S except for even $n$ and odd $c_α\,(\geqslant 3)$ . By our obtained results in this paper we may deduce the main results in \cite{0005} and \cite{0002}.

preprint2019arXiv

On the resistance distance and Kirchhoff index of a linear hexagonal (cylinder) chain

The resistance between two nodes in some resistor networks has been studied extensively by mathematicians and physicists. Let $L_n$ be a linear hexagonal chain with $n$ \, 6-cycles. Then identifying the opposite lateral edges of $L_n$ in ordered way yields the linear hexagonal cylinder chain, written as $R_n$ . We obtain explicit formulae for the resistance distance $r_{L_n}(i, j)$ (resp. $r_{R_n}(i,j)$ ) between any two vertices $i$ and $j$ of $L_n$ (resp. $R_n$ ). To the best of our knowledge $\{L_n\}_{n=1}^{\infty}$ and $\{R_n\}_{n=1}^{\infty}$ are two nontrivial families with diameter going to $\infty$ for which all resistance distances have been explicitly calculated. We determine the maximum and the minimum resistance distances in $L_n$ (resp. $R_n$ ). The monotonicity and some asymptotic properties of resistance distances in $L_n$ and $R_n$ are given. As well we give formulae for the Kirchhoff indices of $L_n$ and $R_n$ respectively.

preprint2015arXiv

'On the signless Laplacian spectra of $k$ -trees'-- CORRIGENDUM

In this paper, we use a new and correct method to determine the $n$ -vertex $k$ -trees with the first three largest signless Laplacian indices.

preprint2015arXiv

On a conjecture for the signless Laplacian spectral radius of cacti with given matching number

A connected graph $G$ is a cactus if any two of its cycles have at most one common vertex. Let $\ell_n^m$ be the set of cacti on $n$ vertices with matching number $m.$ S.C. Li and M.J. Zhang determined the unique graph with the maximum signless Laplacian spectral radius among all cacti in $\ell_n^m$ with $n=2m$ . In this paper, we characterize the case $n\geq 2m+1$ . This confirms the conjecture of Li and Zhang(S.C. Li, M.J. Zhang, On the signless Laplacian index of cacti with a given number of pendant vetices, Linear Algebra Appl. 436, 2012, 4400--4411). Further, we characterize the unique graph with the maximum signless Laplacian spectral radius among all cacti on $n$ vertices.

preprint2015arXiv

On the extremal total reciprocal edge-eccentricity of trees

The total reciprocal edge-eccentricity is a novel graph invariant with vast potential in structure activity/property relationships. This graph invariant displays high discriminating power with respect to both biological activity and physical properties. If $G=(V_G,E_G)$ is a simple connected graph, then the total reciprocal edge-eccentricity (REE) of $G$ is defined as $ξ^{ee}(G)=\sum_{uv\in E_G}(1/\varepsilon_G(u)+1/\varepsilon_G(v))$ , where $\varepsilon_G(v)$ is the eccentricity of the vertex $v$ . In this paper we first introduced four edge-grafting transformations to study the mathematical properties of the reciprocal edge-eccentricity of $G$ . Using these elegant mathematical properties, we characterize the extremal graphs among $n$ -vertex trees with given graphic parameters, such as pendants, matching number, domination number, diameter, vertex bipartition, et al. Some sharp bounds on the reciprocal edge-eccentricity of trees are determined.

preprint2013arXiv

Characterization of tricyclic graphs with exactly two $Q$ -main eigenvalues

The signless Laplacian matrix of a graph $G$ is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called $Q$ -eigenvalues of $G$ . A $Q$ -eigenvalue of a graph $G$ is called a $Q$ -main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Chen and Huang [L. Chen, Q.X. Huang, Trees, unicyclic graphs and bicyclic graphs with exactly two $Q$ -main eigenvalues, submitted for publication] characterized all trees, unicylic graphs and bicyclic graphs with exactly two main $Q$ -eigenvalues, respectively. As a continuance of it, in this paper, all tricyclic graphs with exactly two $Q$ -main eigenvalues are characterized.

preprint2013arXiv

On the eccentric distance sum of unicyclic graphs with a given matching number

Let $G = (V_G,E_G)$ be a simple connected graph. The eccentric distance sum of $G$ is defined as $ξ^d(G)=\sum_{v \in V_G}\,\varepsilon_G(v)D_G(v),$ where $\varepsilon_G(v)$ is the eccentricity of the vertex $v$ and $D_G(v)=\sum_{u \in V_G}\,d(u,v)$ is the sum of all distances from the vertex $v$ . In this paper, we characterize $n$ -vertex unicyclic graphs with given matching number having the minimal and second minimal eccentric distance sums, respectively.

preprint2013arXiv

On the positive and negative inertia of weighted graphs

The number of the positive, negative and zero eigenvalues in the spectrum of the (edge)-weighted graph $G$ are called positive inertia index, negative inertia index and nullity of the weighted graph $G$ , and denoted by $i_+(G)$ , $i_-(G)$ , $i_0(G)$ , respectively. In this paper, the positive and negative inertia index of weighted trees, weighted unicyclic graphs and weighted bicyclic graphs are discussed, the methods of calculating them are obtained.

preprint2013arXiv

The extremal problems on the inertia of weighted bicyclic graphs

Let $G_w$ be a weighted graph. The number of the positive, negative and zero eigenvalues in the spectrum of $G_w$ are called positive inertia index, negative inertia index and nullity of $G_w$ , and denoted by $i_{+}(G_w)$ , $i_{-}(G_w)$ , $i_{0}(G_w)$ , respectively. In this paper, sharp lower bound on the positive (resp. negative) inertia index of weighted bicyclic graphs of order $n$ with pendant vertices is obtained. Moreover, all the weighted bicyclic graphs of order $n$ with at most two positive, two negative and at least $n-4$ zero eigenvalues are identified, respectively.

preprint2012arXiv

Edge-grafting theorems on permanents of the Laplacian matrices of graphs and their applications

The trees, respectively unicyclic graphs, on $n$ vertices with the smallest Laplacian permanent are studied. In this paper, by edge-grafting transformations, the $n$ -vertex trees of given bipartition having the second and third smallest Laplacian permanent are identified. Similarly, the $n$ -vertex bipartite unicyclic graphs of given bipartition having the first, second and third smallest Laplacian permanent are characterized. Consequently, the $n$ -vertex bipartite unicyclic graphs with the first, second and third smallest Laplacian permanent are determined.

preprint2012arXiv

Enumerating the total number of subtrees of trees

Over some types of trees with a given number of vertices, which trees minimize or maximize the total number of subtrees or leaf containing subtrees are studied. Here are some of the main results:\ (1)\, Sharp upper bound on the total number of subtrees (resp. leaf containing subtrees) among $n$ -vertex trees with a given matching number is determined; as a consequence, the $n$ -vertex tree with domination number $γ$ maximizing the total number of subtrees (resp. leaf containing subtrees) is characterized. (2)\, Sharp lower bound on the total number of leaf containing subtrees among $n$ -vertex trees with maximum degree at least $Δ$ is determined; as a consequence the $n$ -vertex tree with maximum degree at least $Δ$ having a perfect matching minimizing the total number of subtrees (resp. leaf containing subtrees) is characterized. (3)\, Sharp upper (resp. lower) bound on the total number of leaf containing subtrees among the set of all $n$ -vertex trees with $k$ leaves (resp. the set of all $n$ -vertex trees of diameter $d$ ) is determined.

preprint2012arXiv

Extremal values on the eccentric distance sum of trees

Let $G=(V_G, E_G)$ be a simple connected graph. The eccentric distance sum of $G$ is defined as $ξ^{d}(G) = \sum_{v\in V_G}\varepsilon_{G}(v)D_{G}(v)$ , where $\varepsilon_G(v)$ is the eccentricity of the vertex $v$ and $D_G(v) = \sum_{u\in V_G}d_G(u,v)$ is the sum of all distances from the vertex $v$ . In this paper the tree among $n$ -vertex trees with domination number $γ$ having the minimal eccentric distance sum is determined and the tree among $n$ -vertex trees with domination number $γ$ satisfying $n = kγ$ having the maximal eccentric distance sum is identified, respectively, for $k=2,3,\frac{n}{3},\frac{n}{2}$ . Sharp upper and lower bounds on the eccentric distance sums among the $n$ -vertex trees with $k$ leaves are determined. Finally, the trees among the $n$ -vertex trees with a given bipartition having the minimal, second minimal and third minimal eccentric distance sums are determined, respectively.

preprint2012arXiv

Further analysis on the total number of subtrees of trees

We study that over some types of trees with a given number of vertices, which trees minimize or maximize the total number of subtrees. Trees minimizing (resp. maximizing) the total number of subtrees usually maximize (resp. minimize) the Wiener index, and vice versa. Here are some of our results: (1) Let $\mathscr{T}_n^k$ be the set of all $n$ -vertex trees with $k$ leaves, we determine the maximum (resp. minimum) value of the total number of subtrees of trees among $\mathscr{T}_n^k$ and characterize the extremal graphs. (2) Let $\mathscr{P}_n^{p,q}$ be the set of all $n$ -vertex trees, each of which has a $(p,q)$ -bipartition, we determine the maximum (resp. minimum) value of the total number of subtrees of trees among $\mathscr{P}_n^{p,q}$ and characterize the extremal graphs. (3) Let $\mathscr{A}_n^q$ be the set of all $q$ -ary trees with $n$ non-leaf vertices, we determine the minimum value of the total number of subtrees of trees among $\mathscr{A}_n^q$ and identify the extremal graph.

preprint2012arXiv

On the spectral moment of graphs with $k$ cut edges

Let $A(G)$ be the adjacency matrix of a graph $G$ with $λ_{1}(G)$ , $λ_{2}(G)$ , ..., $λ_{n}(G)$ being its eigenvalues in non-increasing order. Call the number $S_k(G):=\sum_{i=1}^{n}λ_{i}^k(G) (k=0,1,...,n-1)$ the $k$ th spectral moment of $G$ . Let $S(G)=(S_0(G),S_1(G),...,S_{n-1}(G))$ be the sequence of spectral moments of $G$ . For two graphs $G_1$ and $G_2$ , we have $G_1\prec_sG_2$ if $S_i(G_1)=S_i(G_2) (i=0,1,...,k-1)$ and $S_k(G_1)<S_k(G_2)$ for some $k\in {1,2,...,n-1}$ . Denote by $\mathscr{G}_n^k$ the set of connected $n$ -vertex graphs with $k$ cut edges. In this paper, we determine the first, the second, the last and the second last graphs, in an $S$ -order, among $\mathscr{G}_n^k$ , respectively.

preprint2012arXiv

On the spectral moment of graphs with given clique number

Let $\mathscr{L}_{n,t}$ be the set of all $n$ -vertex connected graphs with clique number $t$ \,( $2\leq t\leq n)$ . For $n$ -vertex connected graphs with given clique number, lexicographic ordering by spectral moments ( $S$ -order) is discussed in this paper. The first $\sum_{i=1}^{\lfloor\frac{n-t-1}{3}\rfloor}(n-t-3i)+1$ graphs with $3\le t\le n-4$ , and the last few graphs, in the $S$ -order, among $\mathscr{L}_{n,t}$ are characterized. In addition, all graphs in $\mathscr{L}_{n,n}\bigcup\mathscr{L}_{n,n-1}$ have an $S$ -order; for the cases $t=n-2$ and $t=n-3$ the first three and the first seven graphs in the set $\mathscr{L}_{n,t}$ are characterized, respectively.

preprint2012arXiv

On the spectral moments of trees with a given bipartition

For two given positive integers $p$ and $q$ with $p\leqslant q$ , we denote $\mathscr{T}_n^{p, q}={T: T$ is a tree of order $n$ with a $(p, q)$ -bipartition}. For a graph $G$ with $n$ vertices, let $A(G)$ be its adjacency matrix with eigenvalues $λ_1(G), λ_2(G), ..., λ_n(G)$ in non-increasing order. The number $S_k(G):=\sum_{i=1}^{n}λ_i^k(G)\,(k=0, 1, ..., n-1)$ is called the $k$ th spectral moment of $G$ . Let $S(G)=(S_0(G), S_1(G),..., S_{n-1}(G))$ be the sequence of spectral moments of $G$ . For two graphs $G_1$ and $G_2$ , one has $G_1\prec_s G_2$ if for some $k\in {1,2,...,n-1}$ , $S_i(G_1)=S_i(G_2) (i=0,1,...,k-1)$ and $S_k(G_1)<S_k(G_2)$ holds. In this paper, the last four trees, in the $S$ -order, among $\mathscr{T}_n^{p, q} (4\leqslant p\leqslant q)$ are characterized.

Shuchao Li

Research overview

Is this your work?

18 publications

Hermitian adjacency matrix of the second kind for mixed graphs

Sharp bounds on the $A_α$ -index of graphs in terms of the independence number

An arithmetic criterion for graphs being determined by their generalized $A_α$ -spectrum

On the resistance distance and Kirchhoff index of a linear hexagonal (cylinder) chain

'On the signless Laplacian spectra of $k$ -trees'-- CORRIGENDUM

On a conjecture for the signless Laplacian spectral radius of cacti with given matching number

On the extremal total reciprocal edge-eccentricity of trees

Characterization of tricyclic graphs with exactly two $Q$ -main eigenvalues

On the eccentric distance sum of unicyclic graphs with a given matching number

On the positive and negative inertia of weighted graphs

The extremal problems on the inertia of weighted bicyclic graphs

Edge-grafting theorems on permanents of the Laplacian matrices of graphs and their applications

Enumerating the total number of subtrees of trees

Extremal values on the eccentric distance sum of trees

Further analysis on the total number of subtrees of trees

On the spectral moment of graphs with $k$ cut edges

On the spectral moment of graphs with given clique number

On the spectral moments of trees with a given bipartition

See the researcher in context

Building this map preview

Shuchao Li

Research overview

Is this your work?

18 publications

Hermitian adjacency matrix of the second kind for mixed graphs

Sharp bounds on the AαA_αAα​-index of graphs in terms of the independence number

An arithmetic criterion for graphs being determined by their generalized AαA_αAα​-spectrum

On the resistance distance and Kirchhoff index of a linear hexagonal (cylinder) chain

'On the signless Laplacian spectra of kkk-trees'-- CORRIGENDUM

On a conjecture for the signless Laplacian spectral radius of cacti with given matching number

On the extremal total reciprocal edge-eccentricity of trees

Characterization of tricyclic graphs with exactly two QQQ-main eigenvalues

On the eccentric distance sum of unicyclic graphs with a given matching number

On the positive and negative inertia of weighted graphs

The extremal problems on the inertia of weighted bicyclic graphs

Edge-grafting theorems on permanents of the Laplacian matrices of graphs and their applications

Enumerating the total number of subtrees of trees

Extremal values on the eccentric distance sum of trees

Further analysis on the total number of subtrees of trees

On the spectral moment of graphs with kkk cut edges

On the spectral moment of graphs with given clique number

On the spectral moments of trees with a given bipartition

See the researcher in context

Building this map preview

Sharp bounds on the $A_α$ -index of graphs in terms of the independence number

An arithmetic criterion for graphs being determined by their generalized $A_α$ -spectrum

'On the signless Laplacian spectra of $k$ -trees'-- CORRIGENDUM

Characterization of tricyclic graphs with exactly two $Q$ -main eigenvalues

On the spectral moment of graphs with $k$ cut edges