Italo Jose Dejter

En 1962, Paul Erdős et Lajos Pósa (en) ont prouvé que pour tout entier positif k, il existait un entier positif k' tel que pour chaque graphe G, soit (i) G a k cycles à sommets disjoints (longs et / ou pairs) soit (ii ) il existe un sous-ensemble X à moins de k' sommets de G tel que G \ X n'a pas de cycle (long et / ou pair). Ce résultat, connu aujourd'hui sous le nom de théorème d'Erdős-Pósa, ne peut être étendu aux cycles impairs. En fait, en 1987, Dejter et Víctor Neumann-Lara (en) ont montré que pour un nombre entier k>0, il existe un graphe G ne possédant pas de cycles impairs disjoints tels que le nombre de sommets de G dont la suppression détruit tous les cycles impairs de G est supérieur à k [8].

Graphe de Dejter à partir du graphe de Heawood.

En 1993, Brouwer, Dejter et Thomassen[9] ont décrit un graphe biparti non orienté à 112 sommets et 168 arêtes (semi-symétrique, c'est-à-dire bord à bord mais pas sommet-transitif, craphe cubique de diamètre 8, rayon 7, nombre chromatique 2, indice chromatique 3, circonférence 10, avec exactement 168 cycles de longueur 10 et 168 cycles de longueur 12), connu depuis 2002 sous le nom de graphe de Ljubljana. Ils ont également établi que le graphe de Dejter (en) [10] obtenu en supprimant une copie du code de Hamming de longueur 7 du cube binaire 7, admet une 3-factorisation (en) en deux copies du graphe de Ljubljana[11] - [12] - [13] - [14] - [15] - [16].

En fait, deux questions ont reçu une réponse [9], à savoir:

(a) Combien de couleurs faut-il pour une coloration du n- cube sans 4 cycles monochromes ou 6 cycles? Brouwer, Dejter et Thomassen [9] ont montré que 4 couleurs suffisaient et réglaient ainsi un problème d'Erdős [17] (indépendamment trouvé par F.R.K. Chung[18]. En 1993, Marston Conder [19] montre que, pour tout n supérieur ou égal à 3, les arêtes du n- cube peuvent être 3-colorées de telle sorte qu’il n’y ait pas de cycle d'ordre 4 ni d'ordre 6 monochromatique).

(b) Quels sous-graphes induits par les sommets-transitifs ont un hypercube? Le graphe de Dejter mentionné ci-dessus est 6-régulier, sommet-transitif et, comme suggéré, ses arêtes peuvent être bicolores, de sorte que les deux sous-graphes monochromes résultants soient isomorphes par rapport au graphe de Ljubljana semi-symétrique de circonférence 10.

En 1972, IZ Bouwer[20] a attribué à Ronald M. Foster un graphique présentant les propriétés mentionnées du graphe de Ljubljana .

En 2012, Dejter [21] a montré que le graphe cubique de Klein à 56 sommets F _{56} B [22] peut être obtenu à partir du graphe cubique de Coxeter à 28 sommets [23].

En 2010, Dejter[24] a adapté la notion de graphe ${\displaystyle {\mathcal {C}}}$-ultrahomogène pour les digraphes, et a poursuivi les travaux de Sheehan[25], Gardiner (en)[26], Renaix[27], Cameron[28], Gol'fand et Klin[29] sur l’étude des graphes ultrahomogènes (en), et ceux de Fraïssé[30], Lachlan et Woodrow[31], Cherlin [32] sur les digraphes[33].

Motivé en 2013 [34] par l'étude de graphes de Menger connectés [35] de 1-configurations auto-duelles (n_d)₁ [36] - [37] exprimables en K_d -graphes ultrahomogènes, Dejter s'est demandé pour quelles valeurs de n de tels graphes existent, car ils donneraient les unions les plus symétriques, connectées, arêtes-disjointes de n copies de K_d sur n sommets dans lesquels les rôles de sommets et de copies de K_d sont interchangeables. Pour d = 4, les valeurs connues de n sont: n = 13, 21 [38] - [39] - [40] et n = 42 [41]. Cette référence, par Dejter en 2009, donne un graphe G pour lequel chaque isomorphisme entre deux des 42 copies de K₄ ou deux des 21 copies de K _2,2,2 en G s'étendent à un automorphisme de G.

En 1983, Dejter[42] a obtenu des résultats sur les cycles hamiltoniens sur le graphe de mouvements d'échecs, résultats cités par I. Parberry[43] - [44], en relation avec les aspects algorithmiques du problème du parcours du cavalier.

En 1985, Dejter[45] a présenté une technique de construction pour les cycles de Hamilton dans les graphes de niveaux moyens. Havel avait supposé l'existence de tels cycles en 1983[46] ainsi que M. Buck et D. Wiedemann en 1984[47] (bien que Béla Bollobás l'ait présentée à Dejter sous la forme d'une conjecture de Paul Erdős en janvier 1983) et créé par T. Mütze[48] en 2014. Dejter et ses étudiants ont utilisé cette technique dans de nombreux articles[49] - [50] - [51] - [52] - [53] - [54].

En 2014, Dejter[55] est revenu sur ce problème et a établi un ordre canonique des sommets dans un graphe quotient : la suite A239903 dans l'Encyclopédie en ligne des suites de nombres entiers de Neil Sloane composée de chaînes de croissance restreintes[56] - [57] (avec le k-ème nombre de Catalan exprimé au moyen de la chaîne 10 ... 0 avec k "zéros" et un "un", comme le fait J. Arndt à la page 325) et en rapport avec les couleurs d’appariement lexical de Kierstead-Trotter[58]. Ce système de numération peut s'appliquer à une version restreinte à symétrie dièdre de la conjecture des niveaux intermédiaires.

Dejter poursuit ses travaux en 1988[59] - [60], en 1990[61] et en 1991 avec Neumann-Lara[62].

Dans[63] Dejter utilise la définition suivante : étant donné une famille C de digraphes, un digraphe G est C-ultrahomogène si chaque isomorphisme entre deux éléments induits de C dans G s'étend à un automorphisme de G. Dejter montre qu'exactement 7 graphes cubiques à distance-transitifs parmi les 12 existants possèdent une propriété ultrahomogène particulière par rapport aux circuits orientés qui réalisent la maille qui permet la construction d'un digraphe de Cayley reliés avec des propriétés ultrahomogènes similaires dans lesquelles ces cycles orientés apparaissent « séparés » de manière minimale.

Une chaîne E est une famille dénombrable de graphes imbriqués, chacun d'eux ayant un ensemble dominant efficace. Dejter et Serra fournissent un outil de construction permettant de produire des chaînes E de graphes de Cayley[68].

En 2009, Dejter travaille sur les ensembles dominants quasi parfaits[69].

Les invariants des codes correcteurs d'erreur parfaits ont été traités par Dejter dans[70] - [71], et Dejter et Delgado [72].

Motivé par un problème d'application dans l'architecture informatique, Araujo, Dejter et Horak [73] ont introduit la notion de PDDS (perfect distance-dominating set )dans un graphe, ce qui constitue une généralisation de codes de Lee parfaits[74], et d'autres codes parfaits[75], amorçant ainsi une étude systématique de tels ensembles de sommets.