On graph equivalences preserved under extensions

DOI10.1016/J.DISC.2011.02.029MaRDI QIDQ536221zbMATH OpenOpenAlexFDO

Authors Zbigniew Lonc, Mirosław Truszczyński

Publication date 16 May 2011

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityconnectivitygeneral graph propertiesstrong equivalence of graphs

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

• A common view on strong, uniform, and other notions of equivalence in answer-set programming
• Characterizing strong equivalence for argumentation frameworks
• scientific article; zbMATH DE number 3967882 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Semantical characterizations and complexity of equivalences in answer set programming
• Strong equivalence made easy: nested expressions and weight constraints
• Strongly equivalent logic programs

Cited in

(8)

• Extending partial isomorphisms of graphs
• Bundling all shortest paths
• A general notion of equivalence for abstract argumentation
• scientific article; zbMATH DE number 6000779 (Why is no real title available?)
• scientific article; zbMATH DE number 4210192 (Why is no real title available?)
• scientific article; zbMATH DE number 4023332 (Why is no real title available?)
• Characterizing strong equivalence for argumentation frameworks
• 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)