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

Abstract

Let $G$ be a graph, $S$ be a set of vertices of $G$, and $\hat{I}»(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\le i\le \ell$. The generalized $k$-edge-connectivity $\hat{I}{»}_k(G)$ of $G$ is defined as $\hat{I}{»}_k(G)=min\{\hat{I}»(S)|S\subseteq V(G)and|S|=k\}$. Thus $\hat{I}{»}_2(G)=\hat{I}»(G)$. In this paper, we consider the Nordhaus-Gaddum-type results for the parameter $\hat{I}{»}_k(G)$. We determine sharp upper and lower bounds of $\hat{I}{»}_k(G)+\hat{I}{»}_k(\bar{G})$ and $\hat{I}{»}_k(G)...\hat{I}{»}_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.

16 pages