A local characterization of bounded clique-width for line graphs

It is shown that a line graph G has clique-width at most 8k+4 and NLC-width at most 4k+3, if G contains a vertex whose non-neighbours induce a subgraph of clique-width k or NLC-width k in G, respectively. This relation implies that co-gem-free line graphs have clique-width at most 14 and NLC-width at most 7.It is also shown that in a line graph the neighbours of a vertex induce a subgraph of clique-width at most 4 and NLC-width at most 2.     

Isometric immersions of tori into R3 with given mean curvature

It is known that a compact Riemannian surface can admit at most two (2) geometrically distinct, i. e., non-congruent isometric immersions into R ³ with given non-constant mean curvature. If the genus is zero, then there is at most one such immersion. Here, we show that there is at most one such immersion in each of the following cases for surfaces of genus one: 1) there exists a point p such that (H ² ? K)(p) = 0, where K is the curvature of the Riemannian metric and H is the given non-constant mean curvature (umbilic point); 2) the surface is a surface of revolution; 3) the surface is a tube formed by moving a circle in such a way that its center describes a smooth plane curve and its plane is constantly perpendicular to this curve. We also indicate the difficulties as to why the so-far existing methodologies cannot give a clear-cut answer to the question if it is possible to reduce the at most two immersions to at most one for any compact Riemannian surface of genus greater than zero.     

Avoiding multiple entry arrays

In this paper we consider the problem of avoiding arrays with more than one entry per cell. An n × n array on n symbols is said to be if an n × n latin square, on the same symbols, can be found which differs from the array in every cell. Our first result is for chessboard squares with at most two entries per black cell. We show that if k ≥ 1 and C is a 4k × 4k chessboard square on symbols 1, 2, …, 4k in which every black cell contains at most two symbols and every symbol appears at most once in every row and column, then C is avoidable. Our main result is for squares with at most two entries in any cell and answers a question of Hilton. If k 3240 and F is a 4k × 4k array on 1, 2,…, 4k in which every cell contains at most two symbols and every symbol appears at most twice in every row and column, then F is avoidable. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 257–266, 1997     

Selections and hyperspaces of finite sets

It is demonstrated that the hyperspace of at most (n+1)-point sets has a Vietoris continuous selection if both the hyperspace of at most n-point sets and that of exactly (n+1)-point sets have Vietoris continuous selections. This result is applied to demonstrate that the hyperspace of at most (2n+2)-point sets has a Vietoris continuous selection provided that one of at most (2n+1)-point sets has such a selection. This settles some open questions.     

Cycle Cover Ratio of Regular Matroids

A cycle in a matroid is a disjoint union of circuits. This paper proves that every regular matroidM without coloops has a set S of cycles whose union is E(M) such that every element is in at most three of the cycles in S. It follows immediately from this that, on average, each element of M is in at most three members of the cycle cover S. This improves on a 1989 result of Jamshy and Tarsi who proved that there is a cycle cover for which this average is at most 4, and conjectured that a cycle cover exists for which the average is at most 2.     

Prime Divisibility Among Degrees of Solvable Groups

Abstract

Let G be a finite, nonabelian, solvable group. Following work by D. Benjamin, we conjecture that some prime must divide at least a third of the irreducible character degrees of G. Benjamin was able to show the conjecture is true if all primes divide at most 3 degrees. We extend this result by showing if primes divide at most 4 degrees, then G has at most 12 degrees. We also present an example showing our result is best possible.     

A trajectory in ℝ<Superscript>3</Superscript> concealed from observers

In the problem of tracking an object moving in ?³ by observers, the most concealed trajectory is characterized under the condition that the object is at any time visible to at most two observers.     

Improved bound for the dimension of posets of treewidth two

Joret et al. proved that posets with cover graphs of treewidth at most 2 have dimension at most 1276. Their proof is long and very complex. We give a short and much simpler proof that the dimension of such posets is at most 12.     

Groups with small deviation for non-subnormal subgroups

We introduce the notion of the non-subnormal deviation of a group G. If the deviation is 0 then G satisfies the minimal condition for nonsubnormal subgroups, while if the deviation is at most 1 then G satisfies the so-called weak minimal condition for such subgroups (though the converse does not hold). Here we present some results on groups G that are either soluble or locally nilpotent and that have deviation at most 1. For example, a torsion-free locally nilpotent with deviation at most 1 is nilpotent, while a Baer group with deviation at most 1 has all of its subgroups subnormal.      

Bounds for rectilinear crossing numbers

A rectilinear drawing of a graph is one where each edge is drawn as a straight-line segment, and the rectilinear crossing number of a graph is the minimum number of crossings over all rectilinear drawings. We describe, for every integer k ≥ 4, a class of graphs of crossing number k, but unbounded rectilinear crossing number. This is best possible since the rectilinear crossing number is equal to the crossing number whenever the latter is at most 3. Further, if we consider drawings where each edge is drawn as a polygonal line segment with at most one break point, then the resulting crossing number is at most quadratic in the regular crossing number. © 1993 John Wiley & Sons, Inc.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Ohba’s conjecture for graphs with independence number five

Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.     

On-Line Potato-Sack Algorithm Efficient for Packing Into Small Boxes

The aim of this paper is to show an on-line algorithm for packing sequences of d-dimensional boxes of edge lengths at most 1 in a box of edge lengths at least 1. It is more efficient than a previously known algorithm in the case when packing into a box with short edges. In particular, our method permits packing every sequence of boxes of edge lengths at most 1 and of total volume at most in the unit cube. For packing sequences of convex bodies of diameters at most 1 the result is d! times smaller.     

Packing and Covering Triangles in K 4-free Planar Graphs

We show that every K ₄-free planar graph with at most ν edge-disjoint triangles contains a set of at most ${\frac32\nu}$ edges whose removal makes the graph triangle-free. Moreover, equality is attained only when G is the edge-disjoint union of 5-wheels plus possibly some edges that are not in triangles. We also show that the same statement is true if instead of planar graphs we consider the class of graphs in which each edge belongs to at most two triangles. In contrast, it is known that for any c?<?2 there are K ₄-free graphs with at most ν edge-disjoint triangles that need more than cν edges to cover all triangles.     

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

Bounding graph diameters of solvable groups

We define a graph associated with a group G by letting nontrivial degrees be the vertices, and placing an edge between distinct degrees if they are not relatively prime. Using results in the literature, it is not difficult to show that when G is solvable and the graph is connected, its diameter is at most 4. Recent results suggest that this bound might be obtained. We show that in fact this diameter is at most 3, which is best possible.     

Bichromatic Lines with Few Points

Given a set of n blue and n red points in the plane, not all on a line, it is shown that there exists a bichromatic line passing through at most two blue points and at most two red points. There does not necessarily exist a line passing through precisely one blue and one red point. This result is extended to the case when the number of blue and red points is not the same.     

Extremal graphs of diameter 4

The object of this paper is to determine the minimum possible number of edges for a graph of order n and diameter at most four having the property that by suppressing any vertex the subgraph obtained has diameter at most λ ≥ 4. Results for λ ≥ 6 will be proved.     

Presentations of m-Complexity at Most 1 Defining the Trivial Group

A family of presentations of m-complexity at most 1 defining the trivial group and containing a Q**-equivalent copy of every balanced presentation of the trivial group with m-complexity at most 1 is described.