A note on sphere containment orders

Using the ideas of Scheinerman and Wierman [1] and of Hurlbert [2] we give a very short proof that the infinite order [2]×[3]× cannot be represented by containment of Euclidean balls in ad-dimensional space for anyd. Also we give representations of the orders [2]×[2]× and [3]×[3]×[3] by containment of circles in the plane.The work was financially supported by the Russian Foundation of Fundamental Research, Grant 93-011-1486     

A note on essentially convex orders

In this note, we determine precisely which partially ordered sets (posets) have the property that, whenever they occur as subposets of a larger poset, they occur there convexly, i.e., as convex subposets. As a corollary, we also determine which lattices have the property that, if they occur as sublattices of a finite distributive lattice L, then they also occur as closed intervals in L. Throughout, all sets will be finite.Dedicated to the memory of Ivan RivalReceived May 5, 2003; accepted in final form October 3, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Note on hypergraphs and sphere orders

We show that each partial order ≤ of height 2 can be represented by spheres in Euclidean space, where inclusion represents ≤. If each element has at most k elements under it, we can do this in 2k ? 1-dimensional space. This extends a result (and a method) of Scheinerman for the case k = 2. © 1993 John Wiley & Sons, Inc.     

A note on a homology sphere

Here we give a solution to a problem of Y.Matsumoto which was posed in ``Kirby's problem list"

     

A note on element orders and character codegrees

The result of this note is as follows. If a finite solvable group has an element of order m, then the group has an irreducible character whose codegree contains all prime divisors of m.     

A note on compact graphs

An undirected simple graph G is called compact iff its adjacency matrix A is such that the polytope S(A) of doubly stochastic matrices X which commute with A has integral-valued extremal points only. We show that the isomorphism problem for compact graphs is polynomial. Furthermore, we prove that if a graph G is compact, then a certain naive polynomial heuristic applied to G and any partner G′ decides correctly whether G and G′ are isomorphic or not. In the last section we discuss some compactness preserving operations on graphs.     

A note on assymmetric graphs

We describe a partition of the points of a graph which is related to its automorphism group. We then prove that the group of a tree is trivial if and only if this partition is the trivial one, and we formulate an algorithm which produces such a partition. Some application to graphs in general are also considered. Work supported in part by NSF Grant GP 11618.     

A note on k-cop-win graphs

The game of Cops and Robbers is a very well known game played on graphs. In this paper we will show that minimum order of a graph that needs $k$ cops to guarantee the robber’s capture is increasing in $k$.     

A note on n-extendable graphs

A graph G having a perfect matching is called n-extendable if every matching of size n of G can be extended to a perfect matching. In this note, we show that if G is an n-extendable nonbipartite graph, then G + e is (n - 1)-extendable for any edge e ? E(G). © 1992 John Wiley & Sons, Inc.     

A note on Ki-perfect graphs

Ki-perfect graphs are a special instance of F - G perfect graphs, where F and G are fixed graphs with F a partial subgraph of G. Given S, a collection of G-subgraphs of graph K, an F - G cover of S is a set of T of F-subgraphs of K such that each subgraph in S contains as a subgraph a member of T. An F - G packing of S is a subcollection S′? S such that no two subgraphs in S′ have an F-subgraph in common. K is F - G perfect if for all such S, the minimum cardinality of an F - G cover of S equals the maximum cardinality of an F - G packing of S. Thus K_i-perfect graphs are precisely K_i-1 - K_i perfect graphs. We develop a hypergraph characterization of F - G perfect graphs that leads to an alternate proof of previous results on K_i-perfect graphs as well as to a characterization of F - G perfect graphs for other instances of F and G.     

A note on degree-continuous graphs

The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.     

A note on perfect graphs

Let the lines of a complete graph be 3-colored so that no triangle gets 3 different colors. If two of these colors form perfect graphs then so does the third.     

A note on cospectral graphs

The notion of a (1, x) adjacency matrix is introduced, together with methods for dealing with it. It is shown that in many instances this adjacency matrix is superior to the usual (0, 1) adjacency matrix, and will distinguish cospectral pairs, when the latter will not. In those cases in which the (1, x) adjacency matrix fares no better than the (0, 1) adjacency matrix, a good deal can be said about the matrices by which the cospectral pairs are similar.     

A note on Cayley graphs

An example is given of a finite group A of order 144, with a generating set X = {x, y} such that x³ = y² = 1 and such that the Cayley graph C(A, X) has genus 4 and characteristic −6 (both of which are small relative to the order of A), although there is no short relator of the form (xy)^r with r < 12 or of the form [x, y]^r with r < 6. Accordingly this and other possible examples do not fit into a pattern suggested by [5.], 244–268).     

A note on graphs spanned by Eulerian graphs

We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP-complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at every node.     

A note on hypersurfaces in a sphere

We study the influence of a unit Killing vector field on the geometry of a hypersurface in the unit sphere. The combination of the Killing vector field on the hypersurface and the conformal vector field on the ambient sphere triggers the presence of four specific smooth functions on the hypersurface, we use these four functions to derive different sufficient conditions for a hypersurface to be the totally geodesic sphere and for a minimal hypersurface to be the totally geodesic sphere, Clifford minimal hypersurface respectively. In particular we classify compact minimal hypersurfaces with a unit Killing vector field in the unit sphere.     

A note on labeled symmetric graphs

By using the known results of groups and graphs, we determine the number of labeled symmetric graphs with a prime number of vertices.