Forestal algebras and algebraic forests (on a new class of weakly compact graphs) (Q1591143)

A new class of graphs called algebraic forests is introduced in this paper, which includes the classes of cographs, trees, interval graphs and rooted-directed path graphs. The authors prove that membership in this class can be tested in \(O(n^{3}\log n)\) time and that isomorphism testing for two graphs in the class also has the same complexity. The tool employed is the notion of cellular (or coherent) algebra whose use in isomorphism studies is fairly well known [see, e.g., \textit{B. Weisfeiler}, On construction and identification of graphs (Lecture Notes in Mathematics. 558. Berlin: Springer-Verlag) (1976; Zbl 0366.05019) and \textit{I. A. Faradžev} et al. (ed.), Investigationes in algebraic theory of combinatorial objects (Mathematics and Its Applications. Soviet Series. 84. Dordrecht: Kluwer Academic Publishers) (1994; Zbl 0782.00025)]. A cellular algebra \(W\) is a subalgebra of \(\text{Mat}_{V}\) (the algebra of all complex matrices whose rows and columns are indexed by the elements of a finite set \(V\)) which is closed under Hadamard (componentwise) multiplication, Hermite conjugation and contains the identity matrix \(I_{V}\) and the all-one matrix \(J_{V}\). The automorphism group \(\Aut(W)\) of \(W\) consists of all permutations \(g\) of \(V\) such that the permutation matrix corresponding to \(g\) centralizes \(W\). With each graph \(\Gamma \) one associates the smallest cellular algebra \(W(\Gamma)\) containing its adjacency matrix and this algebra is said to be generated by \(\Gamma \). A class \(\mathcal F\) of forest cellular algebras is defined recursively from one point cellular algebras by means of taking direct sums and wreath products by symmetric groups. Each forestal algebra is shown to coincide with the restriction of the cellular algebra of some forest to the set of its leaves. Finally, algebraic forests are defined to be graphs whose cellular algebras are forestal. Besides the main results mentioned above, the authors present a complete description of cellular algebras of disconnected graphs. Another interesting consequence obtained is that \(n^{3}\) is an upper bound for the cardinality of a complete set of invariants of an \(n\)-vertex algebraic forest.