A note on compact graphs
adjacency matrixcompact graphdoubly stochastic matricesisomorphismpermutation matricespolynomial time algorithm
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Stochastic matrices (15B51) Graph theory (including graph drawing) in computer science (68R10)
Let \(G\) be an undirected simple graph with adjacency matrix \(A\). By \(S(A)\) we denote the set of all doubly stochastic matrices which commute with \(A\). We say \(G\) is compact if the extreme points of \(S(A)\) are all integral. It is not hard to see that the integral extreme points of \(S(A)\) are precisely the permutation matrices which commute with \(A\). Note also that \(S(A)\) is closed under matrix multiplication. Compact graphs form a fairly restricted class, for example, any compact regular graph must be vertex-transitive. The main result of this paper is a simple polynomial time algorithm for deciding whether a graph \(H\) is isomorphic to a given compact graph \(G\). The bad news is that the problem of recognising whether a graph is compact is not even known to be in NP.
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- A note on certain subpolytopes of the assignment polytope associated with circulant graphs
- An Efficient Algorithm for Graph Isomorphism
- Geometric algorithms and combinatorial optimization
- Graph isomorphism and theorems of Birkhoff type
- scientific article; zbMATH DE number 3545706 (Why is no real title available?)
- scientific article; zbMATH DE number 3575612 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- On testing isomorphism of permutation graphs
- Some applications of doubly stochastic matrices
- Strong tree-cographs are Birkhoff graphs
- The graph isomorphism disease
- Compact cellular algebras and permutation groups
- The QAP-polytope and the graph isomorphism problem
- A note on graphs and rational balls
- Consolidation for compact constraints and Kendall tau LP decodable permutation codes
- Isomorphism of chordal (6, 3) graphs
- Compact graphings
- On the expressive power of linear algebra on graphs
- Fractional isomorphism of graphons
- Graph isomorphism, color refinement, and compactness
- On compact graphs
- On Tinhofer's linear programming approach to isomorphism testing
- The compactness of graph about complete graphs
- scientific article; zbMATH DE number 6613874 (Why is no real title available?)
- Two results of the compact graph and its applications
- A NOTE ON THE GRAPH CONTINUITY
- PEBBLE GAMES AND LINEAR EQUATIONS
- Compactifying exchange graphs. I: Annuli and tubes
- On the structure of compact graphs
- Lov\'asz Meets Weisfeiler and Leman
- Algorithmic data science (invited talk)
- On the expressive power of linear algebra on graphs
- Directed path graph isomorphism
- Combinatorial refinement on circulant graphs
- A graphon perspective for fractional isomorphism
- Compact graphs and equitable partitions
- The iteration number of colour refinement
- Satsuma: structure-based symmetry breaking in SAT
- Graph isomorphism and multivariate graph spectrum
- The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
- Graph similarity and homomorphism densities
This page was built for publication: A note on compact graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1174181)
