Anticonnected digraphs
Abstract
A semipath in a digraph containing no directed path of length 2 is called an antipath. A digraph D is anticonnected if D contains a u-v antipath for each pair u, v of vertices of D. A digraph is antihamiltonian if it contains a hamiltonian anticycle. A digraph D is antihamiltonian extendable if every antipath can be extended to an antihamiltonian cycle and is antihamiltonian-connected if D has a hamiltonian u - v antipath for every pair u, v of vertices of D. Some results concerning antihamiltonian extendable digraphs and antihamiltonian-connected digraphs are presented. The antidistance between two vertices is the length of a shortest antipath between them. The eccentricity of a vertex v is the maximum antidistance between v and another vertex of D. The minimum eccentricity is the antiradius rad D of D and the maximum eccectricity is its antidiameter diam D. The subdigraph of D induced by those vertices with eccentricity rad D is called the anticenter of D, while the subdigraph induced by those vertices with eccentricity diam D is its antiperiphery. All digraphs are determined that can be the anticenter or antiperiphery of some anticonnected digraph. It is shown that if G is a graph of order n ≥ 3 such that deg v ≥ (3n - 1)/4 for every vertex v of G, then every orientation of G is anticonnected and that this bound is sharp.
