Let c (n) be the maximum number of cycles in an outerplanar graph with n vertices. We show that lim c (n)1 / n exists and equals β = 1.502837 ..., where β is a constant related to the recurrence xn + 1 = 1 + xn2, x0...
详细信息
This paper deals with single-machine scheduling problems with decreasing linear deterioration, i.e., jobs whose processing times are a decreasing function of their starting times. In addition, the jobs are related by ...
详细信息
This paper deals with single-machine scheduling problems with decreasing linear deterioration, i.e., jobs whose processing times are a decreasing function of their starting times. In addition, the jobs are related by parallel chains and a series-parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan, polynomial algorithms exist. (C) 2009 Elsevier Ltd. All rights reserved.
Assume that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a demand. Each demand vertex can receive "power" from at most one supp...
详细信息
Assume that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a demand. Each demand vertex can receive "power" from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C has exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in C. If G does not have such a partition, one wishes to partition G into connected components so that each component C either has no supply vertex or has exactly one supply vertex whose supply is no less than the sum of demands in C, and wishes to maximize the sum of demands in all components with supply vertices. We deal with such a maximization problem, which is NP-hard even for trees and strongly NP-hard for general graphs. In this paper, we show that the problem can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees - that is, graphs with bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.
It is proved that if G is a plane embedding of a K-4-minor-free graph with maximum degree Delta, then G is entirely 7-choosable if Delta = 5: that is, if every vertex, edge and face of G is given a list of max{7, Delt...
详细信息
It is proved that if G is a plane embedding of a K-4-minor-free graph with maximum degree Delta, then G is entirely 7-choosable if Delta <= 4 and G is entirely (Delta + 2)-choosable if Delta >= 5: that is, if every vertex, edge and face of G is given a list of max{7, Delta + 2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if G is a plane embedding of a K-2,K-3-minor-free graph or a ((K) over bar (2) + (K-1 boolean OR K-2))-minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely (6 + 4)colourable, holds if C is a plane embedding of a K4-minor-free graph, a K-2,K-3-minor-free graph or a ((K) over bar (2) + (K-1 boolean OR K-2))-minor-free graph. (C) 2008 Elsevier B.V. All rights reserved.
Motivated by previous results on distance constrained labelings and coloring of squares of K-4-minor free graphs, we show that for every p >= q >= 1 there exists Delta(0) such that every K-4-minor free graph G w...
详细信息
Motivated by previous results on distance constrained labelings and coloring of squares of K-4-minor free graphs, we show that for every p >= q >= 1 there exists Delta(0) such that every K-4-minor free graph G with maximum degree Delta >= Delta(0) has an L(p, q)-labeling of span at most qleft perpendicular3 Delta(G)/2right perpendicular. The obtained bound is the best possible. (C) 2008 Elsevier B.V. All rights reserved.
Refining a bound by Lih, Wang and Zhu, we prove that if the square G(2) of a K-4-minor-free graph G with maximum degree Delta >= 6 does not contain a complete subgraph on [3/2 Delta] + 1 vertices, then G(2) is [3/2...
详细信息
Refining a bound by Lih, Wang and Zhu, we prove that if the square G(2) of a K-4-minor-free graph G with maximum degree Delta >= 6 does not contain a complete subgraph on [3/2 Delta] + 1 vertices, then G(2) is [3/2 Delta]-colorable. (C) 2009 Elsevier B.V. All rights reserved.
In an orthogonal drawing of a planar graph G, each vertex is drawn as a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common...
详细信息
In an orthogonal drawing of a planar graph G, each vertex is drawn as a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. A bend is a point where an edge changes its direction. A drawing of G is called an optimal orthogonal drawing if the number of bends is minimum among all orthogonal drawings of G. In this paper we give an algorithm to find an optimal orthogonal drawing of any given series-parallel graph of the maximum degree at most three. Our algorithm takes linear time, while the previously known best algorithm takes cubic time. Furthermore, our algorithm is much simpler than the previous one. We also obtain a best possible upper bound on the number of bends in an optimal drawing.
To suppress a vertex v in a finite graph G means to delete it and add an edge from a to b if a, b are distinct nonadjacent vertices which formed the neighborhood of v. Let G - -x be the graph obtained from G - x by su...
详细信息
To suppress a vertex v in a finite graph G means to delete it and add an edge from a to b if a, b are distinct nonadjacent vertices which formed the neighborhood of v. Let G - -x be the graph obtained from G - x by suppressing vertices of degree at most 2 as long as it is possible;this is proven to be well defined. Our main result states that every 3-connected graph G has a vertex x such that G - -x is 3-connected unless G is isomorphic to K-3,(3), K-2 x K-3, or to a wheel K-1 * C-l for some l >= 3. This leads to a generator theorem for 3-connected graphs in terms of seriesparallel extensions. (c) 2007 Wiley Periodicals, Inc.
A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping f from V(G) to V(H), that is f (x)f (y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the ...
详细信息
A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping f from V(G) to V(H), that is f (x)f (y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the minimum order of an oriented graph H such that G has a homomorphism to H. In this paper, we determine the oriented chromatic number of the class of partial 2-trees for every girth g >= 3. We also give an upper bound for the oriented chromatic number of planar graphs with girth at least 11. (c) 2008 Elsevier B.V. All rights reserved.
graph G is called cyclically orientable (CO) if it admits an orientation in which every simple chordless cycle is cyclically oriented. This family of graphs was introduced by Barot et al. [Cluster algebras of finite t...
详细信息
graph G is called cyclically orientable (CO) if it admits an orientation in which every simple chordless cycle is cyclically oriented. This family of graphs was introduced by Barot et al. [Cluster algebras of finite type and positive symmetrizable matrices, J. London Math. Soc. (3) 73 (2006) 545-564]. The authors obtained several nice characterizations of CO-graphs, being motivated primarily by their applications in cluster algebras. Here we obtain several new characterizations that provide algorithms for recognizing CO-graphs and obtaining their cyclic orientations in linear time. We show that the edge maximal CO-graphs are 2-trees;that is, G = (V, E) is a 2-tree if and only if G is CO and G' = (V, E') is not CO whenever E is a proper subset of E'. (c) 2007 Elsevier B.V. All rights reserved.
暂无评论