The boxicity of a graph G is the minimum dimension b such that G is representable as the intersection graph of axis-parallel boxes in the b-dimensional space. When the boxes are restricted to be axis-parallel b-dimensional cubes, the minimum dimension b required to represent G is called the cubicity of G. In this paper we show that cubicity(H-d) <=, 2d, where Hd is the d-dimensional hypercube. (The d-dimensional hypercube is the graph on 2d vertices which corresponds to the 2(d) d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate.) We also show that cubicity(H-d) >= (d - 1)/(log d). We also show that (1) cubicity(G) >= (log alpha)/(log(D + 1)), (2) cubicity(G) >= (log n - log omega)/(log D), where alpha, omega, D and n denote the stability number, the clique number, the diameter and the number of vertices of G. As consequences of these lower bounds we provide lower bounds for the cubicity of planar graphs, bipartite graphs, triangle-free graphs, etc., in terms of their diameter and the number of vertices. (c) 2005 Elsevier B.V. All rights reserved.

Chandran, L.S., Mannino, C., & Oriolo, G. (2005). On the cubicity of certain graphs. INFORMATION PROCESSING LETTERS, 94(3), 113-118 [10.1016/j.ipl.2005.01.001].

On the cubicity of certain graphs

ORIOLO, GIANPAOLO
2005

Abstract

The boxicity of a graph G is the minimum dimension b such that G is representable as the intersection graph of axis-parallel boxes in the b-dimensional space. When the boxes are restricted to be axis-parallel b-dimensional cubes, the minimum dimension b required to represent G is called the cubicity of G. In this paper we show that cubicity(H-d) <=, 2d, where Hd is the d-dimensional hypercube. (The d-dimensional hypercube is the graph on 2d vertices which corresponds to the 2(d) d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate.) We also show that cubicity(H-d) >= (d - 1)/(log d). We also show that (1) cubicity(G) >= (log alpha)/(log(D + 1)), (2) cubicity(G) >= (log n - log omega)/(log D), where alpha, omega, D and n denote the stability number, the clique number, the diameter and the number of vertices of G. As consequences of these lower bounds we provide lower bounds for the cubicity of planar graphs, bipartite graphs, triangle-free graphs, etc., in terms of their diameter and the number of vertices. (c) 2005 Elsevier B.V. All rights reserved.
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - Ricerca Operativa
English
Boxicity; Clique number; Combinatorial problems; Cubicity; Hypercube; Stability number
Chandran, L.S., Mannino, C., & Oriolo, G. (2005). On the cubicity of certain graphs. INFORMATION PROCESSING LETTERS, 94(3), 113-118 [10.1016/j.ipl.2005.01.001].
Chandran, L; Mannino, C; Oriolo, G
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/39124
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 9
social impact