semi-Hamiltonian paths in planar triangulations
in [Theory]
|
Prev: Exchange of the "oracle machine" and the "oracle" in the polynomial-time hierachy
Next: [] semi-Hamiltonian paths in planar triangulations
From: Mike Terry on 13 Jun 2010 10:08 "William Elliot" <marsh(a)rdrop.remove.com> wrote in message news:20100613031744.T30925(a)agora.rdrop.com... > On Sun, 13 Jun 2010, stdazi(a)gmail.com wrote: > > > On Jun 13, 8:13 am, William Elliot <ma...(a)rdrop.remove.com> wrote: > >> On Sat, 12 Jun 2010, Yann David wrote: > >>> I'd like to know whether there is any known simple instance of planar > >>> triangulation (finite planar graph which is maximal in the sense that > >>> no edge can be added to it) in which there is no semi-Hamiltonian path > >>> of which both endpoints are on the external face. > >> > >>> (A semi-Hamiltonian path is an elementary path that traverses each > >>> vertex of the graph exactly once.) > >> > >>> One could, more specifically, ask for a triangulation in which no semi- > >>> Hamiltonian path has both endpoints on the same face (be it the outer > >>> one or otherwise) or even without any semi-Hamiltonian path at all (a > >>> non semi-Hamiltonian triangulation). > >> > >> o > >> | > >> o--o--o > >> > >> in monospace font, has no Hamiltonian paths. > >> > >>> Any solutions, pointers, suggestions... are most welcome! > > > > how is that a triangulation? > > > It's a finite planar graph as OP described above. It's not maximal as the OP described above. o |\ | \ o--o--o Look - I managed to add another edge! > Why is the beginning of your sentence not capitalized? Why didn't you read what the OP asked? :) Mike.
From: spudnik on 14 Jun 2010 21:40 if a "semi-hamiltonian" path ended on the same face as it began, is it hamiltonian? thus&so: 1/9 is, in base-9, 1/10; or 0.10000... so, what is the canonical digit for base-one? thus&so: time obviously doesn't bend, except in a subjective sense of living & dying, sleeping & waking ... it's too bad about Schroedinger's joke-cat, though ... Schroedinger's cat is dead; long-live Schroedinger's cat! the curvature of space was dyscovered with "synchronized sundials" by Aristarchus; it was measured in Alsace-Lorraine by Gauss, with his theodolite & trigonation ... for money, ne'er again! Dear Editor; It is apparent from the City ordinance, proposed to ban high-density polyethylene (HDPE) bags -- excepting take-out at restaurants -- that it will be a state-wide eco-tax. The "green fee" is slated to be 25 cents for any paper bag from the retailer, grocer or farmer at the market. This is unfortunate for two reasons, although, as I stated a year ago in Council, when it first came-up, the super-light-weight & super-inexpenseve bags (much less than the Staff Report was willing to concede) are so good at what they do, before they inevitably break-up & decompose (but , according to the apocrypha & studies of Heal the Bay etc., HDPEbagsR4ever) that coastal cities may be justified in a ban, to prevent stormdrain blockages. Firstly, just like with "hemp for haemarrhoids," it is not a panacea or much of an economic stop-gap, if only because "only criminals & baby-smotherers will have HDPE bags." Really, there are plenty of natural plastics; "plastic" is really an adjective, as in the plastic arts! Note also that even plant-derived plastic bags will be banned, although they are acknowledged to biodegrade. Secondly, a very small Carbon Tax would be much more realistic than simply allowing Waxman's CO2 cap & trade nostrum, of letting the abitrageurs & daytraders raise the price of our energy as much as they can in the "free market" -- with no provision whatever for government revenue (contrary to the slogan of "cap & tax" used by Tea Partiers, "Republicans," and the WSUrinal). As with the much-greater amount of materiel & energy that is required for the paper bags, we might do better to ban *low* density polypropolene bags at department & boutique stores, which are many times heavier than the HDPE bags. It is surprising that a fifth of the HDPE bags are recycled, considerng that a) they're only good for garbage, if they get dirty, and b) they are quite often re-used by folks; recycling them is an unsanitary joke, though composting might be educational fun. The retailers would get ten of the 25 cents, which seems to be a quite an incentive for the overhead. However, has anyone seen any analysis on the energy requirements for the "reusable" replacement, and their importation? --Sincerely, Brian H. --Stop BP's/Waxman's arbitragueur-daytripper's delight, cap&trade (Captain Tax in the feeble minds of Tea Partiers, "'republicans' R us," and the WSUrinal (and the latter just l o v e Waxman's '91 cap&trade bill !-)) http://wlym.com
From: Yann David on 15 Jun 2010 07:59 On Jun 14, 9:40 pm, spudnik <Space...(a)hotmail.com> wrote: > if a "semi-hamiltonian" path ended > on the same face as it began, > is it hamiltonian? Hum, I guess you're right. Since every face is a triangle, a semi- Hamiltonian path with both endpoints on the same face is Hamiltonian. How could I miss that? Anyway, the problem is still open as far as I'm concerned - but maybe it should be more clearly divided in 2: 1) find a non Hamiltonian triangulation; 2) find a non semi-Hamiltonian triangulation.
From: Yann David on 15 Jun 2010 20:10 On Jun 15, 7:59 am, Yann David <yann_da...(a)hotmail.com> wrote: > On Jun 14, 9:40 pm, spudnik <Space...(a)hotmail.com> wrote: > > > if a "semi-hamiltonian" path ended > > on the same face as it began, > > is it hamiltonian? > > Hum, I guess you're right. Since every face is a triangle, a semi- > Hamiltonian path with both endpoints on the same face is Hamiltonian. > How could I miss that? > > Anyway, the problem is still open as far as I'm concerned - but maybe > it should be more clearly divided in 2: > 1) find a non Hamiltonian triangulation; > 2) find a non semi-Hamiltonian triangulation. In fact, a semi-Hamiltonian path with both endpoints on the external face is actually "stronger" than a "simple" Hamiltonian circuit since a Hamiltonian circuit can trivially be derived from such a path, but the reverse is not true - it's only possible when the circuit traverses one of the edges of the external face. Finding a counterexample should be easier then. :)
From: William Elliot on 16 Jun 2010 02:56
On Tue, 15 Jun 2010, Yann David wrote: > Anyway, the problem is still open as far as I'm concerned - but maybe > it should be more clearly divided in 2: > 1) find a non Hamiltonian triangulation; > 2) find a non semi-Hamiltonian triangulation. > What's a trianglation? Are these definitions the same definitions you're using? A graph is Hamiltonian when there's a circuit that visits each vertex only once. A graph is semi-Hamiltonian when there's a path that visits each vertex only once. |