Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
type: Item
instance of: scholarly article
title: Forestal algebras and algebraic forests (on a new class of weakly compact graphs)
zbMATH Open document ID: 0962.05041
DOI: 10.1016/S0012-365X(00)00152-7
author: S. A. Evdokimov
author: Gottfried Tinhofer
author: Ilya Ponomarenko
published in: Discrete Mathematics
publication date: 2001-06-04T00:00:00Z
review text: 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 de…
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05E30
zbMATH DE Number: 1546495
zbMATH Keywords: algebraic forests
zbMATH Keywords: cellular algebras
zbMATH Keywords: forest algebras
zbMATH Keywords: strong isomorphism
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00152-7
OpenAlex ID: W1983221116
description: scientific article; zbMATH DE number 1546495