Source author record

Zixing Tang

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

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

More bounds for the Grundy number of graphs

A coloring of a graph $G=(V,E)$ is a partition $\{V_1, V_2, \ldots, V_k\}$ of $V$ into independent sets or color classes. A vertex $v\in V_i$ is a Grundy vertex if it is adjacent to at least one vertex in each color class $V_j$ for every $j<i$ . A coloring is a Grundy coloring if every vertex is a Grundy vertex, and the Grundy number $Γ(G)$ of a graph $G$ is the maximum number of colors in a Grundy coloring. We provide two new upper bounds on Grundy number of a graph and a stronger version of the well-known Nordhaus-Gaddum theorem. In addition, we give a new characterization for a $\{P_{4}, C_4\}$ -free graph by supporting a conjecture of Zaker, which says that $Γ(G)\geq δ(G)+1$ for any $C_4$ -free graph $G$ .

preprint2015arXiv

Proof of a conjecture on the zero forcing number of a graph

Amos et al. (Discrete Appl. Math. 181 (2015) 1-10) introduced the notion of the $k$ -forcing number of graph for a positive integer $k$ as the generalization of the zero forcing number of a graph. The $k$ -forcing number of a simple graph $G$ , denoted by $F_k(G)$ , is the minimum number of vertices that need to be initially colored so that all vertices eventually become colored during the discrete dynamical process by the following rule. Starting from an initial set of colored vertices and stopping when all vertices are colored: if a colored vertex has at most $k$ non-colored neighbors, then each of its non-colored neighbors become colored. Particulary, $F_1(G)$ is a widely studied invariant with close connection to the maximum nullity of a graph, under the name of the zero forcing number, denoted by $Z(G)$ . Among other things, the authors proved that for a connected graph $G$ of order $n$ with $Δ=Δ(G)\geq 2$ , $Z(G)\leq \frac{(Δ-2)n+2}{Δ-1}$ , and this inequality is sharp. Moreover, they conjectured that $Z(G)=\frac{(Δ-2)n+2}{Δ-1}$ if and only if $G=C_n$ , $G=K_{Δ+1}$ or $G=K_{Δ, Δ}$ . In this note, we show the above conjecture is true.

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.