BZPEER

preprint2022arXiv

A general approach to deriving diagnosability results of interconnection networks

We generalize an approach to deriving diagnosability results of various interconnection networks in terms of the popular $g$ -good-neighbor and $g$ -extra fault-tolerant models, as well as mainstream diagnostic models such as the PMC and the MM* models. As demonstrative examples, we show how to follow this constructive, and effective, process to derive the $g$ -extra diagnosabilities of the hypercube, the $(n, k)$ -star, and the arrangement graph. These results agree with those achieved individually, without duplicating structure independent technical details. Some of them come with a larger applicable range than those already known, and the result for the arrangement graph in terms of the MM* model is new.

preprint2022arXiv

Some multivariable Rado numbers

The Rado number of an equation is a Ramsey-theoretic quantity associated to the equation. Let $\mathcal{E}$ be a linear equation. Denote by $\operatorname{R}_r(\mathcal{E})$ the minimal integer, if it exists, such that any $r$ -coloring of $[1,\operatorname{R}_r(\mathcal{E})]$ must admit a monochromatic solution to $\mathcal{E}$ . In this paper, we give upper and lower bounds for the Rado number of $\sum_{i=1}^{m-2}x_i+kx_{m-1}=\ell x_{m}$ , and some exact values are also given. Furthermore, we derive some results for the cases that $\ell=m=4$ and $m=5, \ell=k+i \ (1\leq i\leq 5)$ . As a generalization, the \emph{ $r$ -color Rado numbers} for linear equations $\mathcal{E}_1,\mathcal{E}_2,...,\mathcal{E}_r$ is defined as the minimal integer, if it exists, such that any $r$ -coloring of $[1,\operatorname{R}_r(\mathcal{E}_1,\mathcal{E}_2,...,\mathcal{E}_r)]$ must admit a monochromatic solution to some $\mathcal{E}_i$ , where $1\leq i\leq r$ . A lower bound for $\operatorname{R}_r(\mathcal{E}_1,\mathcal{E}_2,...,\mathcal{E}_r)$ and the exact values of $\operatorname{R}_2(x+y=z,\ell x=y)=5k$ and $\operatorname{R}_2(x+y=z, x+a=y)$ was given by Lovász Local Lemma.

preprint2020arXiv

Gallai Ramsey number for double stars

Given a graph $G$ and a positive integer $k$ , the \emph{Gallai-Ramsey number} is defined to be the minimum number of vertices $n$ such that any $k$ -edge coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $G$ . In this paper, we obtain general upper and lower bounds on the Gallai-Ramsey numbers for double stars $S(n,m)$ , where $S(n,m)$ is the graph obtained from the union of two stars $K_{1,n}$ and $K_{1,m}$ by adding an edge between their centers. We also provide the sharp result in some cases.

preprint2020arXiv

Gallai-Ramsey number for the union of stars

Given a graph $G$ and a positive integer $k$ , define the \emph{Gallai-Ramsey number} to be the minimum number of vertices $n$ such that any $k$ -edge coloring of the complete graph $K_n$ contains either a rainbow (all different colored) triangle or a monochromatic copy of $G$ . In this paper, we obtain the exact value of the Gallai-Ramsey numbers for the union of two stars in many cases and bounds in other cases. This work represents the first class of disconnected graphs to be considered as the desired monochromatic subgraph.

preprint2016arXiv

Line k-Arboricity in Product Networks

A \emph{linear $k$ -forest} is a forest whose components are paths of length at most $k$ . The \emph{linear $k$ -arboricity} of a graph $G$ , denoted by ${\rm la}_k(G)$ , is the least number of linear $k$ -forests needed to decompose $G$ . Recently, Zuo, He and Xue studied the exact values of the linear $(n-1)$ -arboricity of Cartesian products of various combinations of complete graphs, cycles, complete multipartite graphs. In this paper, for general $k$ we show that $\max\{{\rm la}_{k}(G),{\rm la}_{\ell}(H)\}\leq {\rm la}_{\max\{k,\ell\}}(G\Box H)\leq {\rm la}_{k}(G)+{\rm la}_{\ell}(H)$ for any two graphs $G$ and $H$ . Denote by $G\circ H$ , $G\times H$ and $G\boxtimes H$ the lexicographic product, direct product and strong product of two graphs $G$ and $H$ , respectively. We also derive upper and lower bounds of ${\rm la}_{k}(G\circ H)$ , ${\rm la}_{k}(G\times H)$ and ${\rm la}_{k}(G\boxtimes H)$ in this paper. The linear $k$ -arboricity of a $2$ -dimensional grid graph, a $r$ -dimensional mesh, a $r$ -dimensional torus, a $r$ -dimensional generalized hypercube and a $2$ -dimensional hyper Petersen network are also studied.

preprint2016arXiv

On the Equitable Vertex Arboricity of Graphs

The equitable coloring problem, introduced by Meyer in 1973, has received considerable attention and research. Recently, Wu, Zhang and Li introduced the concept of equitable $(t,k)$ -tree-coloring, which can be regarded as a generalization of proper equitable $t$ -coloring. The \emph{strong equitable vertex $k$ -arboricity} of $G$ , denoted by ${va_k}^\equiv(G)$ , is the smallest integer $t$ such that $G$ has an equitable $(t', k)$ -tree-coloring for every $t'\geq t$ . The exact value of strong equitable vertex $k$ -arboricity of complete equipartition bipartite graph $K_{n,n}$ was studied by Wu, Zhang and Li. In this paper, we first get a sharp upper bound of strong equitable vertex arboricity of complete bipartite graph $K_{n,n+\ell} \ (1\leq \ell\leq n)$ , that is, ${va_2}^\equiv(K_{n,n+\ell})\leq2\left\lfloor{\frac{n+\ell+1}{3}}\right\rfloor$ . Next, we obtain a sufficient and necessary condition on an equitable $(q,\infty)$ -tree coloring of a complete equipartition tripartite graph, and study the strong equitable vertex arboricity of forests. For a simple graph $G$ of order $n$ , we show that $1\leq {va_k}^\equiv(G)\leq \lceil n/2 \rceil$ . Furthermore, graphs with ${va_k}^\equiv(G)=1,\lceil\frac{n}{2}\rceil,\lceil\frac{n}{2}\rceil-1$ are characterized, respectively. In the end, we obtain the Nordhaus-Gaddum type results of strong equitable vertex $k$ -arboricity for general $k$ .

preprint2016arXiv

Path connectivity of line graphs

Dirac showed that in a $(k-1)$ -connected graph there is a path through each $k$ vertices. The path $k$ -connectivity $π_k(G)$ of a graph $G$ , which is a generalization of Dirac's notion, was introduced by Hager in 1986. In this paper, we study path connectivity of line graphs.

preprint2016arXiv

Pendant-tree connectivity of line graphs

The concept of pendant-tree connectivity, introduced by Hager in 1985, is a generalization of classical vertex-connectivity. In this paper, we study pendant-tree connectivity of line graphs.

preprint2016arXiv

The minimal size of graphs with given pendant-tree connectivity

The concept of pendant-tree $k$ -connectivity $τ_k(G)$ of a graph $G$ , introduced by Hager in 1985, is a generalization of classical vertex-connectivity. Let $f(n,k,\ell)$ be the minimal number of edges of a graph $G$ of order $n$ with $τ_k(G)=\ell \ (1\leq \ell\leq n-k)$ . In this paper, we give some exact value or sharp bounds of the parameter $f(n,k,\ell)$ .

preprint2015arXiv

A survey on the generalized connectivity of graphs

The generalized $k$ -connectivity $κ_k(G)$ of a graph $G$ was introduced by Hager before 1985. As its a natural counterpart, we introduced the concept of generalized edge-connectivity $λ_k(G)$ , recently. In this paper we summarize the known results on the generalized connectivity and generalized edge-connectivity. After an introductory section, the paper is then divided into nine sections: the generalized (edge-)connectivity of some graph classes, algorithms and computational complexity, sharp bounds of $κ_k(G)$ and $λ_k(G)$ , graphs with large generalized (edge-)connectivity, Nordhaus-Gaddum-type results, graph operations, extremal problems, and some results for random graphs and multigraphs. It also contains some conjectures and open problems for further studies.

preprint2015arXiv

Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks

The concept of pedant tree-connectivity was introduced by Hager in 1985. For a graph $G=(V,E)$ and a set $S\subseteq V(G)$ of at least two vertices, \emph{an $S$ -Steiner tree} or \emph{a Steiner tree connecting $S$ } (or simply, \emph{an $S$ -tree}) is a such subgraph $T=(V',E')$ of $G$ that is a tree with $S\subseteq V'$ . For an $S$ -Steiner tree, if the degree of each vertex in $S$ is equal to one, then this tree is called a \emph{pedant $S$ -Steiner tree}. Two pedant $S$ -Steiner trees $T$ and $T'$ are said to be \emph{internally disjoint} if $E(T)\cap E(T')=\varnothing$ and $V(T)\cap V(T')=S$ . For $S\subseteq V(G)$ and $|S|\geq 2$ , the \emph{local pedant tree-connectivity} $τ_G(S)$ is the maximum number of internally disjoint pedant $S$ -Steiner trees in $G$ . For an integer $k$ with $2\leq k\leq n$ , \emph{pedant tree $k$ -connectivity} is defined as $τ_k(G)=\min\{τ_G(S)\,|\,S\subseteq V(G),|S|=k\}$ . In this paper, we prove that for any two connected graphs $G$ and $H$ , $τ_3(G\Box H)\geq \min\{3\lfloor\frac{τ_3(G)}{2}\rfloor,3\lfloor\frac{τ_3(H)}{2}\rfloor\}$ . Moreover, the bound is sharp.

preprint2015arXiv

Graphs with large generalized (edge-)connectivity

The generalized $k$ -connectivity $κ_k(G)$ of a graph $G$ , introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized $k$ -edge-connectivity $λ_k(G)$ . In this paper, graphs of order $n$ such that $κ_k(G)=n-\frac{k}{2}-1$ and $λ_k(G)=n-\frac{k}{2}-1$ for even $k$ are characterized.

preprint2015arXiv

Interval minors of complete multipartite graphs

Interval minors of bipartite graphs were introduced by Jacob Fox in the study of Stanley-Wilf limits. Recently, Mohar, Rafiey, Tayfeh-Rezaie and Wu investigated the maximum number of edges in $K_{k,\ell}$ -interval minor free bipartite graphs when $k=2$ and $k=3$ . In this paper, we investigate the maximum number of edges in $K_{k,\ell}$ -interval minor free bipartite graphs for general $k$ and $\ell$ . We also study the maximum number of edges in $K_{\ell_1,\ell_2,\cdots,\ell_t}$ -interval minor free multipartite graphs.

preprint2015arXiv

Monochromatic connectivity and graph products

The concept of monochromatic connectivity was introduced by Caro and Yuster. A path in an edge-colored graph is called a \emph{monochromatic path} if all the edges on the path are colored the same. An edge-coloring of $G$ is a \emph{monochromatic connection coloring} ( $MC$ -coloring, for short) if there is a monochromatic path joining any two vertices in $G$ . The \emph{monochromatic connection number}, denoted by $mc(G)$ , is defined to be the maximum number of colors used in an $MC$ -coloring of a graph $G$ . In this paper, we study the monochromatic connection number on the lexicographical, strong, Cartesian and direct product and present several upper and lower bounds for these products of graphs.

preprint2015arXiv

On the equitable vertex arboricity of complete tripartite graphs

The equitable coloring problem, introduced by Meyer in 1973, has received considerable attention and research. Recently, Wu et al. introduced the concept of equitable (t,k)-tree-coloring, which can be viewed as a generalization of proper equitable t-coloring. The strong equitable vertex k-arboricity of complete bipartite equipartition graphs was investigated in 2013. In this paper, we study the exact value of the strong equitable vertex 3-arboricity of complete equipartition tripartite graphs.

preprint2015arXiv

On the pedant tree-connectivity of graphs

The concept of pedant tree-connectivity was introduced by Hager in 1985. For a graph $G=(V,E)$ and a set $S\subseteq V(G)$ of at least two vertices, \emph{an $S$ -Steiner tree} or \emph{a Steiner tree connecting $S$ } (or simply, \emph{an $S$ -tree}) is a such subgraph $T=(V',E')$ of $G$ that is a tree with $S\subseteq V'$ . For an $S$ -Steiner tree, if the degree of each vertex in $S$ is equal to one, then this tree is called a \emph{pedant $S$ -Steiner tree}. Two pedant $S$ -Steiner trees $T$ and $T'$ are said to be \emph{internally disjoint} if $E(T)\cap E(T')=\varnothing$ and $V(T)\cap V(T')=S$ . For $S\subseteq V(G)$ and $|S|\geq 2$ , the \emph{local pedant-tree connectivity} $τ_G(S)$ is the maximum number of internally disjoint pedant $S$ -Steiner trees in $G$ . For an integer $k$ with $2\leq k\leq n$ , \emph{ $k$ -pedant tree-connectivity} is defined as $τ_k(G)=\min\{τ_G(S)\,|\,S\subseteq V(G),|S|=k\}$ . In this paper, we first study the sharp bounds of pedant tree-connectivity. Next, we obtain the exact value of a threshold graph, and give an upper bound of the pedant-tree $k$ -connectivity of a complete multipartite graph. For a connected graph $G$ , we show that $0\leq τ_k(G)\leq n-k$ , and graphs with $τ_k(G)=n-k,n-k-1,n-k-2,0$ are characterized in this paper. In the end, we obtain the Nordhaus-Guddum type results for pedant tree-connectivity.

preprint2015arXiv

On the regular k-independence number of graphs

The \emph{regular independence number}, introduced by Albertson and Boutin in 1990, is the maximum cardinality of an independent set of $G$ in which all vertices have equal degree in $G$ . Recently, Caro, Hansberg and Pepper introduced the concept of regular $k$ -independence number, which is a natural generalization of the regular independence number. A \emph{ $k$ -independent set} is a set of vertices whose induced subgraph has maximum degree at most $k$ . The \emph{regular $k$ -independence number} of $G$ , denoted by $α_{k-reg}(G)$ , is defined as the maximum cardinality of a $k$ -independent set of $G$ in which all vertices have equal degree in $G$ . In this paper, the exact values of the regular $k$ -independence numbers of some special graphs are obtained. We also get some lower and upper bounds for the regular $k$ -independence number of trees with given diameter, and the lower bounds for the regular $k$ -independence number of line graphs. For a simple graph $G$ of order $n$ , we show that $1\leqα_{k-reg}(G)\leq n$ and characterize the extremal graphs. The Nordhaus-Gaddum-type results for the regular $k$ -independence number of graphs are also obtained.

preprint2015arXiv

Proper connection number and graph products

A path $P$ in an edge-colored graph $G$ is called \emph{a proper path} if no two adjacent edges of $P$ are colored the same, and $G$ is \emph{proper connected} if every two vertices of $G$ are connected by a proper path in $G$ . The \emph{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 study the proper connection number on the lexicographical, strong, Cartesian, and direct product and present several upper bounds for these products of graphs.

preprint2015arXiv

The Steiner diameter of a graph

The Steiner distance of a graph, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph $G$ of order at least $2$ and $S\subseteq V(G)$ , the \emph{Steiner distance} $d(S)$ among the vertices of $S$ is the minimum size among all connected subgraphs whose vertex sets contain $S$ . Let $n,k$ be two integers with $2\leq k\leq n$ . Then the \emph{Steiner $k$ -eccentricity $e_k(v)$ } of a vertex $v$ of $G$ is defined by $e_k(v)=\max \{d(S)\,|\,S\subseteq V(G), \ |S|=k, \ and \ v\in S \}$ . Furthermore, the \emph{Steiner $k$ -diameter} of $G$ is $sdiam_k(G)=\max \{e_k(v)\,|\, v\in V(G)\}$ . In 2011, Chartrand, Okamoto and Zhang showed that $k-1\leq sdiam_k(G)\leq n-1$ . In this paper, graphs with $sdiam_3(G)=2,3,n-1$ are characterized, respectively. We also consider the Nordhaus-Gaddum-type results for the parameter $sdiam_k(G)$ . We determine sharp upper and lower bounds of $sdiam_k(G)+sdiam_k(\overline{G})$ and $sdiam_k(G)\cdot sdiam_k(\overline{G})$ for a graph $G$ of order $n$ . Some graph classes attaining these bounds are also given.

preprint2015arXiv

The vertex-rainbow index of a graph

The $k$ -rainbow index $rx_k(G)$ of a connected graph $G$ was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the $k$ -rainbow index, we introduced the concept of $k$ -vertex-rainbow index $rvx_k(G)$ in this paper. For a graph $G=(V,E)$ and a set $S\subseteq V$ of at least two vertices, \emph{an $S$ -Steiner tree} or \emph{a Steiner tree connecting $S$ } (or simply, \emph{an $S$ -tree}) is a such subgraph $T=(V',E')$ of $G$ that is a tree with $S\subseteq V'$ . For $S\subseteq V(G)$ and $|S|\geq 2$ , an $S$ -Steiner tree $T$ is said to be a \emph{vertex-rainbow $S$ -tree} if the vertices of $V(T)\setminus S$ have distinct colors. For a fixed integer $k$ with $2\leq k\leq n$ , the vertex-coloring $c$ of $G$ is called a \emph{ $k$ -vertex-rainbow coloring} if for every $k$ -subset $S$ of $V(G)$ there exists a vertex-rainbow $S$ -tree. In this case, $G$ is called \emph{vertex-rainbow $k$ -tree-connected}. The minimum number of colors that are needed in a $k$ -vertex-rainbow coloring of $G$ is called the \emph{ $k$ -vertex-rainbow index} of $G$ , denoted by $rvx_k(G)$ . When $k=2$ , $rvx_2(G)$ is nothing new but the vertex-rainbow connection number $rvc(G)$ of $G$ . In this paper, sharp upper and lower bounds of $srvx_k(G)$ are given for a connected graph $G$ of order $n$ ,\ that is, $0\leq srvx_k(G)\leq n-2$ . We obtain the Nordhaus-Guddum results for $3$ -vertex-rainbow index, and show that $rvx_3(G)+rvx_3(\overline{G})=4$ for $n=4$ and $2\leq rvx_3(G)+rvx_3(\overline{G})\leq n-1$ for $n\geq 5$ . Let $t(n,k,\ell)$ denote the minimal size of a connected graph $G$ of order $n$ with $rvx_k(G)\leq \ell$ , where $2\leq \ell\leq n-2$ and $2\leq k\leq n$ . The upper and lower bounds for $t(n,k,\ell)$ are also obtained.

preprint2014arXiv

Additive codes over $GF(4)$ from circulant graphs

In $2006$ , Danielsen and Parker \cite{DP} proved that every self-dual additive code over $GF(4)$ is equivalent to a graph code. So, graph is an important tool for searching (proposed) optimum codes. In this paper, we introduce a new method of searching (proposed) optimum additive codes from circulant graphs.

preprint2014arXiv

Formally self-dual linear binary codes from circulant graphs

In 2002, Tonchev first constructed some linear binary codes defined by the adjacency matrices of undirected graphs. So, graph is an important tool for searching optimum codes. In this paper, we introduce a new method of searching (proposed) optimum formally self-dual linear binary codes from circulant graphs.

preprint2013arXiv

Further hardness results on the generalized connectivity of graphs

The generalized $k$ -connectivity $κ_k(G)$ of a graph $G$ was introduced by Chartrand et al. in 1984, which is a nice generalization of the classical connectivity. Recently, as a natural counterpart, Li et al. proposed the concept of generalized edge-connectivity for a graph. In this paper, we determine the computational complexity of the generalized connectivity and generalized edge-connectivity of a graph. Two conjectures are also proved to be true.

preprint2013arXiv

Lower bounds for the spanning tree numbers of two graph products

For any graph $G$ of order $n$ , the spanning tree packing number \emph{ $STP(G)$ }, is the maximum number of edge-disjoint spanning trees contained in $G$ . In this paper, we obtain some sharp lower bounds for the spanning tree numbers of Cartesian product graphs and Lexicographic product graphs.

preprint2013arXiv

On extremal graphs with at most $\ell$ internally disjoint Steiner trees connecting any n-1 vertices

The concept of maximum local connectivity $\bar κ$ of a graph was introduced by Bollobás. One of the problems about it is to determine the largest number of edges $f(n;\barκ\leq \ell)$ for graphs of order $n$ that have local connectivity at most $\ell$ . We consider a generalization of the above concept and problem. For $S\subseteq V(G)$ and $|S|\geq 2$ , the \emph{generalized local connectivity} $κ(S)$ is the maximum number of internally disjoint trees connecting $S$ in $G$ . The parameter $\barκ_k(G)=max\{κ(S)|S\subseteq V(G),|S|=k\}$ is called the \emph{maximum generalized local connectivity} of $G$ . This paper it to consider the problem of determining the largest number $f(n;\barκ_k\leq \ell)$ of edges for graphs of order $n$ that have maximum generalized local connectivity at most $\ell$ . The exact value of $f(n;\barκ_k\leq \ell)$ for $k=n,n-1$ is determined. For a general $k$ , we construct a graph to obtain a sharp lower bound.

preprint2013arXiv

On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

The problem of determining the smallest number of edges, $h(n;\barκ\geq r)$ , which guarantees that any graph with $n$ vertices and $h(n;\barκ\geq r)$ edges will contain a pair of vertices joined by $r$ internally disjoint paths was posed by Erdös and Gallai. Bollobás considered the problem of determining the largest number of edges $f(n;\barκ\leq \ell)$ for graphs with $n$ vertices and local connectivity at most $\ell$ . One can see that $f(n;\barκ\leq \ell)= h(n;\barκ\geq \ell+1)-1$ . These two problems had received a wide attention of many researchers in the last few decades. In the above problems, only pairs of vertices connected by internally disjoint paths are considered. In this paper, we study the number of internally disjoint Steiner trees connecting sets of vertices with cardinality at least 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.

preprint2013arXiv

The generalized 3-connectivity of Lexicographic product graphs

The generalized $k$ -connectivity $κ_k(G)$ of a graph $G$ , introduced by Chartrand et al., is a natural and nice generalization of the concept of (vertex-)connectivity. In this paper, we prove that for any two connected graphs $G$ and $H$ , $κ_3(G\circ H)\geq κ_3(G)|V(H)|$ . We also give upper bounds for $κ_3(G\Box H)$ and $κ_3(G\circ H)$ . Moreover, all the bounds are sharp.

preprint2013arXiv

The minimal size of a graph with given generalized 3-edge-connectivity

For $S\subseteq V(G)$ and $|S|\geq 2$ , $λ(S)$ is the maximum number of edge-disjoint trees connecting $S$ in $G$ . For an integer $k$ with $2\leq k\leq n$ , the \emph{generalized $k$ -edge-connectivity} $λ_k(G)$ of $G$ is then defined as $λ_k(G)= min\{λ(S) : S\subseteq V(G) \ and \ |S|=k\}$ . It is also clear that when $|S|=2$ , $λ_2(G)$ is nothing new but the standard edge-connectivity $λ(G)$ of $G$ . In this paper, graphs of order $n$ such that $λ_3(G)=n-3$ is characterized. Furthermore, we determine the minimal number of edges of a graph of order $n$ with $λ_3=1,n-3,n-2$ and give a sharp lower bound for $2\leq λ_3\leq n-4$ .

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

Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

Let $G$ be a graph, $S$ be a set of vertices of $G$ , and $λ(S)$ be the maximum number $\ell$ of pairwise edge-disjoint trees $T_1, T_2,..., T_{\ell}$ in $G$ such that $S\subseteq V(T_i)$ for every $1\leq i\leq \ell$ . The generalized $k$ -edge-connectivity $λ_k(G)$ of $G$ is defined as $λ_k(G)= min\{λ(S) | S\subseteq V(G) \ and \ |S|=k\}$ . Thus $λ_2(G)=λ(G)$ . In this paper, we consider the Nordhaus-Gaddum-type results for the parameter $λ_k(G)$ . We determine sharp upper and lower bounds of $λ_k(G)+λ_k(\bar{G})$ and $λ_k(G)... λ_k(\bar{G})$ for a graph $G$ of order $n$ , as well as for a graph of order $n$ and size $m$ . Some graph classes attaining these bounds are also given.

preprint2012arXiv

The strong rainbow vertex-connection of graphs

A vertex-colored graph $G$ is said to be rainbow vertex-connected if every two vertices of $G$ are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph $G$ , denoted by $rvc(G)$ , is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. If for every pair $u, v$ of distinct vertices, $G$ contains a rainbow $u-v$ geodesic, then $G$ is strong rainbow vertex-connected. The minimum number $k$ for which there exists a $k$ -vertex-coloring of $G$ that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of $G$ , denoted by $srvc(G)$ . Observe that $rvc(G)\leq srvc(G)$ for any nontrivial connected graph $G$ . In this paper, sharp upper and lower bounds of $srvc(G)$ are given for a connected graph $G$ of order $n$ , that is, $0\leq srvc(G)\leq n-2$ . Graphs of order $n$ such that $srvc(G)= 1, 2, n-2$ are characterized, respectively. It is also shown that, for each pair $a, b$ of integers with $a\geq 5$ and $b\geq (7a-8)/5$ , there exists a connected graph $G$ such that $rvc(G)=a$ and $srvc(G)=b$ .

Yaping Mao

Research overview

Is this your work?

32 publications

A general approach to deriving diagnosability results of interconnection networks

Some multivariable Rado numbers

Gallai Ramsey number for double stars

Gallai-Ramsey number for the union of stars

Line k-Arboricity in Product Networks

On the Equitable Vertex Arboricity of Graphs

Path connectivity of line graphs

Pendant-tree connectivity of line graphs

The minimal size of graphs with given pendant-tree connectivity

A survey on the generalized connectivity of graphs

Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks

Graphs with large generalized (edge-)connectivity

Interval minors of complete multipartite graphs

Monochromatic connectivity and graph products

On the equitable vertex arboricity of complete tripartite graphs

On the pedant tree-connectivity of graphs

On the regular k-independence number of graphs

Proper connection number and graph products

The Steiner diameter of a graph

The vertex-rainbow index of a graph

Additive codes over $GF(4)$ from circulant graphs

Formally self-dual linear binary codes from circulant graphs

Further hardness results on the generalized connectivity of graphs

Lower bounds for the spanning tree numbers of two graph products

On extremal graphs with at most $\ell$ internally disjoint Steiner trees connecting any n-1 vertices

On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

On the generalized (edge-)connectivity of graphs

The generalized 3-connectivity of Lexicographic product graphs

The minimal size of a graph with given generalized 3-edge-connectivity

Graphs with large generalized 3-connectivity

Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

The strong rainbow vertex-connection of graphs

See the researcher in context

Building this map preview

Yaping Mao

Research overview

Is this your work?

32 publications

A general approach to deriving diagnosability results of interconnection networks

Some multivariable Rado numbers

Gallai Ramsey number for double stars

Gallai-Ramsey number for the union of stars

Line k-Arboricity in Product Networks

On the Equitable Vertex Arboricity of Graphs

Path connectivity of line graphs

Pendant-tree connectivity of line graphs

The minimal size of graphs with given pendant-tree connectivity

A survey on the generalized connectivity of graphs

Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks

Graphs with large generalized (edge-)connectivity

Interval minors of complete multipartite graphs

Monochromatic connectivity and graph products

On the equitable vertex arboricity of complete tripartite graphs

On the pedant tree-connectivity of graphs

On the regular k-independence number of graphs

Proper connection number and graph products

The Steiner diameter of a graph

The vertex-rainbow index of a graph

Additive codes over GF(4)GF(4)GF(4) from circulant graphs

Formally self-dual linear binary codes from circulant graphs

Further hardness results on the generalized connectivity of graphs

Lower bounds for the spanning tree numbers of two graph products

On extremal graphs with at most ℓ\ellℓ internally disjoint Steiner trees connecting any n-1 vertices

On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices

On the generalized (edge-)connectivity of graphs

The generalized 3-connectivity of Lexicographic product graphs

The minimal size of a graph with given generalized 3-edge-connectivity

Graphs with large generalized 3-connectivity

Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs

The strong rainbow vertex-connection of graphs

See the researcher in context

Building this map preview

Additive codes over $GF(4)$ from circulant graphs

On extremal graphs with at most $\ell$ internally disjoint Steiner trees connecting any n-1 vertices