Boxicity and Cubicity of product graphs

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Standard

Boxicity and Cubicity of product graphs. / Chandran, Sunil L.; Imrich, Wilfried; Mathew, Rogers et al.
in: European journal of combinatorics, Jahrgang 48.2015, Nr. August, 2015, S. 100 - 109.

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Harvard

Chandran, SL, Imrich, W, Mathew, R & Rajendraprasad, D 2015, 'Boxicity and Cubicity of product graphs', European journal of combinatorics, Jg. 48.2015, Nr. August, S. 100 - 109. https://doi.org/10.1016/j.ejc.2015.02.013

APA

Chandran, S. L., Imrich, W., Mathew, R., & Rajendraprasad, D. (2015). Boxicity and Cubicity of product graphs. European journal of combinatorics, 48.2015(August), 100 - 109. https://doi.org/10.1016/j.ejc.2015.02.013

Vancouver

Chandran SL, Imrich W, Mathew R, Rajendraprasad D. Boxicity and Cubicity of product graphs. European journal of combinatorics. 2015;48.2015(August):100 - 109. Epub 2015 Mär 15. doi: 10.1016/j.ejc.2015.02.013

Author

Chandran, Sunil L. ; Imrich, Wilfried ; Mathew, Rogers et al. / Boxicity and Cubicity of product graphs. in: European journal of combinatorics. 2015 ; Jahrgang 48.2015, Nr. August. S. 100 - 109.

Bibtex - Download

@article{b48f4b721a8c4558b3dde80a26619bfa,
title = "Boxicity and Cubicity of product graphs",
abstract = "The boxicity (cubicity) of a graph is the minimum natural number such that can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in . In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of , of the boxicity and the cubicity of the th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the th Cartesian power of any given finite graph is, respectively, in and . On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products.",
keywords = "graphentheorie, kombinatorik",
author = "Chandran, {Sunil L.} and Wilfried Imrich and Rogers Mathew and Deepak Rajendraprasad",
year = "2015",
doi = "10.1016/j.ejc.2015.02.013",
language = "English",
volume = "48.2015",
pages = "100 -- 109",
journal = "European journal of combinatorics",
issn = "0195-6698",
publisher = "Academic Press Inc.",
number = "August",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - Boxicity and Cubicity of product graphs

AU - Chandran, Sunil L.

AU - Imrich, Wilfried

AU - Mathew, Rogers

AU - Rajendraprasad, Deepak

PY - 2015

Y1 - 2015

N2 - The boxicity (cubicity) of a graph is the minimum natural number such that can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in . In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of , of the boxicity and the cubicity of the th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the th Cartesian power of any given finite graph is, respectively, in and . On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products.

AB - The boxicity (cubicity) of a graph is the minimum natural number such that can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in . In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of , of the boxicity and the cubicity of the th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the th Cartesian power of any given finite graph is, respectively, in and . On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products.

KW - graphentheorie, kombinatorik

U2 - 10.1016/j.ejc.2015.02.013

DO - 10.1016/j.ejc.2015.02.013

M3 - Article

VL - 48.2015

SP - 100

EP - 109

JO - European journal of combinatorics

JF - European journal of combinatorics

SN - 0195-6698

IS - August

ER -