Source author record

Shujing Wang

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

6works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Proper connection number and 2-proper connection number of a graph

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored with one same color. An edge-colored graph is called $k$ -proper connected if any two vertices of the graph are connected by $k$ internally pairwise vertex-disjoint proper paths in the graph. The $k$ -proper connection number of a $k$ -connected graph $G$ , denoted by $pc_k(G)$ , is defined as the smallest number of colors that are needed in order to make $G$ $k$ -proper connected. For $k=1$ , we write $pc(G)$ other than $pc_1(G)$ , and call it the proper connection number of $G$ . In this paper, we present an upper bound for the proper connection number of a graph $G$ in terms of the minimum degree of $G$ , and give some sufficient conditions for a graph to have $2$ -proper connection number two. Also, we investigate the proper connection numbers of dense graphs.

preprint2015arXiv

Proper connection numbers of complementary graphs

A path $P$ in an edge-colored graph $G$ is called a proper path if no two adjacent edges of $P$ are colored the same, and $G$ is proper connected if every two vertices of $G$ are connected by a proper path in $G$ . The proper connection number of a connected graph $G$ , denoted by $pc(G)$ , is the minimum number of colors that are needed to make $G$ proper connected. In this paper, we investigate the proper connection number of the complement of graph $G$ according to some constraints of $G$ itself. Also, we characterize the graphs on $n$ vertices that have proper connection number $n-2$ . Using this result, we give a Nordhaus-Gaddum-type theorem for the proper connection number. We prove that if $G$ and $\overline{G}$ are both connected, then $4\le pc(G)+pc(\overline{G})\le n$ , and the only graph attaining the upper bound is the tree with maximum degree $Δ=n-2$ .

preprint2014arXiv

On graphs with maximum Harary spectral radius

Let $G$ be a simple graph with vertex set $V(G) = \{v_1 ,v_2 ,\cdots ,v_n\}$ . The Harary matrix $RD(G)$ of $G$ , which is initially called the reciprocal distance matrix, is an $n \times n$ matrix whose $(i,j)$ -entry is equal to $\frac{1}{d_{ij}}$ if $i\not=j$ and $0$ otherwise, where $d_{ij}$ is the distance of $v_i$ and $v_j$ in $G$ . In this paper, we characterize graphs with maximum spectral radius of Harary matrix in three classes of simple connected graphs with $n$ vertices: graphs with fixed matching number, bipartite graphs with fixed matching number, and graphs with given number of cut edges, respectively.

preprint2014arXiv

On maximum Estrada indices of bipartite graphs with some given parameters

The Estrada index of a graph $G$ is defined as $EE(G)=\sum_{i=1}^ne^{λ_i}$ , where $λ_1,$ $λ_2,\ldots, λ_n$ are the eigenvalues of the adjacency matrix of $G$ . In this paper, we characterize the unique bipartite graph with maximum Estrada index among bipartite graphs with given matching number and given vertex-connectivity, edge-connectivity, respectively.

preprint2012arXiv

Enumerating the total number of subtrees of trees

Over some types of trees with a given number of vertices, which trees minimize or maximize the total number of subtrees or leaf containing subtrees are studied. Here are some of the main results:\ (1)\, Sharp upper bound on the total number of subtrees (resp. leaf containing subtrees) among $n$ -vertex trees with a given matching number is determined; as a consequence, the $n$ -vertex tree with domination number $γ$ maximizing the total number of subtrees (resp. leaf containing subtrees) is characterized. (2)\, Sharp lower bound on the total number of leaf containing subtrees among $n$ -vertex trees with maximum degree at least $Δ$ is determined; as a consequence the $n$ -vertex tree with maximum degree at least $Δ$ having a perfect matching minimizing the total number of subtrees (resp. leaf containing subtrees) is characterized. (3)\, Sharp upper (resp. lower) bound on the total number of leaf containing subtrees among the set of all $n$ -vertex trees with $k$ leaves (resp. the set of all $n$ -vertex trees of diameter $d$ ) is determined.

preprint2012arXiv

Further analysis on the total number of subtrees of trees

We study that over some types of trees with a given number of vertices, which trees minimize or maximize the total number of subtrees. Trees minimizing (resp. maximizing) the total number of subtrees usually maximize (resp. minimize) the Wiener index, and vice versa. Here are some of our results: (1) Let $\mathscr{T}_n^k$ be the set of all $n$ -vertex trees with $k$ leaves, we determine the maximum (resp. minimum) value of the total number of subtrees of trees among $\mathscr{T}_n^k$ and characterize the extremal graphs. (2) Let $\mathscr{P}_n^{p,q}$ be the set of all $n$ -vertex trees, each of which has a $(p,q)$ -bipartition, we determine the maximum (resp. minimum) value of the total number of subtrees of trees among $\mathscr{P}_n^{p,q}$ and characterize the extremal graphs. (3) Let $\mathscr{A}_n^q$ be the set of all $q$ -ary trees with $n$ non-leaf vertices, we determine the minimum value of the total number of subtrees of trees among $\mathscr{A}_n^q$ and identify the extremal graph.

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.