Source author record

Xingchao Deng

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

A note on a conjecture of star chromatic index for outerplanar graphs

A star edge coloring of a graph $G$ is a proper edge coloring of $G$ without bichromatic paths or cycles of length four. The it star chromatic index, $χ_{st}^{'} (G ),$ of $G$ is the minimum number $k$ for which $G$ has a star edge coloring by $k$ colors. In \cite{LB}, L. Bezegov $\acute{a}$ et al. conjectured that $χ_{st}^{'} (G )\leq \lfloor\frac{3Δ}{2}\rfloor+1$ when $G$ is an outerplanar graph with maximum degree $Δ\geq 3.$ In this paper we obtained that $χ_{st}^{'}(G) \leq Δ+6$ when $G$ is an 2-connected outerplanar graph with diameter 2 or 3. If $G$ is an 2-connected outerplanar graph with maximum degree 5, then $χ_{st}^{'}(G) \leq 9.$

preprint2016arXiv

Algorithm on rainbow connection for maximal outerplanar graphs

In this paper, we consider rainbow connection number of maximal outerplanar graphs(MOPs) on algorithmic aspect. For the (MOP) $G$ , we give sufficient conditions to guarantee that $rc(G) = diam(G).$ Moreover, we produce the graph with given diameter $d$ and give their rainbow coloring in linear time. X.Deng et al. $\cite{XD}$ give a polynomial time algorithm to compute the rainbow connection number of MOPs by the Maximal fan partition method, but only obtain a compact upper bound. J. Lauri $\cite{JL}$ proved that, for chordal outerplanar graphs given an edge-coloring, to verify whether it is rainbow connected is NP-complete under the coloring, it is so for MOPs. Therefore we construct Central-cut-spine of MOP $G,$ by which we design an algorithm to give a rainbow edge coloring with at most $2rad(G)+2+c,0\leq c\leq rad(G)-2$ colors in polynomial time.

preprint2016arXiv

Rainbow connection of bridgeless outerplanar graphs with small diameters

In this paper, we investigate rainbow connection number $rc(G)$ of bridgeless outerplanar graphs $G$ with diameter 2 or 3. We proved the following results: If $G$ has diameter $2,$ then $rc(G)=3$ for fan graphs $F_{n}$ with $n\geq 7$ or $C_5,$ otherwise $rc(G)=2;$ if $G$ has diameter $3,$ then $rc(G)\leq 4$ and the bound is sharp.

preprint2012arXiv

Concentration properties of semi-vertex transitive graphs and random bi-coset graphs

It is well-known that concentrators are sparse graphs of high connectivity, which play a key role in the construction of switching networks; and any semi-vertex transitive graph is isomorphic to a bi-coset graph. In this paper, we prove that random bi-coset graphs are almost always concentrators, and construct some examples of semi-vertex transitive concentrators.

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.