Some open problems

This is a set of open problems, mostly from graph theory. Please email me if you wish to have some more background information on any of these problems.

  1. With S. Fiorini. Let S be a closed surface (orientable or non-orientable) and let H be a graph. For k ³ 4 a k-embedding of H on S is a 2-cell embedding of H on S in which every face except one is bounded by a 3-cycle, the exceptional face being bounded by a k-cycle. Clearly, if G triangulates S then, for any vertex v of G with deg(v) ³ 4, G-v has a deg(v)-embedding on S. Is the converse true? That is, if G has the property that, for any vertex v with degree at least 4, G-v has a deg(v)-embedding, then does G triangulate S? Fiorini and Lauri have proved that this is true when S is the sphere (that is, G is maximal planar). This proof makes essential use of Kuratowski's Theorem.
  2. With K. Asciak. The reconstruction number rn(G) of a graph G is the minimum number of vertex-deleted subgraphs which are sufficient to reconstruct G uniquely up to isomorphism. Myrvold and Molina have proved that if G is disconnected and not all its components are isomorphic, then rn(G) = 3. So we assume here that G is made up of a disjoint union of copies of a graph H and we assume also that H has c vertices. Myrvold has observed that if H = Kc, the complete graph on c vertices, then rn(G) = c+2. Asciak has proved the converse, and in fact that if rn(G) ³ c+1 then H = Kc. This means that there is no disconnected graph with all components isomorphic and having c vertices and such that rn(G) = c+1. The problem therefore is this: Let G = ÈH with |V(H)| = c. Determine the number g = g(c) such that if rn(G) ³ g then G is a union of copies of Kc but there is such a G, with H ¹ Kc, such that rn(G) = g-1. The above result shows that g £ c. Also: Is there a constant g0 such that if G is a disconnected graph with rn(G) ³ g0 then G is a union of complete graphs?
  3. With K. Asciak. Asciak has also shown that if G is an r-regular graph (that is, all vertices have degree r) and rn(G) = r+3, then G is a union of copies of the complete graph Kr+1. Problem: Determine the number f = f(r) such that, given an r-regular graph G, if rn(G) ³ f then G is a union of copies of Kr+1, but there exists a different r-regular graph G with rn(G) = f-1. Asciak's result shows that f £ r+2. Is the problem made easier if posed for vertex-transitive graphs?
  4. Asciak. The edge-reconstruction number ern(G) of a graph is analogously defined. Asciak has shown that if G is an r-regular graph then ern(G) £ r+2, but he conjectures: If G is a regular graph then ern(G) £ 2. Is the problem made easier if we assume that G is vertex-transitive, or edge-transitive, or arc-transitive?
  5. With C.Dandria. A graph H is said to be a topological minor of G if G contains a subgraph which is a subdivision of H (that is, obtained by inserting vertices of degree 2 in the edges of H). G is said to be H-critical if it contains a subdivision of H but, for all v Î V(G), G-v does not. Let dT(H) be the largest possible minimum degree of a graph G which is H-critical. Certainly, dT(H) exists for any H and (by a result of Szemerédi) is at most cm2logm +1, although the value of dT(H) would seem to be much less than this in fact. It is easy to prove that dT(K4) = 3. Mitchem has shown that dT(K2,3) also equals 3, and Fiorini has shown that dT(K3,3) = 4. Dandria has shown that dT(K2,4) = 4. She asks: Are there constants c, t0 such that, for t > t0, dT(K2,t) £ c. She also asks: What is dT(K5)? In general, find the value of, or bounds for, dT(Kn).
  6. M.A. Francalanza. The adversary reconstruction number of a graph G is equal to one more than the number of vertex-deleted subgraphs which G can have in common with any other graph H. This number has been studied mostly by Wendy Myrvold. She considered the adversary reconstruction number of trees and she suggested the study of the maximum number of vertex-deleted subgraphs which a caterpillar can have in common with a sunshine graph (this is a unicyclic graph such that, removing all the vertices on the unique cycle results in a graph consisting only of isolated vertices). The edge adversary reconstruction number is analogously defined. Francalanza conjectures: A caterpillar and a sunshine graph can have at most n/3+1 edge-deleted subgraphs in common. She also gives an example showing that this bound is attained.
  7. With F. Harary. Let C be a class of graphs and let G Î C. The class reconstruction number ern(C;G) is defined to be the least number of vertex-deleted subgraphs which can determine G uniquely given the information that G is in C. For example, the class reconstruction number for regular graphs is clearly equal to 1. The edge class reconstruction number is similarly defined in terms of edge-deleted subgraphs. Harary and Lauri have shown that if C is the class of trees and T is any tree, then rn(C;T) £ 3. Myrvold strengthened this to rn(T) = 3, but in many of the cases which Harary and Lauri considered, rn(C;T) turned out to be 2. They, in fact, conjecture: The class reconstruction number of trees is at most 2.
  8. Harary and Lauri also demonstrated six trees whose edge class reconstruction number is 3. They ask: Are these the only trees with edge class reconstruction number greater than 2?
  9. Two vertices u,v in a graph G are said to be pseudosimilar if G-u and G-v are isomorphic but there is no isomorphism of G mapping u into v. A set S of vertices in G are said to be mutually pseudosimilar if any pair of vertices in S are pseudosimilar. Is there a sequence of graphs áGk ñ such that each Gk has k mutually pseudosimilar vertices and |V(Gk)| = O(k)? The best result obtained so far is a sequence with |V(G)| = O(k3/2).
  10. This problem is motivated by a problem in computational molecular biology. A long string (which can be circular) of DNA or RNA is sometimes analysed as follows. It is treated with an enzyme which splits the string into smaller fragments at specified points. It is also treated with another enzyme which fragments the string at different points. It is then also treated with both enzymes which splits the string at both types of points. The problem is then to identify the original string from the fragments. This suggests the following idealised combinatorial problem. Let C be a circle and suppose there is a finite number of points identified on the circle. These points are of two types, Type A and Type B. Suppose that points of different type alternate around the circle (otherwise, the answer to the question below would be no). Suppose you are given the following information: (i) The lengths of the arcs between successive points of Type A, (ii) the lengths of the arcs between successive points of Type B, (iii) the length of all the arcs joining a point of Type A to a successive point of Type B (with the appropriate A to B orientation) and similarly (iv) the lengths of all arcs joining points of Type B to successive points of Type A. Is the distribution of points round the circle reconstructible (up to orientation or reflection) from this information, or can one produce two essentially different distribution of points with the same set of information (i) to (iv)? One can modify the problem to make it more difficult to reconstruct the original circle (or more easy to find two different circles with the same fragment information) by lumping together the information in (iii) and (iv) and not giving the orientation (A to B or B to A) of these sub-fragments.

    11. Solution. The solution to this problem turns out to be quite easy, and the answer is NO-the circle is not necessarily reconstructible from the fragment information. The following are two examples of essentially different circles with the same fragments. In the following notation, each circle is given as a sequence of numbers which give the consecutive lengths of arcs between successive points, one of Type A and one of Type B. Of course, the sequence can be read starting at any entry and following a cyclic order, in any of the two possible directions. The letters x and y denote arbitrary numbers.
    Circle 1:

    (1,4,2,x,1,3,2,y,y,y)

    Circle 2:

    (1,3,2,x,1,4,2,y,y,y)

    This only confirms how much more difficult is the combinatorics of determining a sequence of RNA or DNA with such methods in real life experiments where the restrictions imposed in this idealised problem do not hold, and where the fragment lengths are often known only up to a certain degree of accuracy.

  11. With R. Scapellato. Let G be a p-group (or even a nilpotent group). Suppose H and K are two subgroups of G whose intersection is trivial and such that G is generated by HÈK. Must there be a non-trivial automorphism of G which fixes HÈK setwise? The answer to this question is no if G is not nilpotent.

File translated from TEX by TTH, version 2.00.
On 22 May 2000, 17:28.