Erdős–Pósa theorem and odd cycles In 1962,
Paul Erdős and
Lajos Pósa proved that for every positive integer k there exists a positive integer k' such that for every graph G, either (i) G has k vertex-disjoint (long and/or even) cycles or (ii) there exists a subset X of less than k' vertices of G such that G \ X has no (long and/or even) cycles. This result, known today as the
Erdős–Pósa theorem, cannot be extended to odd cycles. In fact, in 1987 Dejter and
Víctor Neumann-Lara showed that given an integer k > 0, there exists a graph G not possessing disjoint odd cycles such that the number of vertices of G whose removal destroys all odd cycles of G is higher than k.
Ljubljana graph in binary 7-cube In 1993,
Brouwer, Dejter and
Thomassen described an
undirected,
bipartite graph with 112
vertices and 168
edges, (
semi-symmetric, that is
edge-transitive but not
vertex-transitive,
cubic graph with
diameter 8, radius 7,
chromatic number 2,
chromatic index 3, girth 10, with exactly 168 cycles of length 10 and 168 cycles of length 12), known since 2002 as the
Ljubljana graph. They obtained by deleting a copy of the
Hamming code of length 7 from the binary 7-
cube, admits a 3-
factorization into two copies of the
Ljubljana graph. See also. Moreover, relations of this subject with square-blocking subsets and with perfect dominating sets (see below) in hypercubes were addressed by Dejter et al. since 1991 in, (Independently found by F.R.K.Chung. Improving on this,
Marston Conder in 1993 showed that for all n not less than 3 the edges of the
n-cube can be 3-colored in such a way that there is no monochromatic 4-cycle or 6-cycle). (b) Which vertex-transitive induced subgraphs does a hypercube have? The
Dejter graph mentioned above is 6-regular, vertex-transitive and, as suggested, its edges can be 2-colored so that the two resulting monochromatic subgraphs are isomorphic to the
semi-symmetric Ljubljana graph of girth 10. In 1972, I. Z. Bouwer attributed a graph with the mentioned properties of the
Ljubljana graph to
R. M. Foster.
Coxeter graph and Klein graph In 2012, Dejter showed that the 56-vertex Klein cubic graph F{56}B, denoted here Γ', can be obtained from the 28-vertex
Coxeter cubic graph Γ by zipping adequately the squares of the 24 7-cycles of Γ endowed with an orientation obtained by considering Γ as a {\mathcal C}-ultrahomogeneous
digraph, where {\mathcal C} is the collection formed both by the oriented 7-cycles and the 2-arcs that tightly fasten those oriented 7-cycles in Γ. In the process, it is seen that Γ' is a C'-ultrahomogeneous (undirected) graph, where C' is the collection formed by both the 7-cycles and the 1-paths that tightly fasten those 7-cycles in Γ'. This yields an embedding of Γ' into a 3-torus T3 which forms the Klein map of
Coxeter notation (7,3)8. The
dual graph of Γ' in T3 is the
distance-regular Klein quartic graph, with corresponding dual map of
Coxeter notation (3,7)8. Other aspects of this work are also cited in the following pages:
Bitangents of a quartic.
Coxeter graph.
Heawood graph. In 2010, Dejter adapted the notion of {\mathcal C}-ultrahomogeneous graph for
digraphs, and presented a strongly connected \vec{C}_4-ultrahomogeneous oriented graph on 168 vertices and 126 pairwise arc-disjoint 4-cycles with regular indegree and outdegree 3 and no circuits of lengths 2 and 3 by altering a definition of the
Coxeter graph via pencils of ordered lines of the
Fano plane in which pencils were replaced by ordered pencils. The study of
ultrahomogeneous graphs (respectively, digraphs) can be traced back to Sheehan,
Gardiner, Ronse,
Cameron, Gol'fand and Klin, (respectively,
Fraïssé, Lachlan and Woodrow, Cherlin). See also page 77 in
Bondy and
Murty.
Kd-ultrahomogeneous configurations Motivated in 2013 by the study of connected Menger graphs of self-dual 1-configurations (nd)1 expressible as Kd-ultrahomogeneous graphs, Dejter wondered for which values of n such graphs exist, as they would yield the most symmetrical, connected, edge-disjoint unions of n copies of Kd on n vertices in which the roles of vertices and copies of Kd are interchangeable. For d=4, known values of n are: n=13, 21 and n=42, This reference, by Dejter in 2009, yields a graph G for which each isomorphism between two of the 42 copies of K4 or two of the 21 copies of K2,2,2 in G extends to an automorphism of G. While it would be of interest to determine the spectrum and multiplicities of the involved values of n, Dejter mod 17), shown to control attachment of 102 (cuboctahedral) copies of the line graph of the 3-cube to the 102 (tetrahedral) copies of K4, these sharing each triangle with two copies of the cuboctahedral copies and guaranteeing that the distance 3-graph of the
Biggs-Smith graph is the Menger graph of a self-dual 1-configuration (1024)1. This result as digraphs, the
Pappus graph to the
Desargues graph. These applications as well as the reference use the following definition. Given a family C of digraphs, a digraph G is said to be C-ultrahomogeneous if every isomorphism between two induced members of C in G extends to an automorphism of G. In, found that an equivalent condition for the existence of a Z4-Hamilton cycle on the graph of chessknight moves of the usual type (1,2),(resp (1,4)) on the 2nx2n-board is that n is odd larger than 2, (resp. 4). These results are cited by I. Parberry, in relation to the algorithmic aspects of the knight's tour problem. In 1985, Dejter presented a construction technique for Hamilton cycles in the
middle-levels graphs. The existence of such cycles had been conjectured by I. Havel in 1983. and by M. Buck and D. Wiedemann in 1984, (though
Béla Bollobás presented it to Dejter as a
Paul Erdős' conjecture in Jan. 1983) and established by T. Mütze in 2014. That technique was used by Dejter et al. In 2014, Dejter returned to this problem and established a canonical ordering of the vertices in a quotient graph (of each middle-levels graph under the action of a
dihedral group) in one-to-one correspondence with an initial section of a system of numeration (present as sequence A239903 in the
On-Line Encyclopedia of Integer Sequences by
Neil Sloane) composed by restricted growth strings (with the k-th
Catalan number expressed by means of the string 10...0 with k "zeros" and a single "one", as J. Arndt does in page 325 This system of numeration may apply to a dihedral-symmetric restricted version of the middle-levels conjecture. In 1988, Dejter showed that for any positive integer n, all 2-covering graphs of the
complete graph Kn on n vertices can be determined; in addition, he showed that among them there is only one graph that is connected and has a maximal automorphism group, which happens to be bipartite; Dejter also showed that an i-covering graph of Kn is hamiltonian, for i less than 4, and that properly minimal connected non-hamiltonian covering graphs of Kn are obtained which are 4-coverings of Kn; also, non-hamiltonian connected 6-coverings of Kn were constructed in that work. Also in 1988, Dejter showed that if k, n and q are integers such that if 0 <2k<n=2kq\pm1, then the graph generated by the generalized chessknight moves of type (1,2k) on the 2n x 2n-chessboard has Hamilton cycles invariant under quarter turns. For k=1, respectively 2, this extends to the following necessary and sufficient condition for the existence of such cycles: that n is odd and larger than 2k-1. In 1990, Dejter showed that if n and r are integers larger than 0 with n+r larger than 2, then the difference of two concentric square boards A and B with (n + 2r)2 and n2 entries respectively has a chessknight Hamilton cycle invariant under quarter-turns
if and only if r is larger than 2 and either n or r is odd. In 1991, Dejter and
Neumann-Lara showed that given a group Zn acting freely on a graph G, the notion of a voltage graph is applied to the search for Hamilton cycles in G invariant under an action of Zn on G. As an application, for n = 2 and 4, equivalent conditions and lower bounds for chessknight Hamilton cycles containing paths spanning square quadrants and rectangular half-boards were found, respectively.
Coloring the arcs of biregular graphs Recalling that each edge of a graph H has two oppositely oriented arcs, each vertex v of H is identified with the set of arcs (v,e) departing from v along the edges e of H incident to v. Let H be a (λ,μ)-
biregular graph with
bipartition (Y,X), where |Y|=kμ and |X|=kλ, where k<0, λ and μ are integers. In, Dejter considered the problem of assigning, for each edge e=yx of H, a color given by an element of Y, respectively X, to the arc (y,e), respectively (x,e), so that each color is assigned exactly once in the set of arcs departing from each vertex of H. Furthermore, Dejter set such assignment to fulfill a specific bicolor
weight function over a
monotonic subset of Y×X, pointing that this problem applies to the
Design of Experiments for
Industrial Chemistry,
Molecular Biology,
Cellular Neuroscience, etc. An algorithmic construction based on
biregular graphs with bipartitions given by
cyclic-group pairs is also presented in Dejter's work, as well as three essentially different solutions to the Great Circle Challenge Puzzle based on a different
biregular graph whose bipartition is formed by the vertices and 5-cycles of the
Petersen graph. ==Perfect dominating sets==