Source author record

Jephian C. -H. Lin

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

ResearcherUnclaimed source record

math.CO quant-ph

Catalog footprint

Research overview

8works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Complementary Vanishing Graphs

Given a graph $G$ with vertices $\{v_1,\ldots,v_n\}$ , we define $\mathcal{S}(G)$ to be the set of symmetric matrices $A=[a_{i,j}]$ such that for $i\ne j$ we have $a_{i,j}\ne 0$ if and only if $v_iv_j\in E(G)$ . Motivated by the Graph Complement Conjecture, we say that a graph $G$ is complementary vanishing if there exist matrices $A \in \mathcal{S}(G)$ and $B \in \mathcal{S}(\overline{G})$ such that $AB=O$ . We provide combinatorial conditions for when a graph is or is not complementary vanishing, and we characterize which graphs are complementary vanishing in terms of certain minimal complementary vanishing graphs. In addition to this, we determine which graphs on at most $8$ vertices are complementary vanishing.

preprint2022arXiv

The bifurcation lemma for strong properties in the inverse eigenvalue problem of a graph

The inverse eigenvalue problem of a graph studies the real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of the graph. The strong spectral property (SSP) is an important tool for this problem. This note establishes the bifurcation lemma, which states that if a spectrum can be realized by a matrix with the SSP for some graph, then all the nearby spectra can also be realized by matrices with the SSP for the same graph. The idea of the bifurcation lemma also works for other strong properties and for not necessarily symmetric matrices. This is used to develop new techniques for verifying a spectrally arbitrary pattern or inertially arbitrary pattern. The bifurcation lemma provides a unified theoretical foundation for several known results, such as the stable northeast lemma and the nilpotent-centralizer method.

preprint2020arXiv

Complex Hadamard Diagonalisable Graphs

In light of recent interest in Hadamard diagonalisable graphs (graphs whose Laplacian matrix is diagonalisable by a Hadamard matrix), we generalise this notion from real to complex Hadamard matrices. We give some basic properties and methods of constructing such graphs. We show that a large class of complex Hadamard diagonalisable graphs have vertex sets forming an equitable partition, and that the Laplacian eigenvalues must be even integers. We provide a number of examples and constructions of complex Hadamard diagonalisable graphs, including two special classes of graphs: the Cayley graphs over $\mathbb{Z}_r^d$ , and the non--complete extended $p$ --sum (NEPS). We discuss necessary and sufficient conditions for $(α, β)$ --Laplacian fractional revival and perfect state transfer on continuous--time quantum walks described by complex Hadamard diagonalisable graphs and provide examples of such quantum state transfer.

preprint2016arXiv

Generalizations of the Strong Arnold Property and the minimum number of distinct eigenvalues of a graph

For a given graph G and an associated class of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in G, the collection of all possible spectra for such matrices is considered. Building on the pioneering work of Colin de Verdiere in connection with the Strong Arnold Property, two extensions are devised that target a better understanding of all possible spectra and their associated multiplicities. These new properties are referred to as the Strong Spectral Property and the Strong Multiplicity Property. Finally, these ideas are applied to the minimum number of distinct eigenvalues associated with G, denoted by q(G). The graphs for which q(G) is at least the number of vertices of G less one are characterized.

preprint2016arXiv

Multi-part Nordhaus-Gaddum type problems for tree-width, Colin de Verdière type parameters, and Hadwiger number

A traditional Nordhaus-Gaddum problem for a graph parameter $β$ is to find a (tight) upper or lower bound on the sum or product of $β(G)$ and $β(\bar{G})$ (where $\bar{G}$ denotes the complement of $G$ ). An $r$ -decomposition $G_1,\dots,G_r$ of the complete graph $K_n$ is a partition of the edges of $K_n$ among $r$ spanning subgraphs $G_1,\dots,G_r$ . A traditional Nordhaus-Gaddum problem can be viewed as the special case for $r=2$ of a more general $r$ -part sum or product Nordhaus-Gaddum type problem. We determine the values of the $r$ -part sum and product upper bounds asymptotically as $n$ goes to infinity for the parameters tree-width and its variants largeur d'arborescence, path-width, and proper path-width. We also establish ranges for the lower bounds for these parameters, and ranges for the upper and lower bounds of the $r$ -part Nordhaus-Gaddum type problems for the parameters Hadwiger number, the Colin de Verdière number $μ$ that is used to characterize planarity, and its variants $ν$ and $ξ$ .

preprint2016arXiv

Note on von Neumann and Rényi entropies of a Graph

We conjecture that all connected graphs of order $n$ have von Neumann entropy at least as great as the star $K_{1,n-1}$ and prove this for almost all graphs of order $n$ . We show that connected graphs of order $n$ have Rényi 2-entropy at least as great as $K_{1,n-1}$ and for $α>1$ , $K_n$ maximizes Rényi $α$ -entropy over graphs of order $n$ . We show that adding an edge to a graph can lower its von Neumann entropy.

preprint2016arXiv

Using a new zero forcing process to guarantee the Strong Arnold Property

The maximum nullity $M(G)$ and the Colin de Verdière type parameter $ξ(G)$ both consider the largest possible nullity over matrices in $\mathcal{S}(G)$ , which is the family of real symmetric matrices whose $i,j$ -entry, $i\neq j$ , is nonzero if $i$ is adjacent to $j$ , and zero otherwise; however, $ξ(G)$ restricts to those matrices $A$ in $\mathcal{S}(G)$ with the Strong Arnold Property, which means $X=O$ is the only symmetric matrix that satisfies $A\circ X=O$ , $I\circ X=O$ , and $AX=O$ . This paper introduces zero forcing parameters $Z_{\mathrm{SAP}}(G)$ and $Z_{\mathrm{vc}}(G)$ , and proves that $Z_{\mathrm{SAP}}(G)=0$ implies every matrix $A\in \mathcal{S}(G)$ has the Strong Arnold Property and that the inequality $M(G)-Z_{\mathrm{vc}}(G)\leq ξ(G)$ holds for every graph $G$ . Finally, the values of $ξ(G)$ are computed for all graphs up to $7$ vertices, establishing $ξ(G)=\lfloor Z\rfloor(G)$ for these graphs.

preprint2015arXiv

On the distance spectra of graphs

The distance matrix of a graph $G$ is the matrix containing the pairwise distances between vertices. The distance eigenvalues of $G$ are the eigenvalues of its distance matrix and they form the distance spectrum of $G$ . We determine the distance spectra of halved cubes, double odd graphs, and Doob graphs, completing the determination of distance spectra of distance regular graphs having exactly one positive distance eigenvalue. We characterize strongly regular graphs having more positive than negative distance eigenvalues. We give examples of graphs with few distinct distance eigenvalues but lacking regularity properties. We also determine the determinant and inertia of the distance matrices of lollipop and barbell graphs.

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.

Jephian C. -H. Lin

Research overview

Is this your work?

8 publications

Complementary Vanishing Graphs

The bifurcation lemma for strong properties in the inverse eigenvalue problem of a graph

Complex Hadamard Diagonalisable Graphs

Generalizations of the Strong Arnold Property and the minimum number of distinct eigenvalues of a graph

Multi-part Nordhaus-Gaddum type problems for tree-width, Colin de Verdière type parameters, and Hadwiger number

Note on von Neumann and Rényi entropies of a Graph

Using a new zero forcing process to guarantee the Strong Arnold Property

On the distance spectra of graphs

See the researcher in context

Building this map preview