BZPEER

preprint2026arXiv

Distance spectral radius conditions for edge-disjoint spanning trees and a forest with constraints

Let $k\ge 2$ be a positive integer and let $G$ be a simple graph of order $n$ with minimum degree $δ$ . A graph $G$ is said to have property $P(k, d)$ if it contains $k$ edge-disjoint spanning trees and an additional forest $F$ with edge number $|E(F)| > \frac{d-1}{d}(n-1)$ , such that if $F$ is not a spanning tree, then $F$ has a component with at least $d$ edges. Let $D(G)$ be the distance matrix of $G$ . We denote $ρ_D(G)$ as the largest eigenvalue of $D(G)$ , which is called the distance spectral radius of $G$ . In this paper, we investigate the relationship between the distance spectral radius and the property $P(k, δ)$ . We prove that for a connected graph $G$ of order $n \ge 2k+8$ with minimum degree $δ\ge k+2$ , if $ρ_D(G) \le ρ_D(K_{k-1} \vee (K_{n-k} \cup K_1))$ , then $G$ possesses property $P(k, δ)$ . Furthermore, for a connected balanced bipartite graph $G$ of order $n \ge 4k+8$ with minimum degree $δ\ge k+2$ , we show that if $ρ_D(G) \le ρ_D(K_{\frac{n}{2}, \frac{n}{2}} \setminus E(K_{1, \frac{n}{2}-k+1}))$ , then $G$ also possesses property $P(k, δ)$ . Our results generalize the work of Fan et al. [Discrete Appl. Math. 376 (2025), 31--40] from the existence of $k$ edge-disjoint spanning trees to the more refined structural property $P(k, δ)$ .

preprint2026arXiv

Laplacian eigenvalue conditions for edge-disjoint spanning trees and a forest with constraints

Let $k$ be a positive integer and let $G$ be a simple graph of order $n$ with minimum degree $δ$ . A graph $G$ is said to have property $P(k, d)$ if it contains $k$ edge-disjoint spanning trees and an additional forest $F$ with edge number $|E(F)| > \frac{d-1}{d}(|V(G)| - 1)$ , such that if $F$ is not a spanning tree, then $F$ has a component with at least $d$ edges. Let $D(G)$ be the degree diagonal matrix of $G$ . We denote $λ_i$ and $μ_i$ as the $i$ th largest eigenvalue of the adjacency matrix $A(G)$ of $G$ and the Laplacian matrix $L(G) = D(G) - A(G)$ of $G$ for $i = 1, 2, \ldots, n$ , respectively. In this paper, we investigate the relationship between Laplacian eigenvalues and property $P(k, δ)$ . Let $t$ be a positive integer, and define $\mathcal{G}_t$ as the set of simple graphs such that each $G \in \mathcal{G}_t$ contains at least $t+1$ non-empty disjoint proper subsets $V_1, V_2, \ldots, V_{t+1}$ satisfying $V(G) \setminus \bigcup_{i=1}^{t+1} V_i \neq \emptyset$ and edge connectivity $κ'(G) = e(V_i, V(G) \setminus V_i)$ for any $i = 1, 2, \ldots, t+1$ . For the class of graphs $\mathcal{G}_1$ with minimum degree $δ$ , we provide a sufficient condition involving the third smallest Laplacian eigenvalue $μ_{n-2}(G)$ for a graph $G\in \mathcal{G}_1$ to have property $P(k, δ)$ . Similarly, for the class of graphs $\mathcal{G}_2$ with minimum degree $δ$ , we establish a corresponding sufficient condition involving the fourth smallest Laplacian eigenvalue $μ_{n-3}(G)$ for a graph $G\in \mathcal{G}_2$ to have property $P(k, δ)$ . Furthermore, we extend the spectral conditions for all the results about $μ_{n-2}(G)$ , $μ_{n-3}(G)$ and $λ_2(G)$ to the general graph matrices $aD(G) + A(G)$ and $aD(G) + bA(G)$ .

preprint2022arXiv

Integer colorings with no rainbow 3-term arithmetic progression

In this paper, we study the rainbow Erdős-Rothschild problem with respect to 3-term arithmetic progressions. We obtain the asymptotic number of $r$ -colorings of $[n]$ without rainbow 3-term arithmetic progressions, and we show that the typical colorings with this property are 2-colorings. We also prove that $[n]$ attains the maximum number of rainbow 3-term arithmetic progression-free $r$ -colorings among all subsets of $[n]$ . Moreover, the exact number of rainbow 3-term arithmetic progression-free $r$ -colorings of $\mathbb{Z}_p$ is obtained, where $p$ is any prime and $\mathbb{Z}_p$ is the cyclic group of order $p$ .

preprint2022arXiv

On the $α$ -index of minimally 2-connected graphs with given order or size

For any real $α\in [0,1]$ , Nikiforov defined the $A_α$ -matrix of a graph $G$ as $A_α(G)=αD(G)+(1-α)A(G)$ , where $A(G)$ and $D(G)$ are the adjacency matrix and the diagonal matrix of vertex degrees of $G$ , respectively. The largest eigenvalue of $A_α(G)$ is called the $α$ -index or the $A_α$ -spectral radius of $G$ . A graph is minimally $k$ -connected if it is $k$ -connected and deleting any arbitrary chosen edge always leaves a graph which is not $k$ -connected. In this paper, we characterize the extremal graphs with the maximum $α$ -index for $α\in [\frac{1}{2},1)$ among all minimally 2-connected graphs with given order or size, respectively.

preprint2022arXiv

Signless Laplacian Estrada index and Laplacian Estrada index of uniform hypergraphs

We generalize the notions of Laplacian and signless Laplacian Estrada index to uniform hypergraphs. For an $r$ -uniform hypergraph $H,$ we derive an order $r+1$ trace formula of the (signless) Laplacian tensor of $H.$ Among others by using this trace formula, we obtain lower bounds for the signless Laplacian Estrada index and upper bounds for the Laplacian Estrada index. Moreover, we establish a bound involving both the Laplacian Estrada index and Laplacian energy of a uniform hypergraph.

preprint2021arXiv

Extremal problems and results related to Gallai-colorings

A Gallai-coloring (Gallai- $k$ -coloring) is an edge-coloring (with colors from $\{1, 2, \ldots, k\}$ ) of a complete graph without rainbow triangles. Given a graph $H$ and a positive integer $k$ , the $k$ -colored Gallai-Ramsey number $GR_k(H)$ is the minimum integer $n$ such that every Gallai- $k$ -coloring of the complete graph $K_n$ contains a monochromatic copy of $H$ . In this paper, we consider two extremal problems related to Gallai- $k$ -colorings. First, we determine upper and lower bounds for the maximum number of edges that are not contained in any rainbow triangle or monochromatic triangle in a $k$ -edge-coloring of $K_n$ . Second, for $n\geq GR_k(K_3)$ , we determine upper and lower bounds for the minimum number of monochromatic triangles in a Gallai- $k$ -coloring of $K_{n}$ , yielding the exact value for $k=3$ . Furthermore, we determine the Gallai-Ramsey number $GR_k(K_4+e)$ for the graph on five vertices consisting of a $K_4$ with a pendant edge.

preprint2021arXiv

The Erdős-Gyárfás function with respect to Gallai-colorings

For fixed $p$ and $q$ , an edge-coloring of the complete graph $K_n$ is said to be a $(p, q)$ -coloring if every $K_p$ receives at least $q$ distinct colors. The function $f(n, p, q)$ is the minimum number of colors needed for $K_n$ to have a $(p, q)$ -coloring. This function was introduced about 45 years ago, but was studied systematically by Erdős and Gyárfás in 1997, and is now known as the Erdős-Gyárfás function. In this paper, we study $f(n, p, q)$ with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of $K_n$ without rainbow triangles. Combining the two concepts, we consider the function $g(n, p, q)$ that is the minimum number of colors needed for a Gallai- $(p, q)$ -coloring of $K_n$ . Using the anti-Ramsey number for $K_3$ , we have that $g(n, p, q)$ is nontrivial only for $2\leq q\leq p-1$ . We give a general lower bound for this function and we study how this function falls off from being equal to $n-1$ when $q=p-1$ and $p\geq 4$ to being $Θ(\log n)$ when $q = 2$ . In particular, for appropriate $p$ and $n$ , we prove that $g=n-c$ when $q=p-c$ and $c\in \{1,2\}$ , $g$ is at most a fractional power of $n$ when $q=\lfloor\sqrt{p-1}\rfloor$ , and $g$ is logarithmic in $n$ when $2\leq q\leq \lfloor\log_2 (p-1)\rfloor+1$ .

preprint2021arXiv

The generalized Turán number of spanning linear forests

Let $\mathcal{F}$ be a family of graphs. A graph $G$ is called \textit{ $\mathcal{F}$ -free} if for any $F\in \mathcal{F}$ , there is no subgraph of $G$ isomorphic to $F$ . Given a graph $T$ and a family of graphs $\mathcal{F}$ , the generalized Turán number of $\mathcal{F}$ is the maximum number of copies of $T$ in an $\mathcal{F}$ -free graph on $n$ vertices, denoted by $ex(n,T,\mathcal{F})$ . A linear forest is a graph whose connected components are all paths or isolated vertices. Let $\mathcal{L}_{n,k}$ be the family of all linear forests of order $n$ with $k$ edges and $K^*_{s,t}$ a graph obtained from $K_{s,t}$ by substituting the part of size $s$ with a clique of the same size. In this paper, we determine the exact values of $ex(n,K_s,\mathcal{L}_{n,k})$ and $ex(n,K^*_{s,t},\mathcal{L}_{n,k})$ . Also, we study the case of this problem when the \textit{"host graph"} is bipartite. Denote by $ex_{bip}(n,T,\mathcal{F})$ the maximum possible number of copies of $T$ in an $\mathcal{F}$ -free bipartite graph with each part of size $n$ . We determine the exact value of $ex_{bip}(n,K_{s,t},\mathcal{L}_{n,k})$ . Our proof is mainly based on the shifting method.

preprint2020arXiv

Hypothesis Testing Over the Two-hop Relay Network

Coding and testing schemes and the corresponding achievable type-II error exponents are presented for binary hypothesis testing over two-hop relay networks. The schemes are based on cascade source coding techniques and {unanimous decision-forwarding}, the latter meaning that a terminal decides on the null hypothesis only if all previous terminals have decided on the null hypothesis. If the observations at the transmitter, the relay, and the receiver form a Markov chain in this order, then, without loss in performance, the proposed cascade source code can be replaced by two independent point-to-point source codes, one for each hop. The decoupled scheme (combined with decision-forwarding) is shown to attain the optimal type-II error exponents for various instances of "testing against conditional independence." The same decoupling is shown to be optimal also for some instances of "testing against independence," when the observations at the transmitter, the receiver, and the relay form a Markov chain in this order, and when the relay-to-receiver link is of sufficiently high rate. For completeness, the paper also presents an analysis of the Shimokawa-Han-Amari binning scheme for the point-to-point hypothesis testing setup.

preprint2020arXiv

Iota energy orderings of bicyclic signed digraphs

The concept of energy of a signed digraph is extended to iota energy of a signed digraph. The energy of a signed digraph $S$ is defined by $E(S)=\sum_{k=1}^n|\text{Re}(z_k)|$ , where $\text{Re}(z_k)$ is the real part of eigenvalue $z_k$ and $z_k$ is the eigenvalue of the adjacency matrix of $S$ with $n$ vertices, $k=1,2,\ldots,n$ . Then the iota energy of $S$ is defined by $E(S)=\sum_{k=1}^n|\text{Im}(z_k)|$ , where $\text{Im}(z_k)$ is the imaginary part of eigenvalue $z_k$ . In this paper, we consider a special graph class for bicyclic signed digraphs $\mathcal{S}_n$ with $n$ vertices which have two vertex-disjoint signed directed even cycles. We give two iota energy orderings of bicyclic signed digraphs, one is including two positive or two negative directed even cycles, the other is including one positive and one negative directed even cycles.

preprint2020arXiv

On the Capacity of MIMO Optical Wireless Channels

This paper studies the capacity of a general multiple-input multiple-output (MIMO) free-space optical intensity channel under a per-input-antenna peak-power constraint and a total average-power constraint over all input antennas. The focus is on the scenario with more transmit than receive antennas. In this scenario, different input vectors can yield identical distributions at the output, when they result in the same image vector under multiplication by the channel matrix. We first determine the most energy-efficient input vectors that attain each of these image vectors. Based on this, we derive an equivalent capacity expression in terms of the image vector, and establish new lower and upper bounds on the capacity of this channel. The bounds match when the signal-to-noise ratio (SNR) tends to infinity, establishing the high-SNR asymptotic capacity. We also characterize the low-SNR slope of the capacity of this channel.

preprint2020arXiv

The bounds of the spectral radius of general hypergraphs in terms of clique number

The spectral radius (or the signless Laplacian spectral radius) of a general hypergraph is the maximum modulus of the eigenvalues of its adjacency (or its signless Laplacian) tensor. In this paper, we firstly obtain a lower bound of the spectral radius (or the signless Laplacian spectral radius) of general hypergraphs in terms of clique number. Moreover, we present a relation between a homogeneous polynomial and the clique number of general hypergraphs. As an application, we finally obtain an upper bound of the spectral radius of general hypergraphs in terms of clique number.

preprint2016arXiv

5-regular oriented graphs with optimum skew energy

Let $G$ be a simple undirected graph and $G^σ$ be the corresponding oriented graph of $G$ with the orientation $σ$ . The skew energy of $G^σ$ , denoted by $\varepsilon_s(G^σ)$ , is defined as the sum of the singular values of the skew adjacency matrix $S(G^σ)$ . In 2010, Adiga et al. certified that $\varepsilon_s(G^σ) \leq n\sqrtΔ$ , where $Δ$ is the maximum degree of $G$ of order $n$ . In this paper, we determine all connected 5-regular oriented graphs of order $n$ with maximum skew-energy.

preprint2016arXiv

A new S-type eigenvalue localization set for tensors and its applications

A new \emph{S}-type eigenvalue localization set for tensors is derived by breaking $N=\{1,2,\cdots,n\}$ into disjoint subsets $S$ and its complement. It is proved that this new set is tighter than those presented by Qi (Journal of Symbolic Computation 40 (2005) 1302-1324), Li et al. (Numer. Linear Algebra Appl. 21 (2014) 39-50) and Li et al. (Linear Algebra Appl. 493 (2016) 469-483). As applications, checkable sufficient conditions for the positive definiteness and the positive semi-definiteness of tensors are proposed. Moreover, based on this new set, we establish a new upper bound for the spectral radius of nonnegative tensors and a lower bound for the minimum \emph{H}-eigenvalue of weakly irreducible strong \emph{M}-tensors in this paper. We demonstrate that these bounds are sharper than those obtained by Li et al. (Numer. Linear Algebra Appl. 21 (2014) 39-50) and He and Huang (J. Inequal. Appl. 114 (2014) 2014). Numerical examples are also given to illustrate this fact.

preprint2016arXiv

Distance signless Laplacian spectral radius and Hamiltonian properties of graphs

In this paper, first, we establish a sufficient condition for a bipartite graph to be Hamilton-connected. Furthermore, we also give two sufficient conditions on distance signless Laplacian spectral radius for a graph to be Hamilton-connected and traceable from every vertex, respectively. Last, we obtain a sufficient condition for a graph to be Hamiltonian in terms of the distance signless Laplacian spectral radius of $G^{C}$ .

preprint2016arXiv

Fundamental Limits of Communication with Low Probability of Detection

This paper considers the problem of communication over a discrete memoryless channel (DMC) or an additive white Gaussian noise (AWGN) channel subject to the constraint that the probability that an adversary who observes the channel outputs can detect the communication is low. Specifically, the relative entropy between the output distributions when a codeword is transmitted and when no input is provided to the channel must be sufficiently small. For a DMC whose output distribution induced by the "off" input symbol is not a mixture of the output distributions induced by other input symbols, it is shown that the maximum amount of information that can be transmitted under this criterion scales like the square root of the blocklength. The same is true for the AWGN channel. Exact expressions for the scaling constant are also derived.

preprint2016arXiv

Hermitian-Randić matrix and Hermitian-Randić energy of mixed graphs

Let $M$ be a mixed graph and $H(M)$ be its Hermitian-adjacency matrix. If we add every edge and arc in $M$ a Randić weight, then we can get a new weighted Hermitian-adjacency matrix. What are the properties of this new matrix? Motivated by this, we define the Hermitian-Randić matrix $R_{H}(M)=(r_{h})_{kl}$ of a mixed graph $M$ , where $(r_{h})_{kl}=-(r_{h})_{lk}=\frac{\textbf{i}}{\sqrt{d_{k}d_{l}}}$ ( $\textbf{i}=\sqrt{-1}$ ) if $(v_{k},v_{l})$ is an arc of $M$ , $(r_{h})_{kl}=(r_{h})_{lk}=\frac{1}{\sqrt{d_{k}d_{l}}}$ if $v_{k}v_{l}$ is an undirected edge of $M$ , and $(r_{h})_{kl}=0$ otherwise. In this paper, firstly, we compute the characteristic polynomial of the Hermitian-Randić matrix of a mixed graph. Furthermore, we give bounds to the Hermitian-Randić energy of a general mixed graph. Finally, we give some results about the Hermitian-Randić energy of mixed trees.

preprint2016arXiv

Minimal Skew energy of oriented bicyclic graphs with a given diameter

Let $S(G^σ)$ be the skew-adjacency matrix of the oriented graph $G^σ$ , which is obtained from a simple undirected graph $G$ by assigning an orientation $σ$ to each of its edges. The skew energy of an oriented graph $G^σ$ is defined as the sum of absolute values of all eigenvalues of $S(G^σ)$ . For any positive integer $d$ with $3\leq d\leq n-3$ , we determine the graph with minimal skew energy among all oriented bicyclic graphs that contain no vertex disjoint odd cycle of lengths $s$ and $l$ with $s+l\equiv 2(mod 4)$ on $n$ vertices with a given diameter $d$ .

preprint2016arXiv

On the second smallest and the largest normalized Laplacian eigenvalues of a graph

Let $G$ be a simple connected graph with order $n$ . Let $\mathcal{L}(G)$ be the normalized Laplacian matrix of $G$ . Let $λ_{k}(G)$ be the $k$ -th smallest normalized Laplacian eigenvalue of $G$ . Denote $ρ(A)$ the spectral radius of the matrix $A$ . In this paper, we study the behaviors of $λ_{2}(G)$ and $ρ(\mathcal{L}(G))$ when the graph is perturbed by three operations.

preprint2016arXiv

On the signless Laplacian spectral radius of $C_{4}$ -free $k$ -cyclic graphs

A $k$ -cyclic graph is a connected graph of order $n$ and size $n+k-1$ . In this paper, we determine the maximal signless Laplacian spectral radius and the corresponding extremal graph among all $C_{4}$ -free $k$ -cyclic graphs of order $n$ . Furthermore, we determine the first three unicyclic, and bicyclic, $C_{4}$ -free graphs whose spectral radius of the signless Laplacian is maximal. Similar results are obtained for the (combinatorial) Laplacian.

preprint2016arXiv

Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph

Let $G^σ$ be an oriented graph and $S(G^σ)$ be its skew-adjacency matrix, where $G$ is called the underlying graph of $G^σ$ . The skew-rank of $G^σ$ , denoted by $sr(G^σ)$ , is the rank of $S(G^σ)$ . Denote by $d(G)=|E(G)|-|V(G)|+θ(G)$ the dimension of cycle spaces of $G$ , where $|E(G)|$ , $|V(G)|$ and $θ(G)$ are the edge number, vertex number and the number of connected components of $G$ , respectively. Recently, Wong, Ma and Tian [European J. Combin. 54 (2016) 76--86] proved that $sr(G^σ)\leq r(G)+2d(G)$ for an oriented graph $G^σ$ , where $r(G)$ is the rank of the adjacency matrix of $G$ , and characterized the graphs whose skew-rank attain the upper bound. However, the problem of the lower bound of $sr(G^σ)$ of an oriented graph $G^σ$ in terms of $r(G)$ and $d(G)$ of its underlying graph $G$ is left open till now. In this paper, we prove that $sr(G^σ)\geq r(G)-2d(G)$ for an oriented graph $G^σ$ and characterize the graphs whose skew-rank attain the lower bound.

preprint2016arXiv

Some upper bounds for the signless Laplacian spectral radius of digraphs

Let $G=(V(G) ,E(G))$ be a digraph without loops and multiarcs, where $V(G)=\{v_1,v_2,\ldots,v_n\}$ and $E(G)$ are the vertex set and the arc set of $G$ , respectively. Let $d_i^{+}$ be the outdegree of the vertex $v_i$ . Let $A(G)$ be the adjacency matrix of $G$ and $D(G)=\textrm{diag}(d_1^{+},d_2^{+},\ldots,d_n^{+})$ be the diagonal matrix with outdegrees of the vertices of $G$ . Then we call $Q(G)=D(G)+A(G)$ the signless Laplacian matrix of $G$ . The spectral radius of $Q(G)$ is called the signless Laplacian spectral radius of $G$ , denoted by $q(G)$ . In this paper, some upper bounds for $q(G)$ are obtained. Furthermore, some upper bounds on $q(G)$ involving outdegrees and the average 2-outdegrees of the vertices of $G$ are also derived.

preprint2016arXiv

The signless Laplacian spectral radius of subgraphs of regular graphs

Let $q(H)$ be the signless Laplacian spectral radius of a graph $H$ . In this paper, we prove that \\1. Let $H$ be a proper subgraph of a $Δ$ -regular graph $G$ with $n$ vertices and diameter $D$ . Then $2Δ- q(H)>\frac{1}{n(D-\frac{1}{4})}.$ \\2. Let $H$ be a proper subgraph of a $k$ -connected $Δ$ -regular graph $G$ with $n$ vertices, where $k\geq 2$ . Then $2Δ-q(H)>\frac{2(k-1)^{2}}{2(n-Δ)(n-Δ+2k-4)+(n+1)(k-1)^{2}}.$ Finally, we compare the two bounds. We obtain that when $k>2\sqrt{\frac{(n-Δ)(n+Δ-4)}{n(4D-3)-2}}+1$ , the second bound is always better than the first. On the other hand, when $k<\frac{2(n-Δ)}{\sqrt{n(4D-3)-2}}+1$ , the first bound is always better than the second.

preprint2016arXiv

Upper bounds on the Q-spectral radius of book-free and/or $K_{s,t}$ -free graphs

In this paper, we prove two results about the signless Laplacian spectral radius $q(G)$ of a graph $G$ of order $n$ with maximum degree $Δ$ . Let $B_{n}=K_{2}+\overline{K_{n}}$ denote a book, i.e., the graph $B_{n}$ consists of $n$ triangles sharing an edge. (1) Let $1< k\leq l< Δ< n$ and $G$ be a connected \{ $B_{k+1},K_{2,l+1}$ \}-free graph of order $n$ with maximum degree $Δ$ . Then $\displaystyle q(G)\leq \frac{1}{4}[3Δ+k-2l+1+\sqrt{(3Δ+k-2l+1)^{2}+16l(Δ+n-1)}.$ with equality holds if and only if $G$ is a strongly regular graph with parameters ( $Δ$ , $k$ , $l$ ). (2) Let $s\geq t\geq 3$ , and let $G$ be a connected $K_{s,t}$ -free graph of order $n$ $(n\geq s+t)$ . Then $q(G)\leq n+(s-t+1)^{1/t}n^{1-1/t}+(t-1)(n-1)^{1-3/t}+t-3.$

preprint2015arXiv

Complex unit gain bicyclic graphs with rank 2, 3 or 4

A $\mathbb{T}$ -gain graph is a triple $Φ=(G,\mathbb{T},φ)$ consisting of a graph $G=(V,E)$ , the circle group $\mathbb{T}=\{z\in C: |z|=1\}$ and a gain function $φ:\overrightarrow{E}\rightarrow \mathbb{T}$ such that $φ(e_{ij})=φ(e_{ji})^{-1}=\overline{φ(e_{ji})}$ . The rank of $\mathbb{T}$ -gain graph $Φ$ , denoted by $r(Φ)$ , is the rank of the adjacency matrix of $Φ$ . In 2015, Yu, Qu and Tu [ G. H. Yu, H. Qu, J. H. Tu, Inertia of complex unit gain graphs, Appl. Math. Comput. 265(2015) 619--629 ] obtained some properties of inertia of a $\mathbb{T}$ -gain graph. They characterized the $\mathbb{T}$ -gain unicyclic graphs with small positive or negative index. Motivated by above, in this paper, we characterize the complex unit gain bicyclic graphs with rank 2, 3 or 4.

preprint2015arXiv

Distance integral complete multipartite graphs with $s=5,6$

Let $D(G)=(d_{ij})_{n\times n}$ denote the distance matrix of a connected graph $G$ with order $n$ , where $d_{ij}$ is equal to the distance between vertices $v_{i}$ and $v_{j}$ in $G$ . A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a sufficient and necessary condition for complete $r$ -partite graphs $K_{p_{1},p_{2},\ldots,p_{r}}=K_{a_{1}\cdot p_{1},a_{2}\cdot p_{2},\ldots,a_{s}\cdot p_{s}}$ to be distance integral and obtained such distance integral graphs with $s=1,2,3,4$ . However distance integral complete multipartite graphs $K_{a_{1}\cdot p_{1},a_{2}\cdot p_{2},\ldots,a_{s}\cdot p_{s}}$ with $s>4$ have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs $K_{a_{1}\cdot p_{1},a_{2}\cdot p_{2},\ldots,a_{s}\cdot p_{s}}$ with $s=5,6$ . The problem of the existence of such distance integral graphs $K_{a_{1}\cdot p_{1},a_{2}\cdot p_{2},\ldots,a_{s}\cdot p_{s}}$ with arbitrarily large number $s$ remains open.

preprint2015arXiv

Photon-efficient quantum cryptography with pulse-position modulation

The binary (one-bit-per-photon) encoding that most existing quantum key distribution (QKD) protocols employ puts a fundamental limit on their achievable key rates, especially under high channel loss conditions associated with long-distance fiber-optic or satellite-to-ground links. Inspired by the pulse-position-modulation (PPM) approach to photon-starved classical communications, we design and demonstrate the first PPM-QKD, whose security against collective attacks is established through continuous-variable entanglement measurements that also enable a novel decoy-state protocol performed conveniently in post processing. We achieve a throughput of 8.0 Mbit/s (2.5 Mbit/s for loss equivalent to 25 km of fiber) and secret-key capacity up to 4.0 bits per detected photon, thus demonstrating the significant enhancement afforded by high-dimensional encoding. These results point to a new avenue for realizing high-throughput satellite-based or long-haul fiber-optic quantum communications beyond their photon-reception-rate limits.

preprint2014arXiv

A refined analysis of the Poisson channel in the high-photon-efficiency regime

We study the discrete-time Poisson channel under the constraint that its average input power (in photons per channel use) must not exceed some constant E. We consider the wideband, high-photon-efficiency extreme where E approaches zero, and where the channel's "dark current" approaches zero proportionally with E. Improving over a previously obtained first-order capacity approximation, we derive a refined approximation, which includes the exact characterization of the second-order term, as well as an asymptotic characterization of the third-order term with respect to the dark current. We also show that pulse-position modulation is nearly optimal in this regime.

preprint2014arXiv

Toward Photon-Efficient Key Distribution over Optical Channels

This work considers the distribution of a secret key over an optical (bosonic) channel in the regime of high photon efficiency, i.e., when the number of secret key bits generated per detected photon is high. While in principle the photon efficiency is unbounded, there is an inherent tradeoff between this efficiency and the key generation rate (with respect to the channel bandwidth). We derive asymptotic expressions for the optimal generation rates in the photon-efficient limit, and propose schemes that approach these limits up to certain approximations. The schemes are practical, in the sense that they use coherent or temporally-entangled optical states and direct photodetection, all of which are reasonably easy to realize in practice, in conjunction with off-the-shelf classical codes.

preprint2013arXiv

One-Shot Classical-Quantum Capacity and Hypothesis Testing

The one-shot classical capacity of a quantum channel quantifies the amount of classical information that can be transmitted through a single use of the channel such that the error probability is below a certain threshold. In this work, we show that this capacity is well approximated by a relative-entropy-type measure defined via hypothesis testing. Combined with a quantum version of Stein's lemma, our results give a conceptually simple proof of the well-known Holevo-Schumacher-Westmoreland theorem for the capacity of memoryless channels. More generally, we obtain tight capacity formulas for arbitrary (not necessarily memoryless) channels.

preprint2012arXiv

Private-Capacity Bounds for Bosonic Wiretap Channels

We prove an upper bound on the private capacity of the single-mode noiseless bosonic wiretap channel. Combined with a previous lower bound, we obtain the low photon-number asymptotic expression for the private capacity. We then show that the multiple-mode noiseless bosonic wiretap channel is equivalent to parallel single-mode channels, hence the single-mode bounds can be applied. Finally, we consider multiple-spatial-mode propagation through atmospheric turbulence, and derive a private-capacity lower bound that only requires second moments of the channel matrix.

preprint2012arXiv

The State-Dependent Semideterministic Broadcast Channel

We derive the capacity region of the state-dependent semideterministic broadcast channel with noncausal state-information at the transmitter. One of the two outputs of this channel is a deterministic function of the channel input and the channel state, and the state is assumed to be known noncausally to the transmitter but not to the receivers. We show that appending the state to the deterministic output does not increase capacity. We also derive an outer bound on the capacity of general (not necessarily semideterministic) state-dependent broadcast channels.

preprint2010arXiv

It takes half the energy of a photon to send one bit reliably on the Poisson channel with feedback

We consider the transmission of a single bit over the continuous-time Poisson channel with noiseless feedback. We show that to send the bit reliably requires, on the average, half the energy of a photon. In the absence of peak-power constraints this holds irrespective of the intensity of the dark current. We also solve for the energy required to send $log_{2} M$ bits.

preprint2010arXiv

Simple Channel Coding Bounds

New channel coding converse and achievability bounds are derived for a single use of an arbitrary channel. Both bounds are expressed using a quantity called the "smooth 0-divergence", which is a generalization of Renyi's divergence of order 0. The bounds are also studied in the limit of large block-lengths. In particular, they combine to give a general capacity formula which is equivalent to the one derived by Verdu and Han.

preprint2008arXiv

Low SNR Capacity of Noncoherent Fading Channels

Discrete-time Rayleigh fading single-input single-output (SISO) and multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter or the receiver. The fading is assumed to be stationary and correlated in time, but independent from antenna to antenna. Peak-power and average-power constraints are imposed on the transmit antennas. For MIMO channels, these constraints are either imposed on the sum over antennas, or on each individual antenna. For SISO channels and MIMO channels with sum power constraints, the asymptotic capacity as the peak signal-to-noise ratio tends to zero is identified; for MIMO channels with individual power constraints, this asymptotic capacity is obtained for a class of channels called transmit separable channels. The results for MIMO channels with individual power constraints are carried over to SISO channels with delay spread (i.e. frequency selective fading).

Ligong Wang

Research overview

Is this your work?

35 publications

Distance spectral radius conditions for edge-disjoint spanning trees and a forest with constraints

Laplacian eigenvalue conditions for edge-disjoint spanning trees and a forest with constraints

Integer colorings with no rainbow 3-term arithmetic progression

On the ααα-index of minimally 2-connected graphs with given order or size

Signless Laplacian Estrada index and Laplacian Estrada index of uniform hypergraphs

Extremal problems and results related to Gallai-colorings

The Erdős-Gyárfás function with respect to Gallai-colorings

The generalized Turán number of spanning linear forests

Hypothesis Testing Over the Two-hop Relay Network

Iota energy orderings of bicyclic signed digraphs

On the Capacity of MIMO Optical Wireless Channels

The bounds of the spectral radius of general hypergraphs in terms of clique number

5-regular oriented graphs with optimum skew energy

A new S-type eigenvalue localization set for tensors and its applications

Distance signless Laplacian spectral radius and Hamiltonian properties of graphs

Fundamental Limits of Communication with Low Probability of Detection

Hermitian-Randić matrix and Hermitian-Randić energy of mixed graphs

Minimal Skew energy of oriented bicyclic graphs with a given diameter

On the second smallest and the largest normalized Laplacian eigenvalues of a graph

On the signless Laplacian spectral radius of C4C_{4}C4​-free kkk-cyclic graphs

Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph

Some upper bounds for the signless Laplacian spectral radius of digraphs

The signless Laplacian spectral radius of subgraphs of regular graphs

Upper bounds on the Q-spectral radius of book-free and/or Ks,tK_{s,t}Ks,t​-free graphs

Complex unit gain bicyclic graphs with rank 2, 3 or 4

Distance integral complete multipartite graphs with s=5,6s=5,6s=5,6

Photon-efficient quantum cryptography with pulse-position modulation

A refined analysis of the Poisson channel in the high-photon-efficiency regime

Toward Photon-Efficient Key Distribution over Optical Channels

One-Shot Classical-Quantum Capacity and Hypothesis Testing

Private-Capacity Bounds for Bosonic Wiretap Channels

The State-Dependent Semideterministic Broadcast Channel

It takes half the energy of a photon to send one bit reliably on the Poisson channel with feedback

Simple Channel Coding Bounds

Low SNR Capacity of Noncoherent Fading Channels

See the researcher in context

Building this map preview

On the $α$ -index of minimally 2-connected graphs with given order or size

On the signless Laplacian spectral radius of $C_{4}$ -free $k$ -cyclic graphs

Upper bounds on the Q-spectral radius of book-free and/or $K_{s,t}$ -free graphs

Distance integral complete multipartite graphs with $s=5,6$