On the cubicity of certain graphs

DOI10.1016/j.ipl.2005.01.001zbMath1186.05090OpenAlexW1986528255MaRDI QIDQ1041732

L. Sunil Chandran, Gianpaolo Oriolo, Carlo Mannino

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.01.001

zbMATH Keywords

hypercubecombinatorial problemsstability numberclique numberboxicitycubicity

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Cubicity and bandwidth ⋮ Upper bound on cubicity in terms of boxicity for graphs of low chromatic number ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ On the cubicity of bipartite graphs ⋮ The cubicity of hypercube graphs ⋮ Cubicity, boxicity, and vertex cover ⋮ On the Cubicity of AT-Free Graphs and Circular-Arc Graphs ⋮ On the cubicity of interval graphs ⋮ Boxicity and cubicity of product graphs

Cites Work

• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Grid intersection graphs and boxicity
• Interval representations of planar graphs
• Poset boxicity of graphs
• A note on circular dimension
• Optimal packing and covering in the plane are NP-complete
• The circular dimension of a graph
• A special planar satisfiability problem and a consequence of its NP- completeness
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• The Complexity of the Partial Order Dimension Problem
• Extremal Values of the Interval Number of a Graph
• When the cartesian product of directed cycles is Hamiltonian
• Unnamed Item
• Unnamed Item
• Unnamed Item