Hardness results on generalized connectivity - Mathematics > CombinatoricsReport as inadecuate




Hardness results on generalized connectivity - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Let $G$ be a nontrivial connected graph of order $n$ and let $k$ be aninteger with $2\leq k\leq n$. For a set $S$ of $k$ vertices of $G$, let $\kappaS$ denote the maximum number $\ell$ of edge-disjoint trees$T 1,T 2,

.,T \ell$ in $G$ such that $VT i\cap VT j=S$ for every pair$i,j$ of distinct integers with $1\leq i,j\leq \ell$. A collection$\{T 1,T 2,

.,T \ell\}$ of trees in $G$ with this property is called aninternally disjoint set of trees connecting $S$. Chartrand et al. generalizedthe concept of connectivity as follows: The $k$-$connectivity$, denoted by$\kappa kG$, of $G$ is defined by $\kappa kG=$min$\{\kappaS\}$, where theminimum is taken over all $k$-subsets $S$ of $VG$. Thus$\kappa 2G=\kappaG$, where $\kappaG$ is the connectivity of $G$, forwhich there are polynomial-time algorithms to solve it. This paper mainly focuson the complexity of the generalized connectivity. At first, we obtain that fortwo fixed positive integers $k 1$ and $k 2$, given a graph $G$ and a$k 1$-subset $S$ of $VG$, the problem of deciding whether $G$ contains $k 2$internally disjoint trees connecting $S$ can be solved by a polynomial-timealgorithm. Then, we show that when $k 1$ is a fixed integer of at least 4, but$k 2$ is not a fixed integer, the problem turns out to be NP-complete. On theother hand, when $k 2$ is a fixed integer of at least 2, but $k 1$ is not afixed integer, we show that the problem also becomes NP-complete. Finally wegive some open problems.



Author: Shasha Li, Xueliang Li

Source: https://arxiv.org/







Related documents