Recognizing some complementary products

DOI10.1016/J.TCS.2013.11.006MaRDI QIDQ389934zbMATH OpenOpenAlexFDO

Authors 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

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)

Recommendations

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

Cites work

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

Cited in

(15)

• 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
• The complementary product of two graphs
• Algorithm to check the existence of \(H\) for a given \(G\) such that \(A(G)A(H)\) is graphical
• Remarks on \(k\)-clique, \(k\)-independent set and 2-contamination in complementary prisms
• Perfect matching cuts partitioning a graph into complementary subgraphs
• A polynomial time algorithm for geodetic hull number for complementary prisms
• 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)