Two {4,n-3}-isomorphic n-vertex digraphs are hereditarily isomorphic - Université de La Réunion
Journal Articles Filomat Year : 2019

Two {4,n-3}-isomorphic n-vertex digraphs are hereditarily isomorphic

Abstract

Let D and D' be two digraphs with the same vertex set V, and let F be a set of positive integers. The digraphs D and D' are hereditarily isomorphic whenever the (induced) subdigraphs D[X] and D'[X] are isomorphic for each nonempty vertex subset X. They are F-isomorphic if the subdigraphs D[X] and D'[X] are isomorphic for each vertex subset X with |X|€ F. In this paper, we prove that if D and D' are two {4,n-3}-isomorphic n-vertex digraphs, where n >= 9, then D and D0 are hereditarily isomorphic. As a corollary, we obtain that given integers k and n with 4 <= k <= n-6, if D and D' are two {n-k}-isomorphic n-vertex digraphs, then D and D' are hereditarily isomorphic.
nema

Dates and versions

hal-04555487 , version 1 (23-04-2024)

Identifiers

Cite

Youssef Boudabbous. Two {4,n-3}-isomorphic n-vertex digraphs are hereditarily isomorphic. Filomat, 2019, 33 (13), pp.4307-4325. ⟨10.2298/FIL1913307B⟩. ⟨hal-04555487⟩
19 View
0 Download

Altmetric

Share

More