Recognizing some complementary products

DOI10.1016/J.TCS.2013.11.006zbMATH Open1279.05062OpenAlexW2021788611MaRDI QIDQ389934FDOQ389934

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

Recommendations

• The complementary product of two graphs
• Complexity properties of complementary prisms
• Partial complementation of graphs
• Partitioning a graph into complementary subgraphs
• Subgraph complementation

zbMATH Keywords

graph algorithmsCartesian productcombinatorial problemscomplementary prismcomplementary product

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

• On the geodetic number of complementary prisms
• Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
• Viral Marketing for Complementary Products
• Cycles in complementary prisms
• Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms
• A polynomial time algorithm for geodetic hull number for complementary prisms
• Perfect matching cuts partitioning a graph into complementary subgraphs
• The core of a complementary prism
• Partitioning a graph into complementary subgraphs
• Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism
• Complexity properties of complementary prisms
• Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs
• Open-independent, open-locating-dominating sets in complementary prism graphs

This page was built for publication: Recognizing some complementary products

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