A note on compact graphs

DOI10.1016/0166-218X(91)90049-3MaRDI QIDQ1174181zbMATH OpenOpenAlexWikidataFDO

Authors Gottfried Tinhofer

Publication date 25 June 1992

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(91)90049-3

zbMATH Keywords

adjacency matrixpermutation matricesdoubly stochastic matricesisomorphismpolynomial time algorithmcompact graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Stochastic matrices (15B51)

Recommendations

• On compact graphs
• Compact graphs and equitable partitions
• The compactness of graph about complete graphs
• Two results of the compact graph and its applications
• scientific article; zbMATH DE number 6613874

Cites work

• scientific article; zbMATH DE number 3545706 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• 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
• 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

Cited in

(30)

• On the expressive power of linear algebra on graphs
• The compactness of graph about complete graphs
• Lov\'asz Meets Weisfeiler and Leman
• On the expressive power of linear algebra on graphs
• scientific article; zbMATH DE number 6613874 (Why is no real title available?)
• Compactifying exchange graphs. I: Annuli and tubes
• The QAP-polytope and the graph isomorphism problem
• Compact graphings
• A NOTE ON THE GRAPH CONTINUITY
• Isomorphism of chordal (6, 3) graphs
• Combinatorial refinement on circulant graphs
• Two results of the compact graph and its applications
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
• Graph similarity and homomorphism densities
• The iteration number of colour refinement
• A graphon perspective for fractional isomorphism
• Graph isomorphism and multivariate graph spectrum
• Compact graphs and equitable partitions
• scientific article; zbMATH DE number 7559112 (Why is no real title available?)
• Directed path graph isomorphism
• On compact graphs
• Graph isomorphism, color refinement, and compactness
• A note on graphs and rational balls
• Consolidation for compact constraints and Kendall tau LP decodable permutation codes
• Satsuma: structure-based symmetry breaking in SAT
• Compact cellular algebras and permutation groups
• On Tinhofer's linear programming approach to isomorphism testing
• PEBBLE GAMES AND LINEAR EQUATIONS
• On the structure of compact graphs
• Fractional isomorphism of graphons

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)