Highly regular graphs. (English) Zbl 0792.05093

Alavi, Yousef; Chartrand, Gary; Lick, Don R.; Swart, Henda C.

Capobianco, Michael F. (ed.) et al., Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9-20, 1986. New York: New York Academy of Sciences,. Ann. N. Y. Acad. Sci. 576, 20-29 (1989).

A graph \(G\) of order \(p \geq 3\) is highly regular if there exists an \(n \times n\) matrix \(C=[c_{ij}]\), where \(2 \leq n<p\), called a collapsed adjacency matrix (CAM), such that for each vertex \(v\) of \(G\) there is a partition of \(V(G)\) into \(n\) subsets \(V_ 1=\{v\}\), \(V_ 2,\dots,V_ n\), such that each vertex \(y \in V_ j\) is adjacent to \(c_{ij}\) vertices in \(V_ i\). In this article we develop some of the properties of highly regular graphs.
For the entire collection see [Zbl 0788.00046].

MSC:

05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)
05C99	Graph theory

Keywords:

collapsed adjacency matrix; partition; highly regular graphs