Characterizing Homogeneous Digraphs

Jing Huang1
1Department of Mathematics and Statistics, University of Victoria, P.O. Box 3060 STN CSC, Victoria, B.C., Canada V8W 3RA4.

Abstract

A digraph is called \({homogeneous}\) if every connected induced sub-digraph with two or more vertices is either strong or acyclic. The class of homogeneous digraphs contains acyclic digraphs, round digraphs, and symmetric digraphs. Tournaments which are homogeneous have been studied by Guido, Moon, and others, and characterized by Moon. In this paper, we give a characterization of homogeneous digraphs. Our characterization reveals a nice structural property of this class of digraphs and shows that all homogeneous digraphs can be obtained from acyclic digraphs, round digraphs, and symmetric digraphs by the operation of substitution.