Source author record

Zhen-Mu Hong

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Connectivity and eigenvalues of graphs with given girth or clique number

Let $κ'(G)$ , $κ(G)$ , $μ_{n-1}(G)$ and $μ_1(G)$ denote the edge-connectivity, vertex-connectivity, the algebraic connectivity and the Laplacian spectral radius of $G$ , respectively. In this paper, we prove that for integers $k\geq 2$ and $r\geq 2$ , and any simple graph $G$ of order $n$ with minimum degree $δ\geq k$ , girth $g\geq 3$ and clique number $ω(G)\leq r$ , the edge-connectivity $κ'(G)\geq k$ if $μ_{n-1}(G) \geq \frac{(k-1)n}{N(δ,g)(n-N(δ,g))}$ or if $μ_{n-1}(G) \geq \frac{(k-1)n}{φ(δ,r)(n-φ(δ,r))}$ , where $N(δ,g)$ is the Moore bound on the smallest possible number of vertices such that there exists a $δ$ -regular simple graph with girth $g$ , and $φ(δ,r) = \max\{δ+1,\lfloor\frac{rδ}{r-1}\rfloor\}$ . Analogue results involving $μ_{n-1}(G)$ and $\frac{μ_1(G)}{μ_{n-1}(G)}$ to characterize vertex-connectivity of graphs with fixed girth and clique number are also presented. Former results in [Linear Algebra Appl. 439 (2013) 3777--3784], [Linear Algebra Appl. 578 (2019) 411--424], [Linear Algebra Appl. 579 (2019) 72--88], [Appl. Math. Comput. 344-345 (2019) 141--149] and [Electronic J. Linear Algebra 34 (2018) 428--443] are improved or extended.

preprint2020arXiv

Induced subgraphs of product graphs and a generalization of Huang's theorem

Recently, Huang showed that every $(2^{n-1}+1)$ -vertex induced subgraph of the $n$ -dimensional hypercube has maximum degree at least $\sqrt{n}$ in [Annals of Mathematics, 190 (2019), 949--955]. In this paper, we discuss the induced subgraphs of Cartesian product graphs and semi-strong product graphs to generalize Huang's result. Let $Γ_1$ be a connected signed bipartite graph of order $n$ and $Γ_2$ be a connected signed graph of order $m$ . By defining two kinds of signed product of $Γ_1$ and $Γ_2$ , denoted by $Γ_1\widetilde{\Box}Γ_2$ and $Γ_1\widetilde{\bowtie} Γ_2$ , we show that if $Γ_1$ and $Γ_2$ have exactly two distinct adjacency eigenvalues $\pmθ_1$ and $\pmθ_2$ respectively, then every $(\frac{1}{2}mn+1)$ -vertex induced subgraph of $Γ_1\widetilde{\Box}Γ_2$ (resp. $Γ_1\widetilde{\bowtie} Γ_2$ ) has maximum degree at least $\sqrt{θ_1^2+θ_2^2}$ (resp. $\sqrt{(θ_1^2+1)θ_2^2}$ ). Moreover, we discuss the eigenvalues of $Γ_1\widetilde{\Box} Γ_2$ and $Γ_1\widetilde{\bowtie} Γ_2$ and obtain a sufficient and necessary condition such that the spectrum of $Γ_1\widetilde{\Box}Γ_2$ and $Γ_1\widetilde{\bowtie}Γ_2$ are symmetric, from which we obtain more general results on maximum degree of the induced subgraphs.

preprint2016arXiv

On restricted edge-connectivity of replacement product graphs

This paper considers the edge-connectivity and restricted edge-connectivity of replacement product graphs, gives some bounds on edge-connectivity and restricted edge-connectivity of replacement product graphs and determines the exact values for some special graphs. In particular, the authors further confirm that under certain conditions, the replacement product of two Cayley graphs is also a Cayley graph, and give a necessary and sufficient condition for such Cayley graphs to have maximum restricted edge-connectivity. Based on these results, the authors construct a Cayley graph with degree $d$ whose restricted edge-connectivity is equal to $d+s$ for given odd integer $d$ and integer $s$ with $d \geqslant 5$ and $1\leqslant s\leqslant d-3$ , which answers a problem proposed ten years ago.

preprint2013arXiv

Vulnerability of super edge-connected graphs

A subset $F$ of edges in a connected graph $G$ is a $h$ -extra edge-cut if $G-F$ is disconnected and every component has more than $h$ vertices. The $h$ -extra edge-connectivity $\la^{(h)}(G)$ of $G$ is defined as the minimum cardinality over all $h$ -extra edge-cuts of $G$ . A graph $G$ , if $\la^{(h)}(G)$ exists, is super-$\la^{(h)}$ if every minimum $h$ -extra edge-cut of $G$ isolates at least one connected subgraph of order $h+1$ . The persistence $ρ^{(h)}(G)$ of a super-$\la^{(h)}$ graph $G$ is the maximum integer $m$ for which $G-F$ is still super-$\la^{(h)}$ for any set $F\subseteq E(G)$ with $|F|\leqslant m$ . Hong {\it et al.} [Discrete Appl. Math. 160 (2012), 579-587] showed that $\min\{\la^{(1)}(G)-δ(G)-1,δ(G)-1\}\leqslant ρ^{(0)}(G)\leqslant δ(G)-1$, where $δ(G)$ is the minimum vertex-degree of $G$ . This paper shows that $\min\{\la^{(2)}(G)-ξ(G)-1,δ(G)-1\}\leqslant ρ^{(1)}(G)\leqslant δ(G)-1$, where $ξ(G)$ is the minimum edge-degree of $G$ . In particular, for a $k$ -regular super-$\la'$ graph $G$ , $ρ^{(1)}(G)=k-1$ if $\la^{(2)}(G)$ does not exist or $G$ is super-$\la^{(2)}$ and triangle-free, from which the exact values of $ρ^{(1)}(G)$ are determined for some well-known networks.

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.