On graph equivalences preserved under extensions

DOI10.1016/J.DISC.2011.02.029zbMATH Open1216.05036arXiv1002.1749OpenAlexW1977603542MaRDI QIDQ536221FDOQ536221

Authors: Zbigniew Lonc, Mirosław Truszczyński 

Publication date: 16 May 2011

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

Abstract: Let R be an equivalence relation on graphs. By the strengthening of R we mean the relation R' such that graphs G and H are in the relation R' if for every graph F, the union of the graphs G and F is in the relation R with the union of the graphs H and F. We study strengthenings of equivalence relations on graphs. The most important case that we consider concerns equivalence relations defined by graph properties. We obtain results on the strengthening of equivalence relations determined by the properties such as being a k-connected graph, k-colorable, hamiltonian and planar.

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

Recommendations

• scientific article; zbMATH DE number 4023332
• Equality of graphs up to complementation
• scientific article
• scientific article; zbMATH DE number 819122
• scientific article; zbMATH DE number 3895108

zbMATH Keywords

computational complexityconnectivitygeneral graph propertiesstrong equivalence of graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15) Graph designs and isomorphic decomposition (05C51)

Cites Work

• Title not available (Why is that?)
• Strong equivalence made easy: nested expressions and weight constraints
• Strongly equivalent logic programs
• Title not available (Why is that?)
• Characterizing strong equivalence for argumentation frameworks
• Title not available (Why is that?)
• Semantical characterizations and complexity of equivalences in answer set programming
• A common view on strong, uniform, and other notions of equivalence in answer-set programming

Cited In (7)

• Title not available (Why is that?)
• A general notion of equivalence for abstract argumentation
• Extending partial isomorphisms of graphs
• Characterizing strong equivalence for argumentation frameworks
• Title not available (Why is that?)
• Bundling all shortest paths
• On three extensions of equimatchable graphs

This page was built for publication: On graph equivalences preserved under extensions

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