Sign in
Supereulerian digraphs with forbidden induced subdigraphs containing short dipaths
Journal article

Supereulerian digraphs with forbidden induced subdigraphs containing short dipaths

Mansour J. Algefari, Hong-Jian Lai, Juan Liu and Xindong Zhang
Ars combinatoria, Vol.147, pp.289-301
01/10/2019

Abstract

Mathematics Physical Sciences Science & Technology
A digraph D is supereulerian if D has a spanning eulerian subdigraph. We investigate forbidden induced subdigraph conditions for a strong digraph to be supereulerian. Let P-k denote the dipath on k vertices. For k is an element of {2, 3, 4}, we determine the smallest integer h(k) such that if a strong strict digraph D containing a subdigraph H isomorphic to P-k always satisfies vertical bar A(D[V(H)])vertical bar >= h(k), then D is supereulerian. For k >= 5, we show that k(2) - 4k + 8 <= h(k) <= k(k - 1).

Metrics

1 Record Views

Details