Cycle-regular graphs of \((0,\lambda )\)-graph type
type: Item
instance of: scholarly article
title: Cycle-regular graphs of \((0,\lambda )\)-graph type
zbMATH Open document ID: 1209.05132
author: Nawel Kahoul
author: Abdelhafid Berrachedi
published in: Discrete Mathematics
publication date: 2010-03-29T00:00:00Z
review text: A connected simple graph \(G\) is a \textit{\((0,\lambda )\)-graph}, introduced by \textit{M. Mulder} [``\((0,\lambda)\)-graphs and \(n\)-cubes,'' Discrete Math. 28, 179--188 (1979; Zbl 0418.05034)], if every pair of distinct vertices have exactly \(\lambda\) common neighbors or none at all. Hadamard graphs and hypercubes are examples of \((0, \lambda )\)-graphs. \textit{M. Mollard} [``Cycle-regular graphs,'' Discrete Math. 89, No. 1, 29--41 (1991; Zbl 0726.05044)] defined a graph \(G\) to be an \textit{\([l, \lambda]\)-cycle-regular graph} if there is a nonempty subset \({\mathcal C}\) of cycles in \(G\) such that every path in \(G\) of length \(l\) belongs to exactly \(\lambda\) cycles in \({\mathcal C}\). In particular, if \({\mathcal C}\) is the set of cycles of length \(k\) where \(k \geq 2l\), then \(G\) is an \textit{\([l, \lambda, k]\)-cycle-regular graph}. Thus \((0, \lambda )\)-graphs are \([2, \lambda - 1, 4]\)-cycle-regular graphs. Let \(H_n\) be the subgraph of the hypercube \(Q_{2n-1}\) induced by the \(n\)-subsets and \((n-1)\)-subsets of a \((2n-1)\)-element set. Two vertices \(A, B \in H_n\) are adjacent to each other if and only if \(|(A \setminus B) \cup (B \setminus A)| = 1\). The odd graphs and the graphs \(H_n\) are \([3, 1, 6]\)-cycle-regular graphs. Mollard [loc. cit.] showed that if a \([3, 1, 6]\)-cycle-regular graph \(G\) has maximum degree \(\Delta(G) = n\), then \(G\) has at most \({2n \choose n}\) vertices and the diameter \(diam(G)\) of \(G\) is at most \(2n - 1\). Also, if a \([3, 1, 6]\)-cycle-regular graph \(G\) has \(\Delta(G) = n\) and \(|V(G)| = {2n \choose n}\), then \(G = H_n\). The main result of this paper is that if a \([3, 1, 6]\)-cycle-regular graph \(G\) has \(\Delta(G) = n\) and \(diam(G) = 2n - 1\), then \(G = H_n\).
reviewed by: Ya-Chen Chen
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5687554
zbMATH Keywords: hypercubes
zbMATH Keywords: odd graphs
zbMATH Keywords: semi-regular graphs
zbMATH Keywords: \((0, \lambda )\)-graph
zbMATH Keywords: cycle-regular graph
MaRDI profile type: Publication
full work available at URL: j.disc.2008.09.022
OpenAlex ID: W2083831242
cites work: Q5422499
cites work: Q3309859
cites work: Another characterization of hypercubes
cites work: Cycle-regular graphs
cites work: \((0,\lambda)\)-graphs and \(n\)-cubes
cites work: Q3890733
DOI: 10.1016/J.DISC.2008.09.022
Recommended article: Cycle-regular graphs
Recommended article: Existence of graphs with specified cycle lengths
Recommended article: Partitioning the edge set of a hypergraph into almost regular cycles
Recommended article: Q3697040
Recommended article: 4-cycle properties for characterizing\newline rectagraphs and hypercubes
Recommended article: Q5487120
Recommended article: Q3708045
Recommended article: Q3201092
Recommended article: Q3347917
Recommended article: On subgraphs in distance-regular graphs
description: scientific article; zbMATH DE number 5687554