17
$\begingroup$

Joshua Lederberg received a the Nobel prize in medicine in 1958 and he was a major contributor to the Stanford DENDRAL software expert system that

Given a mass spectrum of an organic molecular sample and the chemical formula of the molecule, the program will produce a short list of molecular "graphs" as hypotheses...

In that expert system non-Hamiltonicity plays a central role and Lederberg devised a method of generating non-Hamilton graphs by means of a 9-vertex "gadget" and with it constructed a planar cubic and biconnected non-Hamiltonian graph with 18 vertices and also the better known Barnette-Bosák-Lederberg graph that is triply connected.

Question:

  • how well is Lederberg's contribution to graph theory known in the graph theory community?
  • is chemical graph theory recognized as a research topic in graph theory?

A search for "Lederberg" on MO didn't succeed and trying to find a definition or illustration of Lederberg's 18-vertex graph is also a frustrating task, even with AI assistance.

I'm not sure if the 9-vertex gadget or the 18-vertex Lederberg graphs are known to the house of graphs

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ I can't answer your questions about Lederberg, but the classic book Spectra of Graphs: Theory and Application by Cvetković, Doob, and Sachs repeatedly mentions that many results in the spectral theory of graphs are due to chemists. $\endgroup$ Commented Feb 22 at 13:49
  • $\begingroup$ I just learned that the Flinders University Graph Database contains downloadable definitons of small cubic graphs up to about 20 vertices for Hamiltonian and for non-Hamiltonian instances. And there is of course plantri which also allows for exhaustive search for planar cubic graphs that have no Hamilton cycles and have the right number of vertices $\endgroup$ Commented Feb 28 at 16:34

5 Answers 5

Reset to default
11
$\begingroup$

Addressing your questions in the reverse order:

Chemical graph theory is enough of a field to have books devoted to it. Nenad Trinadstić published a two volume Chemical Graph Theory in 1983 that was updated in a combined second edition in 1992. Stephan Wagner and Hua Wang published Introduction to Chemcial Graph Theory in 2019. (All of these are from CRC Press.)

Searching Lederberg in MathSciNet gives seven hits, of which six seem relevant. In addition to the Monthly article mentioned by Timothy Chow, he wrote a chapter "Topology of molecules" in a 1969 collection The Mathematical Sciences (MIT Press). The other four follow.

Jean W. Butler. Hamiltonian circuits on simple 3-polytopes J. Combinatorial Theory Ser. B 15 (1973) 69–73.

Roberto Frucht. A canonical representation of trivalent Hamiltonian graphs. J. Graph Theory 1 (1977) 45–60.

David W. Barnette. Every simple 3-polytype with 34 vertices is Hamiltonian. Discrete Math. 62 (1986) 1–20.

D. A. Holton and B. D. McKay. The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices. J. Combin. Theory Ser. B 45 (1988) 305–319.

Here are additional articles from zbMath (that reference the Lederberg paper or mention him in the review):

Branko Grünbaum. Polytopes, graphs, and complexes. Bull. Amer. Math. Soc. 76 (1970) 1131-1201.

Branko Grünbaum and Hansjoachim Walther. Shortness exponents of families of graphs. J. Comb. Theory, Ser. A 14 (1973) 364-385.

Branko Grünbaum. Acyclic colorings of planar graphs. Isr. J. Math. 14 (1973) 390-408.

David Barnette and Gerd Wegner. Hamiltonian circuits in simple 3-polytopes with up to 26 vertices. Isr. J. Math. 19 (1974) 212-216.

Paul Goodey and Moshe Rosenfeld. Hamiltonian circuits in prisms over certain simple 3-polytopes. Discrete Math. 21 (1978) 229-235.

Nicolas Van Cleemput and Carol T. Zamfirescu. Regular non-Hamiltonian polyhedral graphs. Appl. Math. Comput. 338 (2018) 192-206.

Stefan Steinerberger. A spectral approach to the shortest path problem. Linear Algebra Appl. 620 (2021) 182-200.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ I see that I should have consulted MathSciNet instead of using "traditional" online search. The 18-vertex Lederberg graph is only 2-connected and not polyhedral and I really would like to see it depicted or described somewhere $\endgroup$ Commented Feb 23 at 16:53
  • $\begingroup$ @ManfredWeis Actually, I see now that the paper that you yourself linked to in your question cites Lederberg's Monthly paper. From there you could have found some of the other references using Google Scholar. But apropos the 18-vertex Lederberg graph, what exactly do you know about it and what references exist? Maybe you could ask that as a separate MO question. $\endgroup$ Commented Feb 23 at 17:52
  • $\begingroup$ The 4 papers you cite at the end all either mention Lederberg somewhere in the text or cite a paper by him in the references? $\endgroup$ Commented Feb 24 at 7:05
  • $\begingroup$ @quarague The four papers each include Lederberg in the review. None of them happen to include the papers' bibliographies. $\endgroup$ Commented Feb 25 at 2:40
15
$\begingroup$

Lederberg wrote an article Hamilton circuits of convex trivalent polyhedra (up to 18 vertices) in the American Mathematical Monthly 74 (1967), 522–527, and Google Scholar lists a number of citations of this paper in the mathematical literature. So that gives us a lower bound on how well known Lederberg's contributions are to graph theorists.

Improve this answer
$\endgroup$
10
$\begingroup$

As Brian noted in his answer, chemical graph theory is very much of interest to graph theorists. However, unlike the extremely important short cycles, hamiltonian cycles do not have any chemical significance that I am aware of.

In the paper that Timothy linked to, Lederberg only indicates that molecular graphs suggested the problem to him. Neither of the two DENRAL papers it cites mentions hamiltonian cycles.

Therefore, I doubt the assertion that hamiltonian cycles played a significant role in DENDRAL.

Here is the unique smallest non-hamiltonian 2-connected cubic planar graph. It has 14 vertices.

enter image description here

From 4 to 32 vertices, here are counts "non-hamiltonian/all":

0/1, 0/1, 0/3, 0/8, 0/29, 1/114, 5/583, 31/3310, 200/21168, 477/144622, 11507/1039495, 94891/7731540, 801157/59054465, 6867298/460532269, 59314885/3654030986

Incidentally, those are counts of abstract isomorphism classes, even though many of the graphs have more than one embedding. Although it is still true that most of these small graphs are hamiltonian, as the size increases eventually the non-hamiltonian ones dominate.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Thanks for mentioning this. I was wondering how an NP-complete property could be physically or chemically important. $\endgroup$ Commented Feb 24 at 12:10
  • 2
    $\begingroup$ This raises the question of why Lederberg was interested in Hamilton cycles? In the paper oeis.org/A000602/a000602_10.pdf about DENDRAL (note the two Ds) he devotes quite a bit of time talking about Hamilton cycles. He also uses the term gauche graph for a non-planar graph, which obviously did not catch on. $\endgroup$ Commented Feb 25 at 2:25
  • 3
    $\begingroup$ @GordonRoyle In that paper he is on about graph generation, and one way to generate cubic graphs is to consider them as chords on a hamiltonian cycle. Then he says they rely on there being such a cycle, presumably because the known counterexamples are much bigger than the range of their computations. So I was not correct to say that hamiltonian cycles are unimportant for DENDRAL, though I still maintain that that have no have no chemical application in the sense of there not being a chemical behaviour of a molecule meaningfully related to whether it has a hamiltonian cycle. $\endgroup$ Commented Feb 25 at 12:26
  • 1
    $\begingroup$ @TimothyChow The number of Eulerian orientations is one of the Tutte polynomial evaluations that is #P-hard, so testing a bound is NP-hard. This is used in a theory of physical lattices like water ice. I think there are other examples, like Ising models. Of course all such things are approximations of physical reality. Anyway the point is that being NP-hard is not necessarily an impediment to physical importance, though I don't know a clear-cut example of an NP-complete existence problem that fits the bill. $\endgroup$ Commented Mar 9 at 3:15
6
$\begingroup$

Here is an 18-vertex graph that is cubic, planar, non-Hamiltonian and is constructed from 2 copies of a 9-vertex graph joined by 3 edges.

enter image description here

I do not know if this is Lederberg's original example, but there are no other 18-vertex planar cubic non-Hamiltonian graphs that are constructed in this fashion.

The fact that it is non-Hamiltonian is immediate from observing that the gadget alone has no Hamilton path connecting an end-vertex to the middle-vertex.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I suspect that it is not the Lederberg graph and if that is the case, your graph would be interesting because it would have taken about 60 years until a different graph with the same properties has been found $\endgroup$ Commented Feb 25 at 15:30
  • $\begingroup$ @ManfredWeis I'm still curious as to what you know about the Lederberg graph and what your sources are. $\endgroup$ Commented Feb 28 at 21:17
  • 1
    $\begingroup$ @ManfredWeis I am still confused about how you know that Lederberg found a 9-vertex gadget and combined two of them to generate a planar cubic non-Hamiltonian biconnected graph. Did you read this claim in a NASA report? If not, where? $\endgroup$ Commented Mar 1 at 11:03
  • 2
    $\begingroup$ @ManfredWeis That is AI gossip for sure. This report says that Memo 54 is Mechanization of Inductive Inference in Organic Chemistry by Lederberg and Feigenbaum, not some weird title with "computer consciousness." I haven't been able to find the latter paper online, but my guess is that its contents are similar to DENDRAL and Meta-DENDRAL: Their Applications Dimension and that it doesn't contain the quoted passage. $\endgroup$ Commented Mar 1 at 13:04
  • 4
    $\begingroup$ Update: It seems that Mechanization of Inductive Inference in Organic Chemistry was reprinted in a book. As I suspected, there is no Section 5 entitled "Topological Mapping," let alone any mention of non-Hamiltonian graphs. $\endgroup$ Commented Mar 2 at 1:41
1
$\begingroup$

just for the records: the smallest biconnected, planar, cubic and non-Hamiltonian graphs have 16 vertices

the two non-isomorphic smallest planar, biconnected, cubic and non-Hamiltonian graphs

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sorry, there's one with 14 vertices, see my answer shortly. $\endgroup$ Commented Mar 8 at 4:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.