Compact graphs and equitable partitions
From MaRDI portal
Let \(\Gamma\) and \(S(A)\) be the sets of permutation and doubly-stochastic matrices, respectively, which commute with the adjacency matrix \(A\) of a graph \(G\). A graph \(G\) is called compact if every matrix from \(S(A)\) is a convex combination of matrices from \(\Gamma\). Graphs for which \(S(A)= \{I\}\) are characterized. It is proved that in compact regular graphs \(G\) any two vertices can be interchanged by an automorphism of \(G\).
Recommendations
Cites work
- A note on certain subpolytopes of the assignment polytope associated with circulant graphs
- A note on compact graphs
- An Efficient Algorithm for Graph Isomorphism
- Feasibility conditions for the existence of walk-regular graphs
- Graph isomorphism and theorems of Birkhoff type
- scientific article; zbMATH DE number 3760444 (Why is no real title available?)
- scientific article; zbMATH DE number 43547 (Why is no real title available?)
- Problems in algebraic combinatorics
- Some applications of doubly stochastic matrices
Cited in
(42)- Minimum fractional dominating functions and maximum fractional packing functions
- Graph isomorphism and theorems of Birkhoff type
- A note on compact graphs
- Equipartitions of graphs
- Compact cellular algebras and permutation groups
- Characterizing and computing weight-equitable partitions of graphs
- Perfect 2-coloring of the quartic graphs with order at most 8
- Joins of hypergraphs and their spectra
- On the status sequences of trees
- On perfect colorings of infinite multipath graphs
- Edge-matching graph contractions and their interlacing properties
- Perfect 3-colorings on 6-regular graphs of order 9
- Permutational powers of a graph
- Graph isomorphism, color refinement, and compactness
- A characterization and an application of weight-regular partitions of graphs
- A short update on equipackable graphs
- On compact graphs
- On Tinhofer's linear programming approach to isomorphism testing
- On the power of color refinement
- The compactness of graph about complete graphs
- Two results of the compact graph and its applications
- Perfect 2-colorings of the generalized Petersen graph
- Parabolic theory of the discrete p-Laplace operator
- scientific article; zbMATH DE number 7009673 (Why is no real title available?)
- Constructing cospectral signed graphs
- Perfect 3-colorings of the cubic graphs of order 10
- Controlling consensus in networks with symmetries
- Perfect 2-colorings of the generalized Petersen graph \(GP(n,3)\)
- Perfect 4-colorings of the 3-regular graphs of order at most 8
- Relational linear programming
- scientific article; zbMATH DE number 7289053 (Why is no real title available?)
- Perfect 2-colorings of the cubic graphs of order less than or equal to 10
- Block transitivity and degree matrices
- Modeling Polarity-Driven Laminar Patterns in Bilayer Tissues with Mixed Signaling Mechanisms
- Perfect 2-colorings of C_n C_m
- Pattern polynomial graphs
- The iteration number of colour refinement
- An improved bound on the chromatic number of the pancake graphs
- Perfect colorings of submatrix hypergraphs
- A note on the calculation of vertex energy of graphs based on Estrada-Benzi approach
- Infinite families of directed strongly regular graphs using equitable partitions
- On compact symmetric regularizations of graphs
This page was built for publication: Compact graphs and equitable partitions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q677814)
