✦ LIBER ✦

A counterexample to a conjecture of grant

✍ Scribed by Mao-cheng Cai

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 74 KB
Volume: 44
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(83)90010-9

No coin nor oath required. For personal study only.

✦ Synopsis

We give a counterexample to the following conjecture of Douglas D. Grant Cl]: If a positive integer t 3 2 and D is a strict digraph of order 2t such that S+(D) 3 t and S'(D)2 t, then D has an anti-directed hamiltonian cycle. Where S+(D) and 6-(D) denote the minimum indegree and outdegree, respectively. A hamiltonian cycle in a digraph is called anti-directed if no two of its consecutive arcs form a directed path.

The counterexample is given in Fig. , where an edge e with two arrows denotes the two oppositely oriented arcs with the same ends as e. For every vertex u of D; d+(u) = d-(u) = t.

📜 SIMILAR VOLUMES

A counterexample to a conjecture of Hass

A counterexample to a conjecture of Hasson

✍ Chengmin Yang 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 127 KB

Counterexamples to a conjecture of Tamas

Counterexamples to a conjecture of Tamaschke

✍ E.C Dade 📂 Article 📅 1969 🏛 Elsevier Science 🌐 English ⚖ 247 KB

A counterexample to the bold conjecture

✍ Sakuma, Tadashi 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views

A pair of vertices (x, y) of a graph G is an ω-critical pair if ω(G + xy) > ω(G), where G + xy denotes the graph obtained by adding the edge xy to G and ω(H) is the clique number of H. The ω-critical pairs are never edges in G. A maximal stable set S of G is called a forced color class of G if S mee

A simple counterexample to a conjecture

A simple counterexample to a conjecture of rota

✍ J.B. Shearer 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 319 KB

A counterexample to the rank-coloring co

A counterexample to the rank-coloring conjecture

✍ N. Alon; P. D. Seymour 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

It has been conjectured by C. van Nuffelen that the chromatic number of any graph with at least one edge does not exceed the rank of its adjacency matrix. We give a counterexample, with chromatic number 32 and with an adjacency matrix of rank 29.

Counterexample to a conjecture on Hamilt

Counterexample to a conjecture on Hamilton cycles

✍ P Paulraja 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 65 KB

We disprove the following conjecture: Let G be a 2-connected graph with minimum degree n on atmost 3n -2 vertices. Then G is hamiltonian if it has a 2-factor.