Source author record

Shenggui Zhang

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

19works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Anti-Ramsey numbers for vertex-disjoint triangles

An edge-colored graph is called rainbow if all the colors on its edges are distinct. Given a positive integer n and a graph G, the anti-Ramsey number ar(n,G) is the maximum number of colors in an edge-coloring of K_{n} with no rainbow copy of G. Denote by kC_{3} the union of k vertex-disjoint copies of C_{3}. In this paper, we determine the anti-Ramsey number ar(n,kC_{3}) for n=3k and n\geq2k^{2}-k+2, respectively. When 3k\leq n\leq 2k^{2}-k+2, we give lower and upper bounds for ar(n, kC_{3}).

preprint2020arXiv

Rainbow triangles in arc-colored tournaments

Let $T_{n}$ be an arc-colored tournament of order $n$ . The maximum monochromatic indegree $Δ^{-mon}(T_{n})$ (resp. outdegree $Δ^{+mon}(T_{n})$ ) of $T_{n}$ is the maximum number of in-arcs (resp. out-arcs) of a same color incident to a vertex of $T_{n}$ . The irregularity $i(T_{n})$ of $T_{n}$ is the maximum difference between the indegree and outdegree of a vertex of $T_{n}$ . A subdigraph $H$ of an arc-colored digraph $D$ is called rainbow if each pair of arcs in $H$ have distinct colors. In this paper, we show that each vertex $v$ in an arc-colored tournament $T_{n}$ with $Δ^{-mon}(T_n)\leqΔ^{+mon}(T_n)$ is contained in at least $\frac{δ(v)(n-δ(v)-i(T_n))}{2}-[Δ^{-mon}(T_{n})(n-1)+Δ^{+mon}(T_{n})d^+(v)]$ rainbow triangles, where $δ(v)=\min\{d^+(v), d^-(v)\}$ . We also give some maximum monochromatic degree conditions for $T_{n}$ to contain rainbow triangles, and to contain rainbow triangles passing through a given vertex. Finally, we present some examples showing that some of the conditions in our results are best possible. Keywords: arc-colored tournament, rainbow triangle, maximum monochromatic indegree (outdegree), irregularity

preprint2016arXiv

Cyclability of $id$ -cycles in graphs

Let $G$ be a graph on $n$ vertices and $C'=v_0v_1\cdots v_{p-1}v_0$ a vertex sequence of $G$ with $p\geq 3$ ( $v_i\neq v_j$ for all $i,j=0,1,\ldots,p-1$ , $i\neq j$ ). If for any successive vertices $v_i$ , $v_{i+1}$ on $C'$ , either $v_iv_{i+1}\in E(G)$ or both of the first implicit-degrees of $v_i$ and $v_{i+1}$ are at least $n/2$ (indices are taken modulo $p$ ), then $C'$ is called an $id$ -cycle of $G$ . In this paper, we prove that for every $id$ -cycle $C'$ , there exists a cycle $C$ in $G$ with $V(C')\subseteq V(C)$ . This generalizes several early results on the Hamiltonicity and cyclability of graphs.

preprint2016arXiv

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called \emph{claw-free} if it contains no induced subgraph isomorphic to $K_{1,3}$ . Matthews and Sumner proved that a 2-connected claw-free graph $G$ is hamiltonian if every vertex of it has degree at least $(|V(G)|-2)/3$ . At the workshop C\&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of $N$ (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of $Z_1$ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs $H$ such that a 2-connected claw-free graph $G$ is hamiltonian if each end-vertex of every induced copy of $H$ in $G$ has degree at least $|V(G)|/3+1$ . This gives an affirmative solution of the conjecture of Broersma up to an additive constant.

preprint2015arXiv

Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions

A graph $G$ is called \emph{claw-o-heavy} if every induced claw ( $K_{1,3}$ ) of $G$ has two end-vertices with degree sum at least $|V(G)|$ in $G$ . For a given graph $R$ , $G$ is called \emph{ $R$ -f-heavy} if for every induced subgraph $H$ of $G$ isomorphic to $R$ and every pair of vertices $u,v\in V(H)$ with $d_H(u,v)=2$ , there holds $\max\{d(u),d(v)\}\geq |V(G)|/2$ . In this paper, we prove that every 2-connected claw-\emph{o}-heavy and $Z_3$ -\emph{f}-heavy graph is hamiltonian (with two exceptional graphs), where $Z_3$ is the graph obtained from identifying one end-vertex of $P_4$ (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed in [B. Ning, S. Zhang, Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs, Discrete Math. 313 (2013) 1715--1725], and also implies two previous theorems of Faudree et al. and Chen et al., respectively.

preprint2014arXiv

Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

Let claw be the graph $K_{1,3}$ . A graph $G$ on $n\geq 3$ vertices is called \emph{o}-heavy if each induced claw of $G$ has a pair of end-vertices with degree sum at least $n$ , and 1-heavy if at least one end-vertex of each induced claw of $G$ has degree at least $n/2$ . In this note, we show that every 2-connected $o$ -heavy or 3-connected 1-heavy graph is Hamiltonian if we restrict Fan-type degree condition or neighborhood intersection condition to certain pairs of vertices in some small induced subgraphs of the graph. Our results improve or extend previous results of Broersma et al., Chen et al., Fan, Goodman & Hedetniemi, Gould & Jacobson, and Shi on the existence of Hamilton cycles in graphs.

preprint2013arXiv

On traceability of claw-o_{-1}-heavy graphs

A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all its vertices. Let $G$ be a graph on $n$ vertices. $G$ is called claw- $o_{-1}$ -heavy if every induced claw ( $K_{1,3}$ ) of $G$ has a pair of nonadjacent vertices with degree sum at least $n-1$ in $G$ . In this paper we show that a claw- $o_{-1}$ -heavy graph $G$ is traceable if we impose certain additional conditions on $G$ involving forbidden induced subgraphs.

preprint2013arXiv

Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs

Bedrossian characterized all pairs of forbidden subgraphs for a 2-connected graph to be Hamiltonian. Instead of forbidding some induced subgraphs, we relax the conditions for graphs to be Hamiltonian by restricting Ore- and Fan-type degree conditions on these induced subgraphs. Let $G$ be a graph on $n$ vertices and $H$ be an induced subgraph of $G$ . $H$ is called \emph{o}-heavy if there are two nonadjacent vertices in $H$ with degree sum at least $n$ , and is called $f$ -heavy if for every two vertices $u,v\in V(H)$ , $d_{H}(u,v)=2$ implies that $\max\{d(u),d(v)\}\geq n/2$ . We say that $G$ is $H$ -\emph{o}-heavy ( $H$ -\emph{f}-heavy) if every induced subgraph of $G$ isomorphic to $H$ is \emph{o}-heavy (\emph{f}-heavy). In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ such that every 2-connected $R$ -\emph{f}-heavy and $S$ -\emph{f}-heavy ( $R$ -\emph{o}-heavy and $S$ -\emph{f}-heavy, $R$ -\emph{f}-heavy and $S$ -free) graph is Hamiltonian. Our results extend several previous theorems on forbidden subgraph conditions and heavy subgraph conditions for Hamiltonicity of 2-connected graphs.

preprint2013arXiv

Rainbow triangles in edge-colored graphs

Let $G$ be an edge-colored graph. The color degree of a vertex $v$ of $G$ , is defined as the number of colors of the edges incident to $v$ . The color number of $G$ is defined as the number of colors of the edges in $G$ . A rainbow triangle is one in which every pair of edges have distinct colors. In this paper we give some sufficient conditions for the existence of rainbow triangles in edge-colored graphs in terms of color degree, color number and edge number. As a corollary, a conjecture proposed by Li and Wang (Color degree and heterochromatic cycles in edge-colored graphs, European J. Combin. 33 (2012) 1958--1964) is confirmed.

preprint2013arXiv

Two sufficient conditions for the existence of Hamilton cycles in graphs

Let $G$ be a graph on $n\geq 3$ vertices, claw the bipartite graph $K_{1,3}$ , and $Z_i$ the graph obtained from a triangle by attaching a path of length $i$ to its one vertex. $G$ is called 1-heavy if at least one end vertex of each induced claw of $G$ has degree at least $n/2$ , and claw-\emph{o}-heavy if each induced claw of it has a pair of end vertices with degree sum at least $n$ . In this paper we prove two results: (1) Every 2-connected claw- $o$ -heavy graph $G$ is Hamiltonian if every pair of vertices $u,v$ in a subgraph $H\cong Z_1$ contained in an induced subgraph $Z_2$ of $G$ with $d_{H}(u,v)=2$ satisfies one of the following conditions: ( $a$ ) $|N(u)\cap N(v)|\geq 2$ ; ( $b$ ) $\max(d(u),d(v))\geq n/2$ . (2) Every 3-connected 1-heavy graph $G$ is Hamiltonian if every pair of vertices $u,v$ in an induced subgraph $H\cong Z_2$ of $G$ with $d_{H}(u,v)=2$ satisfies one of the following conditions: ( $a$ ) $|N(u)\cap N(v)|\geq 2$ ; ( $b$ ) $\max(d(u),d(v))\geq n/2$ . Our results improve or extend previous theorems of Broersma et al., Chen et al., Fan, Goodman & Hedetniemi, Gould & Jacobson and Shi on the existence of Hamilton cycles in graphs.

preprint2012arXiv

A note on heavy cycles in weighted digraphs

A weighted digraph is a digraph such that every arc is assigned a nonnegative number, called the weight of the arc. The weighted outdegree of a vertex $v$ in a weighted digraph $D$ is the sum of the weights of the arcs with $v$ as their tail, and the weight of a directed cycle $C$ in $D$ is the sum of the weights of the arcs of $C$ . In this note we prove that if every vertex of a weighted digraph $D$ with order $n$ has weighted outdegree at least 1, then there exists a directed cycle in $D$ with weight at least $1/\log_2 n$ . This proves a conjecture of Bollobás and Scott up to a constant factor.

preprint2012arXiv

A note on heterochromatic cycles of length 4 in edge-colored graphs

Let $G$ be an edge-colored graph. A heterochromatic cycle of $G$ is one in which every two edges have different colors. For a vertex $v\in V(G)$ , let $CN(v)$ denote the set of colors which are assigned to the edges incident to $v$ . In this note we prove that $G$ contains a heterochromatic cycle of length 4 if $G$ has $n\geq 60$ vertices and $|CN(u)\cup CN(v)|\geq n-1$ for every pair of vertices $u$ and $v$ of $G$ . This extends a result of Broersma et al. on the existence of heterochromatic cycles of length 3 or 4.

preprint2012arXiv

Covering the edges of digraphs in $\mathscr{D}(3,3)$ and $\mathscr{D}(4,4)$ with directed cuts

For nonnegative integers $k$ and $l$ , let $\mathscr{D}(k,l)$ denote the family of digraphs in which every vertex has either indegree at most $k$ or outdegree at most $l$ . In this paper we prove that the edges of every digraph in $\mathscr{D}(3,3)$ and $\mathscr{D}(4,4)$ can be covered by at most five directed cuts and present an example in $\mathscr{D}(3,3)$ showing that this result is best possible.

preprint2012arXiv

Star subdivisions and connected even factors in the square of a graph

For any positive integer $s$ , a $[2,2s]$ -factor in a graph $G$ is a connected even factor with maximum degree at most $2s$ . We prove that if every induced $S(K_{1, 2s+1})$ in a graph $G$ has at least 3 edges in a block of degree at most two, then $G^2$ has a $[2,2s]$ -factor. This extends the results of Hendry and Vogler and of Abderrezzak et al.

preprint2011arXiv

Bipartite graphs with the maximum sum of squares of degrees

In this paper we determine all the bipartite graphs with the maximum sum of squares of degrees among the ones with a given number of vertices and edges.

preprint2011arXiv

Extreme tenacity of graphs with given order and size

Computer or communication networks are so designed that they do not easily get disrupted under external attack and, moreover, these are easily reconstructible if they do get disrupted. These desirable properties of networks can be measured by various graph parameters, such as connectivity, toughness, scattering number, integrity, tenacity, rupture degree and edge-analogues of some of them. Among these parameters, the tenacity and rupture degree are two better ones to measure the stability of a network. In this paper we consider two extremal problems on the tenacity of graphs: Determine the minimum and maximum tenacity of graphs with given order and size. We give a complete solution to the first problem, while for the second one, it turns out that the problem is much more complicated than that of the minimum case. We determine the maximum tenacity of trees and unicyclic graphs with given order and show the corresponding extremal graphs. These results are helpful in constructing stable networks with lower costs. The paper concludes with a discussion of a related problem on the edge vulnerability parameters of graphs.

preprint2011arXiv

Heavy subgraph conditions for longest cycles to be heavy in graphs

Let $G$ be a graph on $n$ vertices. A vertex of $G$ with degree at least $n/2$ is called a heavy vertex, and a cycle of $G$ which contains all the heavy vertices of $G$ is called a heavy cycle. In this paper, we characterize the graphs which contain no heavy cycles. For a given graph $H$ , we say that $G$ is $H$ -\emph{heavy} if every induced subgraph of $G$ isomorphic to $H$ contains two nonadjacent vertices with degree sum at least $n$ . We find all the connected graphs $S$ such that a 2-connected graph $G$ being $S$ -heavy implies any longest cycle of $G$ is a heavy cycle.

preprint2011arXiv

On heavy paths in 2-connected weighted graphs

A weighted graph is a graph in which every edge is assigned a non-negative real number. In a weighted graph, the weight of a path is the sum of the weights of its edges, and the weighed degree of a vertex is the sum of the weights of the edges incident with it. In this paper we give three weighted degree conditions for the existence of heavy or Hamilton paths with one or two given end-vertices in 2-connected weighted graphs.

preprint2011arXiv

Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs

Let $G$ be a graph on $n$ vertices. An induced subgraph $H$ of $G$ is called heavy if there exist two nonadjacent vertices in $H$ with degree sum at least $n$ in $G$ . We say that $G$ is $H$ -heavy if every induced subgraph of $G$ isomorphic to $H$ is heavy. For a family $\mathcal{H}$ of graphs, $G$ is called $\mathcal{H}$ -heavy if $G$ is $H$ -heavy for every $H\in\mathcal{H}$ . In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ (the path on three vertices) such that every 2-connected $\{R,S\}$ -heavy graph is Hamiltonian. This extends several previous results on forbidden subgraph conditions for Hamiltonian 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.

Shenggui Zhang

Research overview

Is this your work?

19 publications

Anti-Ramsey numbers for vertex-disjoint triangles

Rainbow triangles in arc-colored tournaments

Cyclability of $id$ -cycles in graphs

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions

Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

On traceability of claw-o_{-1}-heavy graphs

Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs

Rainbow triangles in edge-colored graphs

Two sufficient conditions for the existence of Hamilton cycles in graphs

A note on heavy cycles in weighted digraphs

A note on heterochromatic cycles of length 4 in edge-colored graphs

Covering the edges of digraphs in $\mathscr{D}(3,3)$ and $\mathscr{D}(4,4)$ with directed cuts

Star subdivisions and connected even factors in the square of a graph

Bipartite graphs with the maximum sum of squares of degrees

Extreme tenacity of graphs with given order and size

Heavy subgraph conditions for longest cycles to be heavy in graphs

On heavy paths in 2-connected weighted graphs

Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs

See the researcher in context

Building this map preview

Shenggui Zhang

Research overview

Is this your work?

19 publications

Anti-Ramsey numbers for vertex-disjoint triangles

Rainbow triangles in arc-colored tournaments

Cyclability of ididid-cycles in graphs

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions

Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

On traceability of claw-o_{-1}-heavy graphs

Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs

Rainbow triangles in edge-colored graphs

Two sufficient conditions for the existence of Hamilton cycles in graphs

A note on heavy cycles in weighted digraphs

A note on heterochromatic cycles of length 4 in edge-colored graphs

Covering the edges of digraphs in D(3,3)\mathscr{D}(3,3)D(3,3) and D(4,4)\mathscr{D}(4,4)D(4,4) with directed cuts

Star subdivisions and connected even factors in the square of a graph

Bipartite graphs with the maximum sum of squares of degrees

Extreme tenacity of graphs with given order and size

Heavy subgraph conditions for longest cycles to be heavy in graphs

On heavy paths in 2-connected weighted graphs

Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs

See the researcher in context

Building this map preview

Cyclability of $id$ -cycles in graphs

Covering the edges of digraphs in $\mathscr{D}(3,3)$ and $\mathscr{D}(4,4)$ with directed cuts