Abstract
A subgraph H= (V, E′) of a graph G= (V, E) is non-separating if G\ E′, that is, the graph obtained from G by deleting the edges in E′, is connected. Analogously we say that a subdigraph X= (V, A′) of a digraph D= (V, A) is non-separating if D\ A′ is strongly connected. We study non-separating spanning trees and out-branchings in digraphs of independence number 2. Our main results are that every 2-arc-strong digraph D of independence number α(D) = 2 and minimum in-degree at least 5 and every 2-arc-strong oriented graph with α(D) = 2 and minimum in-degree at least 3 has a non-separating out-branching and minimum in-degree 2 is not enough. We also prove a number of other results, including that every 2-arc-strong digraph D with α(D) ≤ 2 and at least 14 vertices has a non-separating spanning tree and that every graph G with δ(G) ≥ 4 and α(G) = 2 has a non-separating Hamiltonian path.
| Originalsprog | Engelsk |
|---|---|
| Artikelnummer | 187 |
| Tidsskrift | Graphs and Combinatorics |
| Vol/bind | 38 |
| Udgave nummer | 6 |
| ISSN | 0911-0119 |
| DOI | |
| Status | Udgivet - dec. 2022 |
Bibliografisk note
Funding Information:J. Bang-Jensen: Part of this work was done while the author was visiting LIRMM, Université de Montpellier as well as INRIA Sophia Antipolis. Hospitality and financial support by both is gratefully acknowledged. Ce travail a bénéficié d’une aide du gouvernement français, gérée par l’Agence Nationale de la Recherche au titre du projet Investissements d’Avenir UCAJEDI portant la référence no ANR-15-IDEX-01. S. Bessy: financial suports: PICS CNRS DISCO and ANR DIGRAPHS n.194718.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.