Source author record

Jian-Liang Wu

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO physics.soc-ph Social and Information Networks

Catalog footprint

Research overview

9works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Toward Structural Controllability and Predictability in Directed Networks

The lack of studying the complex organization of directed network usually limits to the understanding of underlying relationship between network structures and functions. Structural controllability and structural predictability, two seemingly unrelated subjects, are revealed in this paper to be both highly dependent on the critical links previously thought to only be able to influence the number of driver nodes in controllable directed networks. Here, we show that critical links can not only contribute to structural controllability, but they can also have a significant impact on the structural predictability of networks, suggesting the universal pattern of structural reciprocity in directed networks. In addition, it is shown that the fraction and location of critical links have a strong influence on the performance of prediction algorithms. Moreover, these empirical results are interpreted by introducing the link centrality based on corresponding line graphs. This work bridges the gap between the two independent research fields, and it provides indications of developing advanced control strategies and prediction algorithms from a microscopic perspective.

preprint2012arXiv

A conjecture on equitable vertex arboricity of graphs

Wu, Zhang and Li [4] conjectured that the set of vertices of any simple graph $G$ can be equitably partitioned into $\lceil(Δ(G)+1)/2\rceil$ subsets so that each of them induces a forest of $G$ . In this note, we prove this conjecture for graphs $G$ with $Δ(G)\geq |G|/2$ .

preprint2012arXiv

Equitable vertex arboricity of graphs

An equitable $(t,k,d)$ -tree-coloring of a graph $G$ is a coloring to vertices of $G$ such that the sizes of any two color classes differ by at most one and the subgraph induced by each color class is a forest of maximum degree at most $k$ and diameter at most $d$ . The minimum $t$ such that $G$ has an equitable $(t',k,d)$ -tree-coloring for every $t'\geq t$ is called the strong equitable $(k,d)$ -vertex-arboricity and denoted by $va^{\equiv}_{k,d}(G)$ . In this paper, we give sharp upper bounds for $va^{\equiv}_{1,1}(K_{n,n})$ and $va^{\equiv}_{k,\infty}(K_{n,n})$ by showing that $va^{\equiv}_{1,1}(K_{n,n})=O(n)$ and $va^{\equiv}_{k,\infty}(K_{n,n})=O(n^{\1/2})$ for every $k\geq 2$ . It is also proved that $va^{\equiv}_{\infty,\infty}(G)\leq 3$ for every planar graph $G$ with girth at least 5 and $va^{\equiv}_{\infty,\infty}(G)\leq 2$ for every planar graph $G$ with girth at least 6 and for every outerplanar graph. We conjecture that $va^{\equiv}_{\infty,\infty}(G)=O(1)$ for every planar graph and $va^{\equiv}_{\infty,\infty}(G)\leq \lceil\frac{Δ(G)+1}{2}\rceil$ for every graph $G$ .

preprint2011arXiv

(1,λ)-embedded graphs and the acyclic edge choosability

A (1,λ)-embedded graph is a graph that can be embedded on a surface with Euler characteristic λ so that each edge is crossed by at most one other edge. A graph G is called α-linear if there exists an integral constant β such that e(G') \leq α v(G')+β for each G'\subseteq G. In this paper, it is shown that every (1,λ)-embedded graph G is 4-linear for all possible λ, and is acyclicly edge-(3Δ(G)+70)-choosable for λ=1,2.

preprint2011arXiv

Degree conditions for the partition of a graph into triangles and quadrilaterals

For two positive integers $r$ and $s$ with $r\geq 2s-2$ , if $G$ is a graph of order $3r+4s$ such that $d(x)+d(y)\geq 4r+4s$ for every $xy\not\in E(G)$ , then $G$ independently contains $r$ triangles and $s$ quadrilaterals, which partially prove the El-Zahar's Conjecture.

preprint2011arXiv

Edge covering pseudo-outerplanar graphs with forests

A graph is called pseudo-outerplanar if each block has an embedding on the plane in such a way that the vertices lie on a fixed circle and the edges lie inside the disk of this circle with each of them crossing at most one another. In this paper, we prove that each pseudo-outerplanar graph admits edge decompositions into a linear forest and an outerplanar graph, or a star forest and an outerplanar graph, or two forests and a matching, or $\max\{Δ(G),4\}$ matchings, or $\max\{\lceilΔ(G)/2\rceil,3\}$ linear forests. These results generalize some ones on outerplanar graphs and $K_{2,3}$ -minor-free graphs, since the class of pseudo-outerplanar graphs is a larger class than the one of $K_{2,3}$ -minor-free graphs.

preprint2011arXiv

k-forested choosability of graphs with bounded maximum average degree

A proper vertex coloring of a simple graph is $k$ -forested if the graph induced by the vertices of any two color classes is a forest with maximum degree less than $k$ . A graph is $k$ -forested $q$ -choosable if for a given list of $q$ colors associated with each vertex $v$ , there exists a $k$ -forested coloring of $G$ such that each vertex receives a color from its own list. In this paper, we prove that the $k$ -forested choosability of a graph with maximum degree $Δ\geq k\geq 4$ is at most $\lceil\fracΔ{k-1}\rceil+1$ , $\lceil\fracΔ{k-1}\rceil+2$ or $\lceil\fracΔ{k-1}\rceil+3$ if its maximum average degree is less than 12/5, $8/3 or 3, respectively.

preprint2010arXiv

Edge Coloring of Triangle-Free 1-Planar Graphs

it is shown that each triangle-free 1-planar graph with maximum degree $Δ\geq7$ can be $Δ$ -colorable by Discharging Method.

preprint2010arXiv

Structural properties of 1-planar graphs and an application to acyclic edge coloring

A graph is called 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we establish a local property of 1-planar graphs which describes the structure in the neighborhood of small vertices (i.e. vertices of degree no more than seven). Meanwhile, some new classes of light graphs in 1-planar graphs with the bounded degree are found. Therefore, two open problems presented by Fabrici and Madaras [The structure of 1-planar graphs, Discrete Mathematics, 307, (2007), 854-865] are solved. Furthermore, we prove that each 1-planar graph $G$ with maximum degree $Δ(G)$ is acyclically edge $L$ -choosable where $L=\max\{2Δ(G)-2,Δ(G)+83\}$ .

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.

Jian-Liang Wu

Research overview

Is this your work?

9 publications

Toward Structural Controllability and Predictability in Directed Networks

A conjecture on equitable vertex arboricity of graphs

Equitable vertex arboricity of graphs

(1,λ)-embedded graphs and the acyclic edge choosability

Degree conditions for the partition of a graph into triangles and quadrilaterals

Edge covering pseudo-outerplanar graphs with forests

k-forested choosability of graphs with bounded maximum average degree

Edge Coloring of Triangle-Free 1-Planar Graphs

Structural properties of 1-planar graphs and an application to acyclic edge coloring

See the researcher in context

Building this map preview