{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T00:14:08Z","timestamp":1698970448411},"reference-count":24,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T00:00:00Z","timestamp":1291161600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2010,12]]},"abstract":"Abstract<\/jats:title>Let G<\/jats:italic>(V, E<\/jats:italic>) be a simple, undirected graph where V<\/jats:italic> is the set of vertices and E<\/jats:italic> is the set of edges. A b<\/jats:italic>\u2010dimensional cube is a Cartesian product I<\/jats:italic>1<\/jats:sub>\u00d7I<\/jats:italic>2<\/jats:sub>\u00d7\u00b7\u00b7\u00b7\u00d7I<\/jats:italic>b<\/jats:italic><\/jats:sub>, where each I<\/jats:italic>i<\/jats:italic><\/jats:sub> is a closed interval of unit length on the real line. The cubicity<\/jats:italic> of G<\/jats:italic>, denoted by cub(G<\/jats:italic>), is the minimum positive integer b<\/jats:italic> such that the vertices in G<\/jats:italic> can be mapped to axis parallel b<\/jats:italic>\u2010dimensional cubes in such a way that two vertices are adjacent in G<\/jats:italic> if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line\u2014i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S<\/jats:italic>(m<\/jats:italic>) denotes a star graph on m<\/jats:italic>+1 nodes. We define claw number<\/jats:italic> \u03c8(G<\/jats:italic>) of the graph to be the largest positive integer m<\/jats:italic> such that S<\/jats:italic>(m<\/jats:italic>) is an induced subgraph of G<\/jats:italic>. It can be easily shown that the cubicity of any graph is at least \u2308log2<\/jats:sub>\u03c8(G<\/jats:italic>)\u2309. In this article, we show that for an interval graph G<\/jats:italic> \u2308log2<\/jats:sub>\u03c8(G<\/jats:italic>)\u2309\u2a7dcub(G<\/jats:italic>)\u2a7d\u2308log2<\/jats:sub>\u03c8(G<\/jats:italic>)\u2309+2. It is not clear whether the upper bound of \u2308log2<\/jats:sub>\u03c8(G<\/jats:italic>)\u2309+2 is tight: till now we are unable to find any interval graph with cub(G<\/jats:italic>)>\u2308log2<\/jats:sub>\u03c8(G<\/jats:italic>)\u2309. We also show that for an interval graph G<\/jats:italic>, cub(G<\/jats:italic>)\u2a7d\u2308log2<\/jats:sub>\u03b1\u2309, where \u03b1 is the independence number of G<\/jats:italic>. Therefore, in the special case of \u03c8(G<\/jats:italic>)=\u03b1, cub(G<\/jats:italic>) is exactly \u2308log2<\/jats:sub>\u03b12<\/jats:sub>\u2309. The concept of cubicity can be generalized by considering boxes instead of cubes. A b<\/jats:italic>\u2010dimensional box is a Cartesian product I<\/jats:italic>1<\/jats:sub>\u00d7I<\/jats:italic>2<\/jats:sub>\u00d7\u00b7\u00b7\u00b7\u00d7I<\/jats:italic>b<\/jats:italic><\/jats:sub>, where each I<\/jats:italic>i<\/jats:italic><\/jats:sub> is a closed interval on the real line. The boxicity<\/jats:italic> of a graph, denoted box(G<\/jats:italic>), is the minimum k<\/jats:italic> such that G<\/jats:italic> is the intersection graph of k<\/jats:italic>\u2010dimensional boxes. It is clear that box(G<\/jats:italic>)\u2a7dcub(G<\/jats:italic>). From the above result, it follows that for any graph G<\/jats:italic>, cub(G<\/jats:italic>)\u2a7dbox(G<\/jats:italic>)\u2308log2<\/jats:sub>\u03b1\u2309. \u00a9 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323\u2013333, 2010<\/jats:p>","DOI":"10.1002\/jgt.20483","type":"journal-article","created":{"date-parts":[[2010,1,22]],"date-time":"2010-01-22T20:32:29Z","timestamp":1264192349000},"page":"323-333","source":"Crossref","is-referenced-by-count":2,"title":["Cubicity of interval graphs and the claw number"],"prefix":"10.1002","volume":"65","author":[{"given":"Abhijin","family":"Adiga","sequence":"first","affiliation":[]},{"given":"L. Sunil","family":"Chandran","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2010,12]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.05.004"},{"key":"e_1_2_1_3_2","first-page":"333","article-title":"Problem 56","volume":"1","author":"Bielecki A.","year":"1948","journal-title":"Colloq Math"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-008-0830-8"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.08.002"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.04.011"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.12.004"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.10.011"},{"key":"e_1_2_1_9_2","unstructured":"M. B.Cozzens Higher and multi\u2010dimensional analogues of interval graphs Ph.D. thesis Department of Mathematics Rutgers University New Brunswick NJ 1981."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90077-X"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90057-6"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_2_1_13_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/b95547","volume-title":"LATIN","author":"Gardi F.","year":"2004"},{"key":"e_1_2_1_14_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"e_1_2_1_15_2","unstructured":"T. F.Havel The combinatorial distance geometry approach to the calculation of molecular conformation. Ph.D. thesis University of California Berkeley1982."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90012-3"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/342\/06137"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90143-0"},{"key":"e_1_2_1_19_2","volume-title":"Threshold Graphs and Related Topics","author":"Mahadev N. V. R.","year":"1995"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.01.004"},{"key":"e_1_2_1_21_2","first-page":"301","volume-title":"On the Boxicity and Cubicity of a Graph","author":"Roberts F. S.","year":"1969"},{"key":"e_1_2_1_22_2","unstructured":"E. R.Scheinerman Intersection classes and multiple intersection parameters Ph.D. thesis Princeton University 1984."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90061-4"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90137-7"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0603036"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.20483","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.20483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,2]],"date-time":"2023-11-02T10:59:54Z","timestamp":1698922794000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.20483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1002\/jgt.20483"],"URL":"http:\/\/dx.doi.org\/10.1002\/jgt.20483","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}
