Balancing permuted copies of multigraphs and integer matrices

DOI10.1016/J.JCTA.2023.105756MaRDI QIDQ6162862zbMATH OpenOpenAlexFDO

Authors Coen del Valle, Peter Dukes

Publication date 26 June 2023

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

permutationgraph decompositioncombinatorial matrix theory

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Combinatorial aspects of block designs (05B05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph designs and isomorphic decomposition (05C51)

Abstract: Given a square matrix $A$ over the integers, we consider the $mathbbZ$-module $M_A$ generated by the set of all matrices that are permutation-similar to $A$. Motivated by analogous problems on signed graph decompositions and block designs, we are interested in the completely symmetric matrices $aI+bJ$ belonging to $M_A$. We give a relatively fast method to compute a generator for such matrices, avoiding the need for a very large canonical form over $mathbbZ$. We consider several special cases in detail. In particular, the problem for symmetric matrices answers a question of Cameron and Cioabv{a} on determining the eventual period for integers $lambda$ such that the $lambda$-fold complete graph $lambda{K}_n$ has an edge-decomposition into a given (multi)graph.

Recommendations

• Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
• Commuting decompositions of complete graphs
• Balanced \(0,\pm 1\) matrices. I: Decomposition
• A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case
• Circulant blocks and rotational graphs

Cites work

• scientific article; zbMATH DE number 3458752 (Why is no real title available?)
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• A graph partition problem
• A linear algebraic approach to directed designs
• An existence theory for loopy graph decompositions
• Asymptotic Existence of Resolvable Graph Designs
• Diagonal forms of incidence matrices associated with \(t\)-uniform hypergraphs
• Progress towards Nash-Williams' conjecture on triangle decompositions
• Signed hypergraph designs and diagonal forms for some incidence matrices
• Smith normal forms of incidence matrices
• The Smith normal form
• The module structure of integral designs

Cited in

(1)

• Combinatorics of balanced carries

This page was built for publication: Balancing permuted copies of multigraphs and integer matrices

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