Source author record

Yuansheng Yang

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

13works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The crossing number of the complete 4-partite graph $K_{1,1,m,n}$

Let $\textrm{cr}(G)$ denote the crossing number of a graph $G$ . The well-known Zarankiewicz's conjecture (ZC) asserted $\textrm{cr}(K_{m,n})$ in 1954. In 1971, Harborth gave a conjecture (HC) on $\textrm{cr}(K_{x_1,...,x_n})$ . HC on $K_{1,m,n}$ is verified if ZC is true by Ho et al. in 2021. In this paper, we showed the following results: If both $m$ and $n$ are even, then $\textrm{cr}(K_{1,1,m,n})\geq \frac{1}{2}(\textrm{cr}(K_{m+1,n+3})+\textrm{cr}(K_{m+3,n+1})-mn-\frac{1}{4}(m^2+n^2));$ If both $m$ and $n$ are odd, then $\textrm{cr}(K_{1,1,m,n})\geq \frac{1}{2}(\textrm{cr}(K_{1,m+1,n+1})+\textrm{cr}(K_{2,m,n})-\frac{1}{4}(m+1)(n+1)+1);$ If $m$ is even and $n$ is odd, then \begin{equation}\nonumber \begin{split} \textrm{cr}(K_{1,1,m,n})&\geq \frac{1}{4}(\textrm{cr}(K_{m+1,n+2})+\textrm{cr}(K_{m+3,n+2})+2\textrm{cr}(K_{2,m,n}) \\&-m(n+1)-\frac{1}{4}(n+1)^2). \end{split} \end{equation} The lower bounds in our result imply that if both $m$ and $n$ are even and ZC is true, then HC on $K_{1,1,m,n}$ holds; if at least one of $m$ and $n$ is odd and both ZC and HC on $K_{2,m,n}$ are true, then HC on $K_{1,1,m,n}$ holds.

preprint2020arXiv

Italian domination in generalized Petersen graphs

In a graph $G=(V,E)$ , each vertex $v\in V$ is labelled with $0$ , $1$ or $2$ such that each vertex labelled with $0$ is adjacent to at least one vertex labelled $2$ or two vertices labelled $1$ . Such kind of labelling is called an Italian dominating function (IDF) of $G$ . The weight of an IDF $f$ is $w(f)=\sum_{v\in V}f(v)$ . The Italian domination number of $G$ is $γ_{I}(G)=\min_{f} w(f)$ . Gao et al. (2019) have determined the value of $γ_I(P(n,3))$ . In this article, we focus on the study of the Italian domination number of generalized Petersen graphs $P(n, k)$ , $k\neq3$ . We determine the values of $γ_I(P(n, 1))$ , $γ_I(P(n, 2))$ and $γ_I(P(n, k))$ for $k\ge4$ , $k\equiv2,3(\bmod5)$ and $n\equiv0(\bmod5)$ . For other $P(n,k)$ , we present a bound of $γ_I(P(n, k))$ . With the obtained results, we partially solve the open problem presented by Brešar et al. (2007) by giving $P(n,1)$ is an example for which $γ_I=γ_{r2}$ and characterizing $P(n,2)$ for which $γ_I(P(n,2))=γ_{r2}(P(n,2))$ . Moreover, our results imply $P(n,1)$ $(n\equiv0(\bmod\ 4))$ is Italian, $P(n,1)$ $(n\not\equiv0(\bmod\ 4))$ and $P(n,2)$ are not Italian.

preprint2013arXiv

The crossing number of cubes with small order

The {\it crossing number} of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$ . In this paper, we give the exact values of crossing numbers for some variations of hypercube with order at most four, including crossed cube, locally twisted cube and Möbius cube.

preprint2012arXiv

An upper bound for the crossing number of augmented cubes

A {\it good drawing} of a graph $G$ is a drawing where the edges are non-self-intersecting and each two edges have at most one point in common, which is either a common end vertex or a crossing. The {\it crossing number} of a graph $G$ is the minimum number of pairwise intersections of edges in a good drawing of $G$ in the plane. The {\it $n$ -dimensional augmented cube} $AQ_n$ , proposed by S.A. Choudum and V. Sunitha, is an important interconnection network with good topological properties and applications. In this paper, we obtain an upper bound on the crossing number of $AQ_n$ less than $26/324^{n}-(2n^2+7/2n-6)2^{n-2}$ .

preprint2012arXiv

An upper bound for the crossing number of bubble-sort graph Bn

The crossing number of a graph G is the minimum number of pairwise intersections of edges in a drawing of G. Motivated by the recent work [Faria, L., Figueiredo, C.M.H. de, Sykora, O., Vrt'o, I.: An improved upper bound on the crossing number of the hypercube. J. Graph Theory 59, 145-161 (2008)], we give an upper bound of the crossing number of n-dimensional bubble-sort graph Bn.

preprint2012arXiv

The crossing number of pancake graph $P_4$ is six

The {\it crossing number} of a graph $G$ is the least number of pairwise crossings of edges among all the drawings of $G$ in the plane. The pancake graph is an important topology for interconnecting processors in parallel computers. In this paper, we prove the exact value of the crossing number of pancake graph $P_4$ is six.

preprint2012arXiv

The crossing number of the generalized Petersen graph P(10, 3) is six

The crossing number of a graph is the least number of crossings of edges among all drawings of the graph in the plane. In this article, we prove that the crossing number of the generalized Petersen graph P(10, 3) is equal to 6.

preprint2012arXiv

The crossing numbers of $K_{n,n}-nK_2$ , $K_{n}\times P_2$ , $K_{n}\times P_3$ and $K_n\times C_4$

The crossing number of a graph $G$ is the minimum number of pairwise intersections of edges among all drawings of $G$ . In this paper, we study the crossing number of $K_{n,n}-nK_2$ , $K_n\times P_2$ , $K_n\times P_3$ and $K_n\times C_4$ .

preprint2012arXiv

The crossing numbers of $K_m\times P_n$ and $K_m\times C_n$

The {\it crossing number} of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$ . In this paper, we study the crossing numbers of $K_{m}\times P_n$ and $K_{m}\times C_n$ .

preprint2011arXiv

On the Domination Number of Generalized Petersen Graphs P(ck,k)

Let $G=(V(G),E(G))$ be a simple connected and undirected graph with vertex set $V(G)$ and edge set $E(G)$ . A set $S \subseteq V(G)$ is a $dominating$ $set$ if for each $v \in V(G)$ either $v \in S$ or $v$ is adjacent to some $w \in S$ . That is, $S$ is a dominating set if and only if $N[S]=V(G)$ . The domination number $γ(G)$ is the minimum cardinalities of minimal dominating sets. In this paper, we give an improved upper bound on the domination number of generalized Petersen graphs $P(ck,k)$ for $c\geq 3$ and $k\geq 3$ . We also prove that $γ(P(4k,k))=2k+1$ for even $k$ , $γ(P(5k,k))=3k$ for all $k\geq 1$ , and $γ(P(6k,k))=\lceil\frac{10k}{3}\rceil$ for $k\geq 1$ and $k\neq 2$ .

preprint2011arXiv

Roman domination number of Generalized Petersen Graphs P(n,2)

A $Roman\ domination\ function$ on a graph $G=(V, E)$ is a function $f:V(G)\rightarrow\{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ with $f(v)=2$ . The $weight$ of a Roman domination function $f$ is the value $f(V(G))=\sum_{u\in V(G)}f(u)$ . The minimum weight of a Roman dominating function on a graph $G$ is called the $Roman\ domination\ number$ of $G$ , denoted by $γ_{R}(G)$ . In this paper, we study the {\it Roman domination number} of generalized Petersen graphs P(n,2) and prove that $γ_R(P(n,2)) = \lceil {\frac{8n}{7}}\rceil (n \geq 5)$ .

preprint2011arXiv

The crossing number of folded hypercubes

The {\it crossing number} of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$ . The {\it $n$ -dimensional folded hypercube} $FQ_n$ is a graph obtained from $n$ -dimensional hypercube by adding all complementary edges. In this paper, we obtain upper and lower bounds of the crossing number of $FQ_n$ .

preprint2011arXiv

The crossing number of locally twisted cubes

The {\it crossing number} of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$ . Motivated by the recent work [Faria, L., Figueiredo, C.M.H. de, Sykora, O., Vrt'o, I.: An improved upper bound on the crossing number of the hypercube. J. Graph Theory {\bf 59}, 145--161 (2008)] which solves the upper bound conjecture on the crossing number of $n$ -dimensional hypercube proposed by Erdős and Guy, we give upper and lower bounds of the crossing number of locally twisted cube, which is one of variants of hypercube.

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.

Yuansheng Yang

Research overview

Is this your work?

13 publications

The crossing number of the complete 4-partite graph $K_{1,1,m,n}$

Italian domination in generalized Petersen graphs

The crossing number of cubes with small order

An upper bound for the crossing number of augmented cubes

An upper bound for the crossing number of bubble-sort graph Bn

The crossing number of pancake graph $P_4$ is six

The crossing number of the generalized Petersen graph P(10, 3) is six

The crossing numbers of $K_{n,n}-nK_2$ , $K_{n}\times P_2$ , $K_{n}\times P_3$ and $K_n\times C_4$

The crossing numbers of $K_m\times P_n$ and $K_m\times C_n$

On the Domination Number of Generalized Petersen Graphs P(ck,k)

Roman domination number of Generalized Petersen Graphs P(n,2)

The crossing number of folded hypercubes

The crossing number of locally twisted cubes

See the researcher in context

Building this map preview

Yuansheng Yang

Research overview

Is this your work?

13 publications

The crossing number of the complete 4-partite graph K1,1,m,nK_{1,1,m,n}K1,1,m,n​

Italian domination in generalized Petersen graphs

The crossing number of cubes with small order

An upper bound for the crossing number of augmented cubes

An upper bound for the crossing number of bubble-sort graph Bn

The crossing number of pancake graph P4P_4P4​ is six

The crossing number of the generalized Petersen graph P(10, 3) is six

The crossing numbers of Kn,n−nK2K_{n,n}-nK_2Kn,n​−nK2​, Kn×P2K_{n}\times P_2Kn​×P2​, Kn×P3K_{n}\times P_3Kn​×P3​ and Kn×C4K_n\times C_4Kn​×C4​

The crossing numbers of Km×PnK_m\times P_nKm​×Pn​ and Km×CnK_m\times C_nKm​×Cn​

On the Domination Number of Generalized Petersen Graphs P(ck,k)

Roman domination number of Generalized Petersen Graphs P(n,2)

The crossing number of folded hypercubes

The crossing number of locally twisted cubes

See the researcher in context

Building this map preview

The crossing number of the complete 4-partite graph $K_{1,1,m,n}$

The crossing number of pancake graph $P_4$ is six

The crossing numbers of $K_{n,n}-nK_2$ , $K_{n}\times P_2$ , $K_{n}\times P_3$ and $K_n\times C_4$

The crossing numbers of $K_m\times P_n$ and $K_m\times C_n$