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
• Publication:2991746

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

(25)

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

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)