Algebraic properties of perfect structures

DOI10.1016/J.LAA.2020.08.012MaRDI QIDQ2226406zbMATH OpenOpenAlexFDO

Authors Anna A. Taranenko

Publication date 12 February 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.10430

zbMATH Keywords

eigenfunctionequitable partitiongraph coveringgraph productperfect coloringperfect structure

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: A perfect structure is a triple $(M,P,S)$ of matrices $M,P$ and $S$ of consistent sizes such that $MP=PS$. Perfect structures comprise similar matrices, eigenvectors, perfect colorings (equitable partitions) and graph coverings. In this paper we study general algebraic properties of perfect structures and characterize all perfect structures with identity or unity matrix $M$. Next, we consider a graph product generalizing most standard products (e.g. Cartesian, tensor, normal, lexicographic graph products). For this product we propose a construction of perfect structures and prove that it can be reversed for eigenvectors. Finally, we apply obtained results to calculate the spectra of several classes of graphs and to prove some properties of perfect colorings.

Recommendations

• The Hopf algebra structures of perfect graphs and perfect 2-partite graphs
• On a metric property of perfect colorings
• Perfect 3-colorings of the Johnson graphs J(4,2), J(5,2), J(6,2) and Petersen graph.
• On perfect colorings of infinite multipath graphs
• Perfect transversal in some graph products

Cites work

• Handbook of product graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 5379405 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• Minimum supports of eigenfunctions of Hamming graphs
• Minimum supports of functions on the Hamming graphs with spectral constraints
• On weight distributions of perfect colorings and completely regular codes
• Perfect colorings of the prism graph
• Problems in algebraic combinatorics
• Spectra of graphs

Cited in

(8)

• On a metric property of perfect colorings
• On the non-existence of extended 1-perfect codes and MDS codes
• The perfect matching association scheme
• The radical of a perfect residuated structure
• On perfect colorings of paths divisible by a matching
• Minimum supports of eigenfunctions of graphs: a survey
• Perfect colourings of hypergraphs
• On eigenfunctions of the block graphs of geometric Steiner systems

This page was built for publication: Algebraic properties of perfect structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2226406)