Search

A graph is called maximally non-Hamiltonian if it is non-hamiltonian, yet for any two non-adjacent vertices there exists a Hamiltonian path between them. In this paper, we naturally extend the concept to directed graphs and bound their size from below and above. Our results on the lower bound constitute our main contribution, while the upper bound can be obtained using a result of M. Lewin J. Comb. Theory, Ser. B 18, 175--179 (1975), but we give here a different proof. We describe digraphs attaining the upper bound, but whether our lower bound can be improved remains open. Graf se imenuje maksimalen nehamiltonski, če je nehamiltonski, poljubni dve nesosedni vozlišci pa sta povezani s hamiltonsko potjo. V članku naravno razširimo ta koncept na usmerjene grafe in podamo spodnjo in zgornjo mejo njihove velikosti. Naši rezultati v zvezi s spodnjo mejo predstavljajo naš glavni prispevek, medtem ko se da zgornjo mejo dobiti z uporabo Lewinovega rezultata, vendar v članku podamo drugačen dokaz. Opišemo digrafe, ki dosežejo zgornjo mejo, vprašanje, ali se da našo spodnjo mejo izboljšati, pa ostaja odprto.

We study the maximum number of congruent triangles in finite arrangements of l lines in the Euclidean plane. Denote this number by f (l) . We show that f (5) = 5 and that the construction realizing this maximum is unique, f (6) = 8 , and f (7) = 14 . We also discuss for which integers c there exist arrangements on l lines with exactly c congruent triangles. In parallel, we treat the case when the triangles are faces of the plane graph associated to the arrangement (i.e. the interior of the triangle has empty intersection with every line in the arrangement). Lastly, we formulate four conjectures.

We discuss an omission in the statement and proof of Fiorini's 1983 theorem on hypohamiltonian snarks and present a version of this theorem which is more general in several ways. Using Fiorini's erroneous result, Steffen showed that hypohamiltonian snarks exist for some $n \ge 10$ and each even $n \ge 92$. We rectify Steffen's proof by providing a correct demonstration of a technical lemma on flower snarks, which might be of separate interest. We then strengthen Steffen's theorem to the strongest possible form by determining all orders for which hypohamiltonian snarks exists. This also strengthens a result of M\'{a}\v{c}ajov\'{a} and \v{S}koviera. Finally, we verify a conjecture of Steffen on hypohamiltonian snarks up to 36 vertices., Comment: 21 pages; submitted for publication