Italo Jose Dejter

Last updated
Italo Jose Dejter
This is a picture of Italo J. Dejter.jpg
Italo Jose Dejter
BornDecember 17, 1939 (1939-12-17) (age 84)
Bahía Blanca, Argentina
Nationality Argentine American
Alma mater
Known for
Scientific career
Fields
Institutions University of Puerto Rico, Río Piedras Campus
Doctoral advisor Ted Petrie

Italo Jose Dejter (December 17, 1939) is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, (August 1984-February 2018) and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, [1] with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

Contents

Dejter has been a visiting scholar at a number of research institutions, including University of São Paulo, Instituto Nacional de Matemática Pura e Aplicada, Federal University of Rio Grande do Sul, University of Cambridge, National Autonomous University of Mexico, Simon Fraser University, University of Victoria, New York University, University of Illinois at Urbana–Champaign, McMaster University, DIMACS, Autonomous University of Barcelona, Technical University of Denmark, Auburn University, Polytechnic University of Catalonia, Technical University of Madrid, Charles University, Ottawa University and Simón Bolívar University. The sections below describe the relevance of Dejter's work in the research areas mentioned in the first paragraph above, or in the adjacent box.

Algebraic and differential topology

In 1971, Ted Petrie [2] conjectured that if X is a closed, smooth 2n-dimensional homotopy complex projective space that admits a nontrivial smooth action of the circle, and if a function h, mapping X onto the 2n-dimensional complex projective space, is a homotopy equivalence, then h preserves the Pontrjagin classes. In 1975, Dejter [3] proved Petrie's Conjecture for n=3, establishing this way that every closed, smooth, 6-dimensional homotopy complex projective space must be the complex 3-dimensional projective space CP3. Dejter's result is most relevant in view of Petrie's exotic S1-actions on CP3, [4] (apart from the trivial S1-actions on CP3).

Let G be a compact Lie group, let Y be a smooth G-manifold and let F a G-fibre map between G-vector bundles of the same dimension over Y which on each G-fibre is proper and has degree one. Petrie [2] also asked: What are necessary and sufficient conditions for the existence of a smooth G-map properly G-homotopic to F and transverse to the zero-section? Dejter [5] provided both types of conditions, which do not close to a necessary and sufficient condition due to a counterexample. [5]

The main tool involved in establishing the results above by reducing differential-topology problems into algebraic-topology solutions is equivariant algebraic K-theory, where equivariance is understood with respect to the group given by the circle, i.e. the unit circle of the complex plane.

Graph theory

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 [6] 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, [7] 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 [7] also established that the Dejter graph , [8] 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. [9] [10] [11] [12] [13] [14] 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, [12] [13] [14] and . [9]

In fact, two questions were answered in, [7] namely:

(a) How many colors are needed for a coloring of the n-cube without monochromatic 4-cycles or 6-cycles? Brouwer, Dejter and Thomassen [7] showed that 4 colors suffice and thereby settle a problem of Erdős. [15] (Independently found by F.R.K.Chung. [16] Improving on this, Marston Conder [17] 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 [18] attributed a graph with the mentioned properties of the Ljubljana graph to R. M. Foster.

Coxeter graph and Klein graph

In 2012, Dejter [19] showed that the 56-vertex Klein cubic graph F{56}B, [20] 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 -ultrahomogeneous [21] digraph, where 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 [22] 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 [23] adapted the notion of -ultrahomogeneous graph for digraphs, and presented a strongly connected -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, [24] Gardiner, [25] Ronse, [26] Cameron, [27] Gol'fand and Klin, [28] (respectively, Fraïssé, [29] Lachlan and Woodrow, [30] Cherlin [31] ). See also page 77 in Bondy and Murty. [32]

Kd-ultrahomogeneous configurations

Motivated in 2013 [33] by the study of connected Menger graphs [34] of self-dual 1-configurations (nd)1 [35] [36] 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 [37] [38] [39] and n=42, [40] 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 [33] contributes the value of n=102 via the Biggs-Smith association scheme (presented via sextets [41] 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 [33] was obtained as an application of a transformation of distance-transitive graphs into C-UH graphs that yielded the above-mentioned paper [19] and also allowed to confront, [42] as digraphs, the Pappus graph to the Desargues graph.

These applications as well as the reference [43] 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, [43] it is shown that exactly 7 distance-transitive cubic graphs among the existing 12 possess a particular ultrahomogeneous property with respect to oriented cycles realizing the girth that allows the construction of a related Cayley digraph with similar ultrahomogeneous properties in which those oriented cycles appear minimally "pulled apart", or "separated" and whose description is truly beautiful and insightful.

Hamiltonicity in graphs

In 1983, Dejter [44] 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, [45] [46] in relation to the algorithmic aspects of the knight's tour problem.

In 1985, Dejter [47] 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. [48] and by M. Buck and D. Wiedemann in 1984, [49] (though Béla Bollobás presented it to Dejter as a Paul Erdős' conjecture in Jan. 1983) and established by T. Mütze [50] in 2014. That technique was used by Dejter et al. [51] [52] [53] [54] [55] [56]

In 2014, Dejter [57] 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) [58] composed by restricted growth strings [59] [60] (with the k-th Catalan number [61] expressed by means of the string 10...0 with k "zeros" and a single "one", as J. Arndt does in page 325 [60] ) and related to Kierstead-Trotter lexical matching colors. [62] This system of numeration may apply to a dihedral-symmetric restricted version of the middle-levels conjecture.

In 1988, Dejter [63] 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 [64] showed that if k, n and q are integers such that if 0 <2k<n=2kq1, 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 [65] 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 [66] showed that given a group Zn acting freely on a graph G, the notion of a voltage graph [67] 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, [68] 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

A perfect dominating set S of a graph G is a set of vertices of G such that every vertex of G is either in S or is adjacent to exactly one vertex of S. Weichsel [69] showed that a perfect dominating set of the n-cube Qn induces a subgraph of Qn whose components are isomorphic to hypercubes and conjectured that each of these hypercubes has the same dimension. In 1993, Dejter and Weichsel [14] presented the first known cases in which those components have the same dimension but different directions, namely in the 8-cube with components that are 1-cubes formed each by one edge, with the involved edges happening in:

(a) four different directions, as told by Alexander Felzenbaum to Weichsel in Rehovot, Israel, 1988;

(b) eight different directions, which involves the Hamming code of length 7, the Heawood graph, the Fano plane and the Steiner triple system of order 7.

The result of (a) above is immediately extended to perfect dominating sets in cubes of dimensions which are powers of 2 whose components contain each an only edge in half the coordinate direction. On the other hand, in 1991, Dejter and Phelps [70] extended the result of (b) above again to cubes whose dimensions are powers of 2, with components composed each by a unique edge in all coordinate directions. (However, this result is not yet extended to q-ary cubes, as planned by the authors).

The Weichsel conjecture [69] was answered in the affirmative by Östergård and Weakley, [71] who found a perfect dominating set in the 13-cube whose components are 26 4-cubes and 288 isolated vertices. Dejter and Phelps [72] gave a short and elegant proof of this result.

Efficient dominating sets

An E-chain is a countable family of nested graphs, each of which has an efficient dominating set. The Hamming codes in the n-cubes provide a classical example of E-chains. Dejter and Serra [73] gave a constructing tool to produce E-chains of Cayley graphs. This tool was used to construct infinite families of E-chains of Cayley graphs generated by transposition trees of diameter 2 on symmetric groups. These graphs, known as star graphs, [74] had the efficient domination property established by Arumugam and Kala. [75] In contrast, Dejter and O. Tomaiconza [76] showed that there is no efficient dominating set in any Cayley graph generated by a transposition tree of diameter 3. Further study on threaded distance trees and E-sets of star graphs was conducted by Dejter. [77] In 2012, Dejter adapted the results cited above to the case of digraphs. [78] In fact, worst-case efficient dominating sets in digraphs are conceived so that their presence in certain strong digraphs corresponds to that of efficient dominating sets in star graphs. The fact that the star graphs form a so-called dense segmental neighborly E-chain [73] is reflected in a corresponding fact for digraphs.

Quasiperfect dominating sets

In 2009, [79] Dejter defined a vertex subset S of a graph G as a quasiperfect dominating set in G if each vertex v of G not in S is adjacent to dv ∈{1,2} vertices of S, and then investigated perfect and quasiperfect dominating sets in the regular tessellation graph of Schläfli symbol {3,6} and in its toroidal quotient graphs, yielding the classification of their perfect dominating sets and most of their quasiperfect dominating sets S with induced components of the form Kν, where ν ∈{1,2,3} depends only on S.

Coding theory

Invariants of perfect error-correcting codes

Invariants of perfect error-correcting codes were addressed by Dejter in, [80] [81] and Dejter and Delgado [82] in which it is shown that a perfect 1-error-correcting code C is 'foldable' over its kernel via the Steiner triple systems associated to its codewords. The resulting 'folding' produces a graph invariant for C via Pasch configurations and tensors. Moreover, the invariant is complete for Vasil'ev codes [83] of length 15 as viewed by F. Hergert, [84] showing the existence of nonadditive propelinear 1-perfect codes, [85] [86] and allowing to visualize a propelinear code by means of the commutative group formed by its classes mod kernel, as well as to generalize the notion of a propelinear code by extending the involved composition of permutations to a more general group product.

Generalizing perfect Lee codes

Motivated by an application problem in computer architecture, Araujo, Dejter and Horak [87] introduced a notion of perfect distance-dominating set, PDDS, in a graph, constituting a generalization of perfect Lee codes, [88] diameter perfect codes, [89] and other codes and dominating sets, and thus initiating a systematic study of such vertex sets. Some of these sets, related to the motivating application, were constructed, and the non-existence of others was demonstrated. In fact, an extension of the long-standing Golomb-Welch Conjecture, [88] in terms of PDDSs, was stated.

Total perfect codes

According to Dejter and Delgado, [90] given a vertex subset S' of a side Pm of an m x n grid graph G, the perfect dominating sets S in G with S' being the intersection of S with V(Pm) can be determined via an exhaustive algorithm of running time O(2m+n). Extending the algorithm to infinite-grid graphs of width m-1, periodicity makes the binary decision tree prunable into a finite threaded tree, a closed walk of which yields all such sets S. The graphs induced by the complements of such sets S can be codified by arrays of ordered pairs of positive integers, for the growth and determination of which a speedier algorithm exists. A recent characterization of grid graphs having total perfect codes S (i.e. with just 1-cubes as induced components, also called 1-PDDS [87] and DPL(2,4) [89] ), due to Klostermeyer and Goldwasser, [91] allowed Dejter and Delgado [90] to show that these sets S are restrictions of only one total perfect code S1 in the planar integer lattice graph, with the extra-bonus that the complement of S1 yields an aperiodic tiling, like the Penrose tiling. In contrast, the parallel, horizontal, total perfect codes in the planar integer lattice graph are in 1-1 correspondence with the doubly infinite {0,1}-sequences.

Dejter showed [92] that there is an uncountable number of parallel total perfect codes in the planar integer lattice graph L; in contrast, there is just one 1-perfect code, and just one total perfect code in L, the latter code restricting to total perfect codes of rectangular grid graphs (which yields an asymmetric, Penrose, tiling of the plane); in particular, Dejter characterized all cycle products Cm x Cn containing parallel total perfect codes, and the d-perfect and total perfect code partitions of L and Cm x Cn, the former having as quotient graph the undirected Cayley graphs of the cyclic group of order 2d2+2d+1 with generator set {1,2d2}.

In 2012, Araujo and Dejter [93] made a conjecturing contribution to the classification of lattice-like total perfect codes in n-dimensional integer lattices via pairs (G,F) formed by abelian groups G and homomorphisms F from Zn onto G, in the line of the Araujo-Dejter-Horak work cited above. [87]

Combinatorial designs

Since 1994, Dejter intervened in several projects in Combinatorial Designs initially suggested by Alexander Rosa, C. C. Lindner and C. A. Rodger and also worked upon with E. Mendelsohn, F. Franek, D. Pike, P. A. Adams, E. J. Billington, D. G. Hoffman, M. Meszka and others, which produced results in the following subjects:

Invariants for 2-factorization and cycle systems, [94]

Triangles in 2-factorizations, [95] [96]

Number of 4-cycles in 2-factorizations of complete graphs, [97]

Directed almost resolvable Hamilton-Waterloo problem, [98]

Number of 4-cycles in 2-factorizations of K2n minus a 1-factor, [99]

Almost resolvable 4-cycle systems, [100]

Critical sets for the completion of Latin squares [101]

Almost resolvable maximum packings of complete graphs with 4-cycles. [102]

Related Research Articles

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Symmetric graph</span> Graph in which all ordered pairs of linked nodes are automorphic

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism

<span class="mw-page-title-main">Desargues graph</span> Distance-transitive cubic graph with 20 nodes and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

<span class="mw-page-title-main">Wheel graph</span> Cycle graph plus universal vertex

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n – 1)-gonal pyramid. Some authors write Wn to denote a wheel graph with n vertices ; other authors instead use Wn to denote a wheel graph with n + 1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length n. The rest of this article uses the former notation.

<span class="mw-page-title-main">Coxeter graph</span> Type of graph

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.

<span class="mw-page-title-main">Claw-free graph</span> Graph without four-vertex star subgraphs

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

<span class="mw-page-title-main">Hypohamiltonian graph</span> Type of graph in graph theory

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number of vertices. Fibonacci cubes were first explicitly defined in Hsu (1993) in the context of interconnection topologies for connecting parallel or distributed systems. They have also been applied in chemical graph theory.

In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.

The connected 3-regular (cubic) simple graphs are listed for small vertex numbers.

In graph theory, a partial cube is a graph that is an isometric subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

<span class="mw-page-title-main">Dejter graph</span>

In the mathematical field of graph theory, the Dejter graph is a 6-regular graph with 112 vertices and 336 edges. The Dejter graph is obtained by deleting a copy of the Hamming code of length 7 from the binary 7-cube.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal, who first posed it as an open problem in a paper from 1977.

In graph theory, an eternal dominating set for a graph G = (V, E) is a subset D of V such that D is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex). The set D must be such that for any infinite sequence of attacks occurring sequentially at vertices, the set D can be modified by moving a guard from an adjacent vertex to the attacked vertex, provided the attacked vertex has no guard on it at the time it is attacked. The configuration of guards after each attack must induce a dominating set. The eternal domination number, γ∞(G), is the minimum number of vertices possible in the initial set D. For example, the eternal domination number of the cycle on five vertices is two.

In the mathematical field of graph theory, a word-representable graph is a graph that can be characterized by a word whose entries alternate in a prescribed way. In particular, if the vertex set of the graph is V, one should be able to choose a word w over the alphabet V such that letters a and b alternate in w if and only if the pair ab is an edge in the graph. For example, the cycle graph labeled by a, b, c and d in clock-wise direction is word-representable because it can be represented by abdacdbc: the pairs ab, bc, cd and ad alternate, but the pairs ac and bd do not.

References

  1. ↑ Italo Jose Dejter at the Mathematics Genealogy Project
  2. 1 2 Petrie T. "Smooth S1-actions on homotopy complex projective spaces and related topics", Bull. Amer. Math. Soc. 78 (1972) 105–153
  3. ↑ Dejter I. J. "Smooth S1-manifolds in the homotopy type of CP3 ", Mich. Math. Jour. 23 (1976), 83–95
  4. ↑ Petrie T. "Exotic S1-actions on CP3 and related topics", Invent. Math. 17 (1972), 317–327.
  5. 1 2 Dejter I. J. "G-Transversality to CP^n", Springer-Verlag Lecture Notes in Mathematics, 652 (1976), 222–239
  6. ↑ Dejter I. J.; Neumann-Lara V. "Unboundedness for odd cyclic transversality", Coll. Math. Soc. J. Bolyai, 52 (1987), 195–203
  7. 1 2 3 4 Brouwer A. E.; Dejter I. J.; Thomassen C. "Highly symmetric subgraphs of hypercubes", J. Algebraic Combinat. 2, 22-25, 1993
  8. ↑ Klin M.; Lauri J.; Ziv-Av M. "Links between two semisymmetric graphs on 112 vertices through the lens of association schemes", Jour. Symbolic Comput., 47–10, 2012, 1175–1191.
  9. 1 2 Borges J.; Dejter I. J. "On perfect dominating sets in hypercubes and their complements", J. Combin. Math. Combin. Comput. 20 (1996), 161-173
  10. ↑ Dejter I. J. "On symmetric subgraphs of the 7-cube: an overview", Discrete Math. 124 (1994) 55–66
  11. ↑ Dejter I. J. "Symmetry of factors of the 7-cube Hamming shell", J. Combin. Des. 5 (1997), 301–309
  12. 1 2 Dejter I. J.; Guan P. "Square-blocking edge subsets in hypercubes and vertex avoidance", Graph theory, combinatorics, algorithms, and applications (San Francisco, CA, 1989), 162–174, SIAM, Philadelphia, PA, 1991
  13. 1 2 Dejter I. J.; Pujol J. "Perfect domination and symmetry in hypercubes", Proceedings of the Twenty-Sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995). Congr. Numer. 111 (1995), 18–32
  14. 1 2 3 Dejter I. J.; Weichsel P. M. "Twisted perfect dominating subgraphs of hypercubes", Proceedings of the Twenty-Fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993). Congr. Numer. 94 (1993), 67–78
  15. ↑ Erdős P. "Some of my favourite unsolved problems", in: A Tribute to Paul Erdős (A. Baker, B. Bollobás & A. Hajnal, eds.), Cambridge Univ. Press, Cambridge. 1990, 467–478.
  16. ↑ Chung F. R. K. "Subgraphs of a hypercube containing no small even cycles", 1. Journal of Graph Theory, 16 (1992) 273–286.
  17. ↑ Conder M. "Hexagon-free subgraphs of hypercubes", Journal of Graph Theory, 17–4 (1993), 477–479.
  18. ↑ Bouwer I. Z. "On edge but not vertex transitive regular graphs", J. Combin. Theory (B) 12 (1972), 32-40.
  19. 1 2 Dejter I. J. From the Coxeter graph to the Klein graph, Journal of Graph Theory, 70-1 (2012), 1–9.
  20. ↑ Weisstein, Eric W. "Cubic symmetric graph." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/CubicSymmetricGraph.html
  21. ↑ Isaksen D. C.; Jankowski C.; Proctor S. " "Archived copy" (PDF). Archived from the original on 2014-03-23. Retrieved 2016-09-13.{{cite web}}: CS1 maint: archived copy as title (link) CS1 maint: bot: original URL status unknown (link)", Ars Combinatoria, 82 (2007), 83–96.
  22. ↑ Schulte E.; Wills J. M. "A Polyhedral Realization of Felix Klein's Map {3, 7}8 on a Riemann Surface of Genus 3", J. London Math. Soc., s2-32 (1985), 539–547.
  23. ↑ Dejter I. J. "On a 4-ultrahomogeneous oriented graph", Discrete Mathematics, (2010), 1389–1391.
  24. ↑ Sheehan J. "Smoothly embeddable subgraphs", J. London Math. Soc., s2-9 (1974), 212–218.
  25. ↑ , Gardiner A. "Homogeneous graphs", Journal of Combinatorial Theory, Series B, 20 (1976), 94–102.
  26. ↑ Ronse C. "On homogeneous graphs", J. London Math. Soc., s2-17 (1978), 375–379.
  27. ↑ Cameron P. J. "6-transitive graphs", J. Combin. Theory Ser. B 28 (1980), 168–179.
  28. ↑ Gol'fand Ja. Ju.; Klin M. H. "On k-homogeneous graphs", Algorithmic studies in combinatorics (Russian), 186 (1978), 76–85.
  29. ↑ Fraïssé R. "Sur l'extension aux relations de quelques proprietes des ordres", Ann. Sci. Ecole Norm. Sup. 71 (1954), 363–388.
  30. ↑ A. H. Lachlan A. H.; Woodrow R. "Countable ultrahomogeneous undirected graphs", Trans. Amer. Math. Soc. 262 (1980), 51–94.
  31. ↑ Cherlin G. L. "The classification of countable homogeneous directed graphs and countable homogeneous n-tournaments", Memoirs Amer. Math. Soc., vol. 131, number 612, Providence RI, January 1988.
  32. ↑ Bondy A.; Murty U.S.R.; Graph Theory, Springer-Verlag, 2008.
  33. 1 2 3 Dejter I. J. "On a K4-UH self-dual 1-configuration (10241, J. Combin. Math. Combi. Comput. 95 (2015), 127-146 (arXiv:1002:0588) [math.CO].
  34. ↑ Coxeter H. S. M. "Self-dual configurations and regular graphs", Bull. Amer. Math. Soc., 56 (1950), 413-455; http://www.ams.org/journals/bull/1950-56-05/S0002-9904-1950-09407-5/S0002-9904-1950-09407-5.pdf.
  35. ↑ Gropp, Harald (1994). "On symmetric spatial configurations". Discrete Mathematics. 125 (1–3): 201–209. doi: 10.1016/0012-365X(94)90161-9 .
  36. ↑ Colbourn C. J.; Dinitz J. H. "The CRC Handbook of Combinatorial Designs", CRC, 1996.
  37. ↑ Grünbaum B. "Configurations of Points and Lines", Grad. Texts in Math. 103, Amer. Math. Soc, Providence R.I., 2009.
  38. ↑ Grünbaum B.; Rigby J. F. "The real configuration (214)", Jour. London Math. Soc., Sec. Ser. 41(2) (1990), 336–346.
  39. ↑ Pisanski T.; Servatius B. "Configurations from a Graphical Viewpoint", Birkhäuser, 2013.
  40. ↑ Dejter I. J. "On a {K4,K2,2,2}-ultrahomogeneous graph", Australasian Journal of Combinatorics, 44 (2009), 63-76.
  41. ↑ Biggs N. L.; Hoare M. J. "The sextet construction for cubic graphs", Combinatorica, 3 (1983), 153-165.
  42. ↑ Dejter I. J. "Pappus-Desargues digraph confrontation", Jour. Combin. Math. Combin. Comput", 95 (2014), 101-111 (arXiv:0904:1096) [math.CO]
  43. 1 2 Dejter I. J. "Orienting and separating distance-transitive graphs", Ars Mathematica Contemporanea, 5 (2012) 221-236
  44. ↑ I. J. Dejter "Equivalent conditions for Euler problem on Z4-Hamilton cycles", Ars Combinatoria, 16B, (1983), 285-295
  45. ↑ "Knight's Tours". larc.unt.edu. Archived from the original on 2014-01-16.
  46. ↑ I. Parberry "An efficient algorithm for the Knight�s tour problem", Discrete Applied Mathematics, 73, (1997), 251-260
  47. ↑ Dejter I. J. "Hamilton cycles and quotients of bipartite graphs", in Y. Alavi et al., eds., Graph Theory and its Appl. to Alg. and Comp. Sci., Wyley, 1985, 189-199.
  48. ↑ Havel I. "Semipaths in directed cubes", in: M. Fiedler (Ed.), Graphs and other Combinatorial Topics, Teubner-Texte Math., Teubner, Leipzig, 1983, pp. 101–108.
  49. ↑ Buck M. and Wiedemann D. "Gray codes with restricted density", Discrete Math., 48 (1984), 163-–171.
  50. ↑ Mütze T. "Proof of the middle-levels conjecture", Proc. Lond. Math. Soc (3) 112 (2016), 677-713 (Arxiv 1404:4442
  51. ↑ Dejter I. J. "Stratification for hamiltonicity", Congressus Numeranium, 47 (1985) 265-272.
  52. ↑ Dejter I. J.; Quintana J. "Long cycles in revolving door graphs", Congressus Numerantium, 60 (1987), 163-168.
  53. ↑ Dejter I. J.; Cordova J; Quintana J. "Two Hamilton cycles in bipartite reflective Kneser graphs", Discrete Math. 72 (1988) 63-70.
  54. ↑ Dejter I. J.; Quintana J. "On an extension of a conjecture of I. Havel", in Y. Alavi et al. eds., Graph Theory, Combin. and Appl., J. Wiley 1991, vol I, 327-342.
  55. ↑ Dejter I. J.; Cedeno W.; Jauregui V. "Frucht diagrams, Boolean graphs and Hamilton cycles", Scientia, Ser. A, Math. Sci., 5 (1992/93) 21-37.
  56. ↑ Dejter I. J.; Cedeno W.; Jauregui V. "A note on F-diagrams, Boolean graphs and Hamilton cycles", Discrete Math. 114 (1993), 131-135.
  57. ↑ Dejter I. J. "Ordering the Levels Lk and Lk+1 of B2k+1".
  58. ↑ Sloane, N. J. A. (ed.). "SequenceA239903". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.
  59. ↑ Ruskey F. "Simple combinatorial Gray codes constructed by reversing sublists", Lecture Notes in Computer Science, 762 (1993) 201-208.
  60. 1 2 Arndt J., Matters Computational: Ideas, Algorithms, Source Code, Springer, 2011.
  61. ↑ Sloane, N. J. A. (ed.). "SequenceA000108". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.
  62. ↑ Kierstead H. A.; Trotter W. T. "Explicit matchings in the middle two levels of the boolean lattice", Order 5 (1988), 163-171.
  63. ↑ I. J. Dejter "Minimal hamiltonian and nonhamiltonian covering graphs of Kn", Ars Combinatoria, 25-C, (1988), 63-71.
  64. ↑ I. J. Dejter "(1,2k)-Chessknight Hamilton cycles invariant under quarter turns", Scientia, Ser. A, Math. Sci., 2 (1988), 39-51.
  65. ↑ I. J. Dejter "Quarter-turns and Hamilton cycles for annular chessknight graphs", Scientia, Ser. A, Math. Sci., 4 (1990/91), 21-29.
  66. ↑ I. J. Dejter and V. Neumann-Lara "Voltage graphs and Hamilton cycles", in V. Kulli ed., Advances in Graph Theory, Vishwa Int. Publ., Gulbarga, India, 1991, 141-153.
  67. ↑ J.L. Gross and T.W. Tucker "Topological Graph Theory" Wiley, New York (1987).
  68. ↑ I. J. Dejter "On Coloring the Arcs of Biregular Graphs", Discrete Applied Mathematics 284 (2020) 489--498
  69. 1 2 Weichsel P. "Dominating sets in n-cubes", Jour. of Graph Theory, 18 (1994), 479-488
  70. ↑ Dejter. I. J.; Phelps K. T. "On perfect domination of binary cubes", preprint.
  71. ↑ Östergård P.; Weakley W. D. "Constructing covering codes with given automorphisms", Des. Codes Cryptogr. 16 (1999), 65-73
  72. ↑ Dejter I. J.; Phelps K. T. "Ternary Hamming and Binary Perfect Covering Codes", in: A. Barg and S. Litsyn, eds., Codes and Association Schemes, DIMACS Ser. Discrete Math. Theoret. Comput Sci. 56, Amer. Math. Soc., Providence, RI, 111--113"
  73. 1 2 Dejter I. J.; Serra O. "Efficient dominating sets in Cayley graphs", Discrete Appl. Math., 129 (2003), no. 2-3, 319-328.
  74. ↑ Akers S.B.; Krishnamurthy B. "A group theoretic model for symmetric interconnection networks", IEEE Trans. Comput., 38 (1989), 555-565.
  75. ↑ Arumugam S.; Kala R. "Domination Parameters of Star Graphs", Ars Combinatoria, 44 (1996) 93-96
  76. ↑ Dejter I. J.; Tomaiconza O. "Nonexistence of Efficient Dominating Sets in the Cayley Graphs Generated by Transposition Trees of Diameter 3", Discrete Appl. Math., 232 (2017), 116-124.
  77. ↑ Dejter I. J. "Star graphs: threaded distance trees and E-sets", J. Combin. Math. Combin. Comput. 77 (2011), 3-16.
  78. ↑ Dejter I. J. "Worst-case efficient dominating sets in digraphs", Discrete Applied Mathematics, 161 (2013) 944–952. First Online DOI 10.1016/j.dam.2012.11.016
  79. ↑ Dejter I. J. "Quasiperfect domination in triangular lattices", Discussiones Mathematicae Graph Theory, 29(1) (2009), 179-198.
  80. ↑ Dejter I. J. "SQS-graphs of extended 1-perfect codes", Congressus Numerantium, 193 (2008), 175-194.
  81. ↑ Dejter I. J. "STS-Graphical invariant for perfect codes", J. Combin. Math. Combin. Comput., 36 (2001), 65-82.
  82. ↑ Dejter I. J.; Delgado A. A. "STS-Graphs of perfect codes mod kernel", Discrete Mathematics, 253 (2005), 31-47.
  83. ↑ Vasil'ev Y. L. "On nongroup close-packed codes", Problem of Cybernetics, 8 (1962) 375-378 (in Russian).
  84. ↑ Hergert F, "The equivalence classes of the Vasil'ev codes of length 15", Springer-Verlag Lecture Notes 969 (1982) 176-186.
  85. ↑ Rifà J.; Basart J. M.; Huguet L. "On completely regular propelinear codes" AAECC (1988) 341-355
  86. ↑ Rifà J.; Pujol J. "Translation invariant propelinear codes, Transact. Info. Th., IEEE, 43(1997) 590-598.
  87. 1 2 3 Araujo C; Dejter I. J.; Horak P. "generalization of Lee codes", Designs, Codes and Cryptography, 70 77-90 (2014).
  88. 1 2 Golomb S. W.; Welsh L. R. "Perfect codes in the Lee metric and the packing of polyominoes", SIAM J. Applied Math. 18 (1970), 302-317.
  89. 1 2 Horak, P.; AlBdaiwi, B.F "Diameter Perfect Lee Codes", IEEE Transactions on Information Theory 58-8 (2012), 5490-5499.
  90. 1 2 Dejter I. J.; Delgado A. A. "Perfect domination in rectangular grid graphs", J. Combin. Math. Combin. Comput., 70 (2009), 177-196.
  91. ↑ Klostermeyer W. F.; Goldwasser J. L. "Total Perfect Codes in Grid Graphs", Bull. Inst. Comb. Appl., 46(2006) 61-68.
  92. ↑ Dejter I. J. "Perfect domination in regular grid graphs", Austral. Jour. Combin., 42 (2008), 99-114
  93. ↑ Dejter I. J.; Araujo C. "Lattice-like total perfect codes", Discussiones Mathematicae Graph Theory, 34 (2014) 57–74, doi:10.7151/dmgt.1715.
  94. ↑ Dejter I. J.; Rivera-Vega P. I.; Rosa Alexander "Invariants for 2-factorizations and cycle systems", J. Combin. Math. Combin. Comput., 16 (1994), 129-152.
  95. ↑ Dejter I. J.; Franek F.; Mendelsohn E.; Rosa Alexander "Triangles in 2-factorizations", Journal of Graph Theory, 26 (1997) 83-94.
  96. ↑ Dejter I. J.; Franek F.; Rosa Alexander "A Completion conjecture for Kirkman triple systems", Utilitas Mathematica, 50 (1996) 97-102
  97. ↑ Dejter I. J.; Lindner C. C.; Rosa Alexander "The number of 4-cycles in 2-factorizations of Kn", J. Combin. Math. Combin. Comput., 28 (1998), 101-112.
  98. ↑ Dejter I. J.; Pike D.; Rodger C. A. "The directed almost resolvable Hamilton-Waterloo problem", Australas. J. Combin., 18 (1998), 201-208.
  99. ↑ Adams P. A., Billington E. J.; Lindner C. C. "The number of 4-cycles in 2-factorizations of K2n minus a 1-factor}, Discrete Math., 220 (2000), no.1-3, 1-11.
  100. ↑ Dejter I. J.; Lindner C. C.; Rodger C. A.; Meszka M. "Almost resolvable 4-cycle systems", J. Combin. Math. Combin. Comput., 63 (2007), 173-182.
  101. ↑ Horak P.; Dejter I. J. "Completing Latin squares: critical sets, II", Jour. Combin. Des., 15 (2007), 177-83.
  102. ↑ Billington E. J.; Dejter I. J.; Hoffman D. G.; Lindner C. C. "Almost resolvable maximum packings of complete graphs with 4-cycles", Graphs and Combinatorics, 27 (2011), no. 2, 161-170
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.