ISSN:
1435-5914
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Behzad, Chartrand and Wall proposed the conjecture that any regular digraph of degreer and girthg has ordern ≥ r(g − 1) + 1. The conjecture was proved in [3] for vertex transitive graphs. For Loop Networks the conjecture is equivalent to a theorem of Shepherdson in additive number theory. We show that, except for graphs of a particular structure, Loop Networks, and in general Abelian Cayley graphs, verify the stronger inequalityn ≥ (r + 1)(g − 1) − 1. This bound is best possible.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01929482
Permalink