Source author record

Zhidan Yan

Zhidan Yan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.GR

Catalog footprint

What is connected

7works

3topics

2close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Disproof of a conjecture on the main spectrum of generalized Bethe trees

An eigenvalue of the adjacency matrix of a graph is said to be main if the all-ones vector is not orthogonal to its associated eigenspace. A generalized Bethe tree with $k$ levels is a rooted tree in which vertices at the same level have the same degree. França and Brondani [On the main spectrum of generalized Bethe trees, Linear Algebra Appl., 628 (2021) 56-71] recently conjectured that any generalized Bethe tree with $k$ levels has exactly $k$ main eigenvalues whenever $k$ is even. We disprove the conjecture by constructing a family of counterexamples for even integers $k\ge 6$.

preprint2013arXiv

Equitable chromatic threshold of Kronecker products of complete graphs

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. The equitable chromatic threshold of a graph $G$, denoted by $χ_=^*(G)$, is the minimum $k$ such that $G$ is equitably $k^\prime$-colorable for all $k^\prime \ge k$. Let $G\times H$ denote the direct product of graphs $G$ and $H$. For $n\ge m\ge 2$ we prove that $χ_=^*(K_{m} \times K_n)$ equals $\lceil\frac{mn}{m+1}\rceil$ if $n\equiv 2,...,m (\textup{mod} m+1)$, and equals $m\lceil\frac{n}{s^\star}\rceil$ if $n\equiv 0,1 (\textup{mod} m+1)$, where $s^\star$ is the minimum positive integer such that $s^\star \nmid n$ and $s^\star\ge m+2.$

preprint2013arXiv

On r-equitable chromatic threshold of Kronecker products of complete graphs

A graph $G$ is $r$-equitably $k$-colorable if its vertex set can be partitioned into $k$ independent sets, any two of which differ in size by at most $r$. The $r$-equitable chromatic threshold of a graph $G$, denoted by $χ_{r=}^*(G)$, is the minimum $k$ such that $G$ is $r$-equitably $k'$-colorable for all $k'\ge k$. Let $G\times H$ denote the Kronecker product of graphs $G$ and $H$. In this paper, we completely determine the exact value of $χ_{r=}^*(K_m\times K_n)$ for general $m,n$ and $r$. As a consequence, we show that for $r\ge 2$, if $n\ge \frac{1}{r-1}(m+r)(m+2r-1)$ then $K_m\times K_n$ and its spanning supergraph $K_{m(n)}$ have the same $r$-equitable colorability, and in particular $χ_{r=}^*(K_m\times K_n)=χ_{r=}^*(K_{m(n)})$, where $K_{m(n)}$ is the complete $m$-partite graph with $n$ vertices in each part.

preprint2012arXiv

Equitable chromatic threshold of complete multipartite graphs

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The equitable chromatic number of a graph $G$, denoted by $χ_=(G)$, is the minimum $k$ such that $G$ is equitably $k$-colorable. The equitable chromatic threshold of a graph $G$, denoted by $χ_=^*(G)$, is the minimum $t$ such that $G$ is equitably $k$-colorable for $k\ge t$. We develop a formula and a linear-time algorithm which compute the equitable chromatic threshold of an arbitrary complete multipartite graph.

preprint2012arXiv

Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. The equitable chromatic number of a graph $G$, denoted by $χ_=(G)$, is the minimum $k$ such that $G$ is equitably $k$-colorable. The equitable chromatic threshold of a graph $G$, denoted by $χ_=^*(G)$, is the minimum $t$ such that $G$ is equitably $k$-colorable for $k \ge t$. In this paper, we give the exact values of $χ_=(K_{m_1,..., m_r} \times K_n)$ and $χ_=^*(K_{m_1,..., m_r} \times K_n)$ for $\sum_{i = 1}^r m_i \leq n$.

preprint2011arXiv

Connectivity of Kronecker products by K2

Let $κ(G)$ be the connectivity of $G$. The Kronecker product $G_1\times G_2$ of graphs $G_1$ and $G_2$ has vertex set $V(G_1\times G_2)=V(G_1)\times V(G_2)$ and edge set $E(G_1\times G_2)=\{(u_1,v_1)(u_2,v_2):u_1u_2\in E(G_1),v_1v_2\in E(G_2)\}$. In this paper, we prove that $κ(G\times K_2)=\textup{min}\{2κ(G), \textup{min}\{|X|+2|Y|\}\}$, where the second minimum is taken over all disjoint sets $X,Y\subseteq V(G)$ satisfying (1)$G-(X\cup Y)$ has a bipartite component $C$, and (2) $G[V(C)\cup \{x\}]$ is also bipartite for each $x\in X$.