On the maximum number of arcs in some classes of graphs

A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8-traceable oriented graph is traceable.

Vertex-oriented Hamilton cycles in directed graphs.

Plantholt, Michael J., Tipnis, Shailesh K. (2009)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Two constructions of geodetic graphs

Ján Plesník (1977)

Mathematica Slovaca

Similarity:

Displaying similar documents to “On the maximum number of arcs in some classes of graphs”

An extremal problem for some classes of oriented graphs

On partially directed P -graphs

On the crossing numbers of S m × P n and S m × C n

Every 8-Traceable Oriented Graph Is Traceable

Vertex-oriented Hamilton cycles in directed graphs.

Two constructions of geodetic graphs

On partially directed $P$ -graphs

On the crossing numbers of $S_{m} \times P_{n}$ and $S_{m} \times C_{n}$