Open AccessTwo {4,n-3}-isomorphic n-vertex digraphs are hereditarily isomorphic
Author(s) -
Youssef Boudabbous
Publication year - 2019
Publication title -
filomat
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.449
H-Index - 34
eISSN - 2406-0933
pISSN - 0354-5180
DOI - 10.2298/fil1913307b
Subject(s) - mathematics , combinatorics , vertex (graph theory) , corollary , discrete mathematics , graph
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.