BZPEER

preprint2022arXiv

A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs

Let $D$ be a digraph. We define the minimum semi-degree of $D$ as $δ^{0}(D) := \min \{δ^{+}(D), δ^{-}(D)\}$ . Let $k$ be a positive integer, and let $S = \{s\}$ and $T = \{t_{1}, \dots ,t_{k}\}$ be any two disjoint subsets of $V(D)$ . A set of $k$ internally disjoint paths joining source set $S$ and sink set $T$ that cover all vertices $D$ are called a one-to-many $k$ -disjoint directed path cover ( $k$ -DDPC for short) of $D$ . A digraph $D$ is semicomplete if for every pair $x,y$ of vertices of it, there is at least one arc between $x$ and $y$ . In this paper, we prove that every semicomplete digraph $D$ of sufficiently large order $n$ with $δ^{0}(D) \geq \lceil (n+k-1)/2\rceil$ has a one-to-many $k$ -DDPC joining any disjoint source set $S$ and sink set $T$ , where $S = \{s\}, T = \{t_{1}, \dots, t_{k}\}$ .

preprint2022arXiv

Sharp Bounds and Precise Values for the $N_i$ -Chromatic Number of Graphs

Let $G$ be a connected undirected graph.~A vertex coloring $f$ of $G$ is an $N_i$ -vertex coloring if for each vertex $x$ in $G$ , the number of different colors assigned to $N_G(x)$ is at most $i$ .~The $N_i$ -chromatic number of $G$ , denoted by $t_i(G)$ , is the maximum number of colors which are used in an $N_i$ -vertex coloring of $G$ . In this paper, we provide sharp bounds for $t_i(G)$ of a graph $G$ in terms of its vertex cover number, maximum degree and diameter, respectively. We also determine precise values for $t_i(G)$ in some cases.

preprint2022arXiv

Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs

Let $D=(V,A)$ be a digraph of order $n$ , $S$ a subset of $V$ of size $k$ and $2\le k\leq n$ . A strong subgraph $H$ of $D$ is called an $S$ -strong subgraph if $S\subseteq V(H)$ . A pair of $S$ -strong subgraphs $D_1$ and $D_2$ are said to be arc-disjoint if $A(D_1)\cap A(D_2)=\emptyset$ . Let $λ_S(D)$ be the maximum number of arc-disjoint $S$ -strong subgraphs in $D$ . The strong subgraph $k$ -arc-connectivity is defined as $λ_k(D)=\min\{λ_S(D)\mid S\subseteq V(D), |S|=k\}.$ The parameter $λ_k(D)$ can be seen as a generalization of classical edge-connectivity of undirected graphs. In this paper, we first obtain a formula for the arc-connectivity of Cartesian product $λ(G\Box H)$ of two digraphs $G$ and $H$ generalizing a formula for edge-connectivity of Cartesian product of two undirected graphs obtained by Xu and Yang (2006). Then we study the strong subgraph 2-arc-connectivity of Cartesian product $λ_2(G\Box H)$ and prove that $\min\left \{ λ\left ( G \right ) \left | H \right | , λ\left ( H \right ) \left |G \right |,δ^{+ } \left ( G \right )+ δ^{+ } \left ( H \right ),δ^{- } \left ( G \right )+ δ^{- } \left ( H \right ) \right \}\geλ_2(G\Box H)\ge λ_2(G)+λ_2(H)-1.$ The upper bound for $λ_2(G\Box H)$ is sharp and is a simple corollary of the formula for $λ(G\Box H)$ . The lower bound for $λ_2(G\Box H)$ is either sharp or almost sharp i.e. differs by 1 from the sharp bound. We also obtain exact values for $λ_2(G\Box H)$ , where $G$ and $H$ are digraphs from some digraph families.

preprint2020arXiv

Semicomplete Compositions of Digraphs

Let $T$ be a digraph with vertices $u_1, \dots, u_t$ ( $t\ge 2$ ) and let $H_1, \dots, H_t$ be digraphs such that $H_i$ has vertices $u_{i,j_i},\ 1\le j_i\le n_i.$ Then the composition $Q=T[H_1, \dots, H_t]$ is a digraph with vertex set $\{u_{i,j_i}\colon\, 1\le i\le t, 1\le j_i\le n_i\}$ and arc set $A(Q)=\cup^t_{i=1}A(H_i)\cup \{u_{ij_i}u_{pq_p}\colon\, u_iu_p\in A(T), 1\le j_i\le n_i, 1\le q_p\le n_p\}.$ The composition $Q=T[H_1, \dots, H_t]$ is a semicomplete composition if $T$ is semicomplete, i.e. there is at least one arc between every pair of vertices. Digraph compositions generalize some families of digraphs, including (extended) semicomplete digraphs, quasi-transitive digraphs and lexicographic product digraphs. In particular, strong semicomplete compositions form a significant generalization of strong quasi-transitive digraphs. In this paper, we study the structural properties of semicomplete compositions and obtain results on connectivity, paths, cycles, strong spanning subdigraphs and acyclic spanning subgraphs. Our results show that this class of digraphs shares some nice properties of quasi-transitive digraphs.

preprint2013arXiv

Characterize graphs with rainbow connection number $m-2$ and $m-3$

A path in an edge-colored graph, where adjacent edges may be colored the same, is a rainbow path if no two edges of it are colored the same. A nontrivial connected graph $G$ is rainbow connected if there is a rainbow path connecting any two vertices, and the rainbow connection number of $G$ , denoted by $rc(G)$ , is the minimum number of colors that are needed in order to make $G$ rainbow connected. Chartrand et al. obtained that $G$ is a tree if and only if $rc(G)=m$ , and it is easy to see that $G$ is not a tree if and only if $rc(G)\leq m-2$ , where $m$ is the number of edge of $G$ . So there is an interesting problem: Characterize the graphs $G$ with $rc(G)=m-2$ . In this paper, we settle down this problem. Furthermore, we also characterize the graphs $G$ with $rc(G)=m-3$ .

preprint2013arXiv

On the generalized (edge-)connectivity of graphs

The generalized $k$ -connectivity $κ_k(G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of generalized $k$ -edge-connectivity $λ_k(G)$ . For general $k$ , the generalized $k$ -edge-connectivity of a complete graph is obtained. For $k\geq 3$ , tight upper and lower bounds of $κ_k(G)$ and $λ_k(G)$ are given for a connected graph $G$ of order $n$ , that is, $1\leq κ_k(G)\leq n-\lceil\frac{k}{2}\rceil$ and $1\leq λ_k(G)\leq n-\lceil\frac{k}{2}\rceil$ . Graphs of order $n$ such that $κ_k(G)=n-\lceil\frac{k}{2}\rceil$ and $λ_k(G)=n-\lceil\frac{k}{2}\rceil$ are characterized, respectively. Nordhaus-Gaddum-type results for the generalized $k$ -connectivity are also obtained. For $k=3$ , we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of $λ_3(G)$ for a graph $G$ in terms of the edge-connectivity $λ$ of $G$ are obtained, that is, $\frac{3λ-2}{4}\leq λ_3(G)\leq λ$ , and two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain that $λ(G)-1\leq λ_3(G)\leq λ(G)$ if $G$ is a connected planar graph, and the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.

preprint2012arXiv

Graphs with large generalized 3-connectivity

Let $S$ be a nonempty set of vertices of a connected graph $G$ . A collection $T_1,..., T_\ell$ of trees in $G$ is said to be internally disjoint trees connecting $S$ if $E(T_i)\cap E(T_j)= \emptyset$ and $V(T_i)\cap V(T_j)=S$ for any pair of distinct integers $i, j$ , where $1 \leq i, j \leq r$ . For an integer $k$ with $2 \leq k \leq n$ , the generalized $k$ -connectivity $κ_k(G)$ of $G$ is the greatest positive integer $r$ such that $G$ contains at least $r$ internally disjoint trees connecting $S$ for any set $S$ of $k$ vertices of $G$ . Obviously, $κ_2(G)$ is the connectivity of $G$ . In this paper, sharp upper and lower bounds of $κ_3(G)$ are given for a connected graph $G$ of order $n$ , that is, $1 \leq κ_3(G) \leq n - 2$ . Graphs of order $n$ such that $κ_3(G) = n - 2, n - 3$ are characterized, respectively.

preprint2012arXiv

Note on minimally $k$ -rainbow connected graphs

An edge-colored graph $G$ , where adjacent edges may have the same color, is {\it rainbow connected} if every two vertices of $G$ are connected by a path whose edge has distinct colors. A graph $G$ is {\it $k$ -rainbow connected} if one can use $k$ colors to make $G$ rainbow connected. For integers $n$ and $d$ let $t(n,d)$ denote the minimum size (number of edges) in $k$ -rainbow connected graphs of order $n$ . Schiermeyer got some exact values and upper bounds for $t(n,d)$ . However, he did not get a lower bound of $t(n,d)$ for $3\leq d<\lceil\frac{n}{2}\rceil$ . In this paper, we improve his lower bound of $t(n,2)$ , and get a lower bound of $t(n,d)$ for $3\leq d<\lceil\frac{n}{2}\rceil$ .

preprint2011arXiv

Asymptotic value of the minimal size of a graph with rainbow connection number 2

A path in an edge (vertex)-colored graph $G$ , where adjacent edges (vertices) may have the same color, is called a rainbow path if no pair of edges (internal vertices) of the path are colored the same. The rainbow (vertex) connection number $rc(G)$ ( $rvc(G)$ ) of $G$ is the minimum integer $i$ for which there exists an $i$ -edge (vertex)-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. Denote by $\mathcal{G}_d(n)$ ( $\mathcal{G'}_d(n)$ ) the set of all graphs of order $n$ with rainbow (vertex) connection number $d$ , and define $e_d(n)=\min\{e(G)\,|\, G\in \mathcal{G}_d(n)\}$ ( $e_d'(n)=\min\{e(G)\,|\, G\in \mathcal{G'}_d(n)\}$ ), where $e(G)$ denotes the number of edges in $G$ . In this paper, we investigate the bounds of $e_2(n)$ and get the exact asymptotic value. i.e., $\displaystyle \lim_{n\rightarrow \infty}\frac{e_2(n)}{n\log_2 n}=1$ . Meanwhile, we obtain $e'_d(n)=n-1$ for $d\geq 2$ , and the equality holds if and only if $G$ is such a graph such that deleting all leaves of $G$ results in a tree of order $d$ .

preprint2011arXiv

Note on the oriented diameter of graphs with diameter 3

In 1978, Chvátal and Thomassen showed that every bridgeless graph with diameter 2 has an orientation with diameter at most 6. They also gave general bounds on the smallest value $f(d)$ such that every bridgeless graph $G$ with diameter $d$ has an orientation with diameter at most $f(d)$ . For $d=3$ , they proved that $8\leq f(d)\leq 24$ . Until recently, Kwok, Liu and West improved the above bounds by proving $9\leq f(3)\leq 11$ in [P.K. Kwok, Q. Liu and D.B. West, Oriented diameter of graphs with diameter 3, J. Combin. Theory Ser.B 100(2010), 265-274]. In this paper, we determine the oriented diameter among the bridgeless graphs with diameter 3 that have minimum number of edges.

preprint2011arXiv

Oriented diameter and rainbow connection number of a graph

The oriented diameter of a bridgeless graph $G$ is $\min\{diam(H)\ | H\ is\ an orientation\ of\ G\}$ . A path in an edge-colored graph $G$ , where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the smallest integer $k$ for which there exists a $k$ -edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. In this paper, we obtain upper bounds for the oriented diameter and the rainbow connection number of a graph in terms of $rad(G)$ and $η(G)$ , where $rad(G)$ is the radius of $G$ and $η(G)$ is the smallest integer number such that every edge of $G$ is contained in a cycle of length at most $η(G)$ . We also obtain constant bounds of the oriented diameter and the rainbow connection number for a (bipartite) graph $G$ in terms of the minimum degree of $G$ .

preprint2011arXiv

Rainbow connections of graphs -- A survey

The concept of rainbow connection was introduced by Chartrand et al. in 2008. It is fairly interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most of the results and papers that dealt with it. We begin with an introduction, and then try to organize the work into five categories, including (strong) rainbow connection number, rainbow $k$ -connectivity, $k$ -rainbow index, rainbow vertex-connection number, algorithms and computational complexity. This survey also contains some conjectures, open problems or questions.

preprint2011arXiv

The generalized 3-connectivity of Cartesian product graphs

The generalized connectivity of a graph, which was introduced recently by Chartrand et al., is a generalization of the concept of vertex connectivity. Let $S$ be a nonempty set of vertices of $G$ , a collection $\{T_1,T_2,...,T_r\}$ of trees in $G$ is said to be internally disjoint trees connecting $S$ if $E(T_i)\cap E(T_j)=\emptyset$ and $V(T_i)\cap V(T_j)=S$ for any pair of distinct integers $i,j$ , where $1\leq i,j\leq r$ . For an integer $k$ with $2\leq k\leq n$ , the $k$ -connectivity $κ_k(G)$ of $G$ is the greatest positive integer $r$ for which $G$ contains at least $r$ internally disjoint trees connecting $S$ for any set $S$ of $k$ vertices of $G$ . Obviously, $κ_2(G)=κ(G)$ is the connectivity of $G$ . Sabidussi showed that $κ(G\Box H) \geq κ(G)+κ(H)$ for any two connected graphs $G$ and $H$ . In this paper, we first study the 3-connectivity of the Cartesian product of a graph $G$ and a tree $T$ , and show that $(i)$ if $κ_3(G)=κ(G)\geq 1$ , then $κ_3(G\Box T)\geq κ_3(G)$ ; $(ii)$ if $1\leq κ_3(G)< κ(G)$ , then $κ_3(G\Box T)\geq κ_3(G)+1$ . Furthermore, for any two connected graphs $G$ and $H$ with $κ_3(G)\geqκ_3(H)$ , if $κ(G)>κ_3(G)$ , then $κ_3(G\Box H)\geq κ_3(G)+κ_3(H)$ ; if $κ(G)=κ_3(G)$ , then $κ_3(G\Box H)\geq κ_3(G)+κ_3(H)-1$ . Our result could be seen as a generalization of Sabidussi's result. Moreover, all the bounds are sharp.

preprint2011arXiv

Upper bound for the rainbow connection number of bridgeless graphs with diameter 3

A path in an edge-colored graph $G$ , where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the smallest integer $k$ for which there exists a $k$ -edge-coloring of $G$ such that every pair of distinct vertices of $G$ is connected by a rainbow path. It is known that for every integer $k\geq 2$ deciding if a graph $G$ has $rc(G)\leq k$ is NP-Hard, and a graph $G$ with $rc(G)\leq k$ has diameter $diam(G)\leq k$ . In foregoing papers, we showed that a bridgeless graph with diameter 2 has rainbow connection number at most 5. In this paper, we prove that a bridgeless graph with diameter 3 has rainbow connection number at most 9. We also prove that for any bridgeless graph $G$ with radius $r$ , if every edge of $G$ is contained in a triangle, then $rc(G)\leq 3r$ . As an application, we get that for any graph $G$ with minimum degree at least 3, $rc(L(G))\leq 3 rad(L(G))\leq 3 (rad(G)+1)$ .

preprint2010arXiv

Note on the Rainbow $k$ -Connectivity of Regular Complete Bipartite Graphs

A path in an edge-colored graph $G$ , where adjacent edges may be colored the same, is called a rainbow path if no two edges of the path are colored the same. For a $κ$ -connected graph $G$ and an integer $k$ with $1\leq k\leq κ$ , the rainbow $k$ -connectivity $rc_k(G)$ of $G$ is defined as the minimum integer $j$ for which there exists a $j$ -edge-coloring of $G$ such that any two distinct vertices of $G$ are connected by $k$ internally disjoint rainbow paths. Denote by $K_{r,r}$ an $r$ -regular complete bipartite graph. Chartrand et al. in "G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity of a graph, Networks 54(2009), 75-81" left an open question of determining an integer $g(k)$ for which the rainbow $k$ -connectivity of $K_{r,r}$ is 3 for every integer $r\geq g(k)$ . This short note is to solve this question by showing that $rc_k(K_{r,r})=3$ for every integer $r\geq 2k\lceil\frac{k}{2}\rceil$ , where $k\geq 2$ is a positive integer.

preprint2010arXiv

On strong rainbow connection number

A path in an edge-colored graph, where adjacent edges may be colored the same, is a rainbow path if no two edges of it are colored the same. For any two vertices $u$ and $v$ of $G$ , a rainbow $u-v$ geodesic in $G$ is a rainbow $u-v$ path of length $d(u,v)$ , where $d(u,v)$ is the distance between $u$ and $v$ . The graph $G$ is strongly rainbow connected if there exists a rainbow $u-v$ geodesic for any two vertices $u$ and $v$ in $G$ . The strong rainbow connection number of $G$ , denoted $src(G)$ , is the minimum number of colors that are needed in order to make $G$ strong rainbow connected. In this paper, we first investigate the graphs with large strong rainbow connection numbers. Chartrand et al. obtained that $G$ is a tree if and only if $src(G)=m$ , we will show that $src(G)\neq m-1$ , so $G$ is not a tree if and only if $src(G)\leq m-2$ , where $m$ is the number of edge of $G$ . Furthermore, we characterize the graphs $G$ with $src(G)=m-2$ . We next give a sharp upper bound for $src(G)$ according to the number of edge-disjoint triangles in graph $G$ , and give a necessary and sufficient condition for the equality.

preprint2010arXiv

Rainbow connection numbers of complementary graphs

A path in an edge-colored graph, where adjacent edges may be colored the same, is a rainbow path if no two edges of it are colored the same. A nontrivial connected graph $G$ is rainbow connected if there is a rainbow path connecting any two vertices, and the rainbow connection number of $G$ , denoted by $rc(G)$ , is the minimum number of colors that are needed in order to make $G$ rainbow connected. In this paper, we provide a new approach to investigate the rainbow connection number of a graph $G$ according to some constraints to its complement graph $\bar{G}$ . We first derive that for a connected graph $G$ , if $\bar{G}$ does not belong to the following two cases: $(i)$ ~ $diam(\bar{G})=2,3$ , $(ii)~\bar{G}$ contains exactly two connected components and one of them is trivial, then $rc(G)\leq 4$ , where $diam(G)$ is the diameter of $G$ . Examples are given to show that this bound is best possible. Next we derive that for a connected graph $G$ , if $\bar{G}$ is triangle-free, then $rc(G)\leq 6$ .

preprint2010arXiv

Upper bounds for the rainbow connection numbers of line graphs

A path in an edge-colored graph $G$ , where adjacent edges may be colored the same, is called a rainbow path if no two edges of it are colored the same. A nontrivial connected graph $G$ is rainbow connected if for any two vertices of $G$ there is a rainbow path connecting them. The rainbow connection number of $G$ , denoted by $rc(G)$ , is defined as the smallest number of colors by using which there is a coloring such that $G$ is rainbow connected. In this paper, we mainly study the rainbow connection number of the line graph of a graph which contains triangles and get two sharp upper bounds for $rc(L(G))$ , in terms of the number of edge-disjoint triangles of $G$ where $L(G)$ is the line graph of $G$ . We also give results on the iterated line graphs.

Yuefang Sun

Research overview

Is this your work?

18 publications

A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs

Sharp Bounds and Precise Values for the $N_i$ -Chromatic Number of Graphs

Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs

Semicomplete Compositions of Digraphs

Characterize graphs with rainbow connection number $m-2$ and $m-3$

On the generalized (edge-)connectivity of graphs

Graphs with large generalized 3-connectivity

Note on minimally $k$ -rainbow connected graphs

Asymptotic value of the minimal size of a graph with rainbow connection number 2

Note on the oriented diameter of graphs with diameter 3

Oriented diameter and rainbow connection number of a graph

Rainbow connections of graphs -- A survey

The generalized 3-connectivity of Cartesian product graphs

Upper bound for the rainbow connection number of bridgeless graphs with diameter 3

Note on the Rainbow $k$ -Connectivity of Regular Complete Bipartite Graphs

On strong rainbow connection number

Rainbow connection numbers of complementary graphs

Upper bounds for the rainbow connection numbers of line graphs

See the researcher in context

Building this map preview

Yuefang Sun

Research overview

Is this your work?

18 publications

A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs

Sharp Bounds and Precise Values for the NiN_iNi​-Chromatic Number of Graphs

Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs

Semicomplete Compositions of Digraphs

Characterize graphs with rainbow connection number m−2m-2m−2 and m−3m-3m−3

On the generalized (edge-)connectivity of graphs

Graphs with large generalized 3-connectivity

Note on minimally kkk-rainbow connected graphs

Asymptotic value of the minimal size of a graph with rainbow connection number 2

Note on the oriented diameter of graphs with diameter 3

Oriented diameter and rainbow connection number of a graph

Rainbow connections of graphs -- A survey

The generalized 3-connectivity of Cartesian product graphs

Upper bound for the rainbow connection number of bridgeless graphs with diameter 3

Note on the Rainbow kkk-Connectivity of Regular Complete Bipartite Graphs

On strong rainbow connection number

Rainbow connection numbers of complementary graphs

Upper bounds for the rainbow connection numbers of line graphs

See the researcher in context

Building this map preview

Sharp Bounds and Precise Values for the $N_i$ -Chromatic Number of Graphs

Characterize graphs with rainbow connection number $m-2$ and $m-3$

Note on minimally $k$ -rainbow connected graphs

Note on the Rainbow $k$ -Connectivity of Regular Complete Bipartite Graphs