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

Cartesian productcombinatorial problemscomplementary prismcomplementary productgraph algorithms

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

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

• \(k\)-tuple total domination in complementary prisms
• 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

Cited in

(17)

• On the geodetic number 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
• Perfect matching cuts partitioning a graph into complementary subgraphs
• Cycles in complementary prisms
• Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism
• A polynomial time algorithm for geodetic hull number for complementary prisms
• Algorithm to check the existence of \(H\) for a given \(G\) such that \(A(G)A(H)\) is graphical
• Complexity properties of complementary prisms
• The complementary product of two 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
• Viral Marketing for Complementary Products
• Partitioning a graph into complementary subgraphs
• Partitioning a graph into complementary subgraphs
• The core of a complementary prism
• Perfect matching cuts partitioning a graph into complementary subgraphs

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)