Recognizing some complementary products

DOI10.1016/j.tcs.2013.11.006zbMath1279.05062OpenAlexW2021788611MaRDI QIDQ389934

Márcia R. Cappelle, Dieter Rautenbach, Lucia Draque Penso

Publication date: 22 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.11.006

zbMATH Keywords

combinatorial problemsgraph algorithmsCartesian productcomplementary prismcomplementary product

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)

Related Items (11)

A polynomial time algorithm for geodetic hull number for complementary prisms ⋮ Open-independent, open-locating-dominating sets in complementary prism graphs ⋮ Perfect matching cuts partitioning a graph into complementary subgraphs ⋮ The core of a complementary prism ⋮ On the geodetic number of complementary prisms ⋮ Complexity properties of complementary prisms ⋮ Partitioning a graph into complementary subgraphs ⋮ Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs ⋮ Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms ⋮ Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs ⋮ Cycles in complementary prisms

Cites Work

• \(k\)-tuple total domination in complementary prisms
• Factoring a graph in polynomial time
• Graph multiplication
• Recognizing Cartesian products in linear time
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Cartesian graph factorization at logarithmic cost per edge
• Product graph representations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Recognizing some complementary products