Cycle-regular graphs (Q2277469)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycle-regular graphs |
scientific article |
Statements
Cycle-regular graphs (English)
0 references
1991
0 references
A (0,\(\lambda\))-graph is understood to be a connected graph in which any two vertices have \(\lambda\) common neighbors or none at all. These graphs were introduced by \textit{M. Mulder} [ibid. 28, 179-188 (1979; Zbl 0418.05034)]. He also proved that maximum (0,\(\lambda\))-graphs are hypercubes. In the paper under review the concept of (0,\(\lambda\))-graphs is generalized in some sense as follows. We say that G is a [\(\ell,\lambda]\)-cycle regular graph if there is a nonempty subset C of elementary cycles in G such that every path in G of length \(\ell\) belongs to exactly \(\lambda\) cycles in C. If C is the set of elementary cycles of length m (m\(\geq 2\ell)\), then G is said to be a [\(\ell,\lambda,m]\)-cycle regular graph. In Section 1 the author is concerned with the regularity of [\(\ell,\lambda]\)-cycle regular graphs with minimum degree \(\delta\geq 3\). Section 2 discusses the case \(\delta (G)=2\). In Section 3 two families of [3,1,6]-cycle regular graphs are described. Finally, it turns out that maximum [3,1,6]-cycle regular graphs are also related to hypercubes.
0 references
(O,lambda)-graphs
0 references
cycle regular graph
0 references