A CHARACTERIZATION OF THE DOOB GRAPHS

摘要

For a graph Gamma we say that lambda exists if every edge lies in exactly lambda triangles. Egawa has shown that the Hamming graphs are determined by their parameters, unless lambda equals 2. In that case the only possible graphs are the Doob graphs. Rifa and Huguet and Nomura generalised this result by Egawa for lambda not equal 2. We generalise Egawa's result for lambda=2. The main part of the proof is a characterization of cartesian products of graphs. (C) 1995 Academic Press, Inc. [References: 11]