×

On the edge independence number of a regular graph with large edge connectivity. (English) Zbl 0745.05023

Combinatorial mathematics, Proc. 3rd Int. Conf., New York/ NY (USA) 1985, Ann. N. Y. Acad. Sci. 555, 94-102 (1989).
[For the entire collection see Zbl 0699.00014.]
Let \(G\) be an \(r\)-regular, \((r-2)\)-edge-connected graph, \(r\geq 3\), of order \(p\) and let \(\ell\) be an integer such that \(0\leq \ell \leq \lfloor {p\over 2}\rfloor\). If \(p\) is even and \(p<2(\ell +1)(r \lfloor {r\over 2}\rfloor + r-1)\), then there are at least \((p-2\ell)/2\) independent edges in \(G\). Similar result for \(p\) odd is given and it is proved that for \(r\geq 4\) the bounds are best possible.

MSC:

05C35 Extremal problems in graph theory
05C40 Connectivity

Citations:

Zbl 0699.00014
PDFBibTeX XMLCite