Boxicity of line graphs

The boxicity of a graph H, denoted by , is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper we show that for a line graph G of a multigraph, , where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, . For the d-dimensional hypercube Q_d, we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).     

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

Boxicity of series-parallel graphs

We show that there exist series-parallel graphs with boxicity 3.     

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K₄, then . In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless G is isomorphic to K₄ (in which case its boxicity is 1).     

Boxicity of Graphs on Surfaces

The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs G _i  = (V, E _i ), 1 ≤ i ≤ k, such that ${E = E_1 \cap \cdots \cap E_k}$ . Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.     

Chordal Bipartite Graphs with High Boxicity

The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity.     

An upper bound for Cubicity in terms of Boxicity

An axis-parallel b-dimensional box is a Cartesian product R₁×R₂×?×R_b where each R_i (for 1≤i≤b) is a closed interval of the form [a_i,b_i] on the real line. The boxicity of any graph G, is the minimum positive integer b such that G can be represented as the intersection graph of axis-parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product R₁×R₂×?×R_b, where each R_i (for 1≤i≤b) is a closed interval of the form [a_i,a_i+1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by ). In this paper we prove that , where n is the number of vertices in the graph. We also show that this upper bound is tight.Some immediate consequences of the above result are listed below:

1.

Planar graphs have cubicity at most 3⌈log₂n⌉.

2.

Outer planar graphs have cubicity at most 2⌈log₂n⌉.

3.

Any graph of treewidth tw has cubicity at most (tw+2)⌈log₂n⌉. Thus, chordal graphs have cubicity at most (ω+1)⌈log₂n⌉ and circular arc graphs have cubicity at most (2ω+1)⌈log₂n⌉, where ω is the clique number.

The above upper bounds are tight, but for small constant factors.     

Powers of plus-operators

Dedicated to the good memory of Yuryi Lvovich Shmulian.     

Powers of commutators

Any element of a finite group that generates the same cyclic subgroup as some commutator, is itself a commutator. The paper presents a completely elementary proof of this fact, whereas previous proofs depend on character theory.     

Powers and Exponents

<正>In mathematics,a power is represented with a base number and an exponent.The base number tells what number is being multiplied.The exponent,a small number written above and to the right of the base number,tells how many times the base number is being multiplied.Today we will talk about     

Dirac分布的幂

本文结合发散积分的正则化方法及复阶导数概念,在基础空间D(Rⁿ)的某些子空间上,给出了Dirac分布的一些幂δ^α(x)及δ(x)ln δ(x)的确定意义。     

Powers of ordered sets

Recently there has been significant progress in the study of powers of ordered sets. Much of this work has concerned cancellation laws for powers and uses these two steps. First, logarithmic operators are introduced to transform cancellation problems for powers into questions involving direct product decompositions. Second, refinement theorems for direct product decompositions are brought to bear. Here we present two results with the aim of highlighting these steps.Supported by NSF grant MCS 83-02054     

Powers of Renewal Sequences

If (u_n) is a renewal sequence, then so is () for any > 1.     

Powers of

We prove that the Cech-Stone remainder of the integers, , maps onto its square if and only if there is a nontrivial map between two of its different powers, finite or infinite. We also prove that every compact space that maps onto its own square maps onto its own countable infinite product.

     

Choosability of Powers of Circuits

 It is proved that ch(G)=χ(G) if G=C _n ^p , the pth power of the circuit graph C _n , or if G is a uniform inflation of such a graph. The proof uses the method of Alon and Tarsi. As a corollary, the (a : b)-choosability conjectures hold for all such graphs. Received: October 10, 2000 Final version received: November 8, 2001     

The Decomposition of Lie Powers

Let G be a group, F a field of prime characteristic p and Va finite-dimensional FG-module. Let L(V) denote the free Liealgebra on V regarded as an FG-submodule of the free associativealgebra (or tensor algebra) T(V). For each positive integerr, let L^r (V) and T^r (V) be the rth homogeneous components ofL(V) and T(V), respectively. Here L^r (V) is called the rth Liepower of V. Our main result is that there are submodules B₁,B₂, ... of L(V) such that, for all r, B_r is a direct summandof T^r(V) and, whenever m 0 and k is not divisible by p, themodule is the direct sum of , . Thus every Lie power is a direct sum of Lie powers of p-powerdegree. The approach builds on an analysis of T^r (V) as a bimodulefor G and the Solomon descent algebra. 2000 Mathematics SubjectClassification 17B01 (primary), 20C07, 20C20 (secondary).