共查询到20条相似文献,搜索用时 15 毫秒
1.
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 Rk. 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 Qd, 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). 相似文献
2.
A k-dimensional box is a Cartesian product R
1 × · · · × 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. 相似文献
3.
We show that there exist series-parallel graphs with boxicity 3. 相似文献
4.
A k-dimensional box is the Cartesian product R1×R2×?×Rk where each Ri 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 K4, 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 K4 (in which case its boxicity is 1). 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
9.
An axis-parallel b-dimensional box is a Cartesian product R1×R2×?×Rb where each Ri (for 1≤i≤b) is a closed interval of the form [ai,bi] 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 R1×R2×?×Rb, where each Ri (for 1≤i≤b) is a closed interval of the form [ai,ai+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⌈log2n⌉.
- 2.
- Outer planar graphs have cubicity at most 2⌈log2n⌉.
- 3.
- Any graph of treewidth tw has cubicity at most (tw+2)⌈log2n⌉. Thus, chordal graphs have cubicity at most (ω+1)⌈log2n⌉ and circular arc graphs have cubicity at most (2ω+1)⌈log2n⌉, where ω is the clique number.
10.
11.
Dedicated to the good memory of Yuryi Lvovich Shmulian. 相似文献
12.
《Operations Research Letters》2023,51(1):17-20
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. 相似文献
13.
14.
《中学生数学》2018,(2)
<正>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 相似文献
15.
16.
Dwight Duffus 《Order》1984,1(1):83-92
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 相似文献
17.
Powers of Renewal Sequences 总被引:1,自引:0,他引:1
If (un) is a renewal sequence, then so is () for any > 1. 相似文献
18.
Ilijas Farah 《Proceedings of the American Mathematical Society》2002,130(4):1243-1246
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.
19.
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 相似文献
20.
The Decomposition of Lie Powers 总被引:1,自引:0,他引:1
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 Lr (V) and Tr (V) be the rth homogeneous components ofL(V) and T(V), respectively. Here Lr (V) is called the rth Liepower of V. Our main result is that there are submodules B1,B2, ... of L(V) such that, for all r, Br is a direct summandof Tr(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 Tr (V) as a bimodulefor G and the Solomon descent algebra. 2000 Mathematics SubjectClassification 17B01 (primary), 20C07, 20C20 (secondary). 相似文献