Planar graphs and poset dimension

We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<_G b if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V E whose intersection is <_G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning.     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

Posets with interval upper bound graphs

Competition graphs of transitive acyclic digraphs are strict upper bound graphs. This paper characterizes those posets, which can be considered transitive acyclic digraphs, which have upper bound graphs that are interval graphs. The results proved here may shed some light on the open question of those digraphs which have interval competition graphs.This material is taken from Chapter 3 of my (maiden name Diny) PhD Dissertation.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

The partial complement of graphs

For a graphG, the switched graphS _v (G) ofG at a vertexv is the graph obtained fromG by deleting the edges ofG incident withv and adding the edges of incident withv. Properties of graphs whereS _v (G) G or are studied. This concept is extended to the partial complementS _H (G) where H . The investigation here centers around the existence of setsH for whichS _H (G) G. A parameter is introduced which measures how near a graph is to being self-complementary.     

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.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

On the geodetic number of median graphs

A set of vertices S in a graph is called geodetic if every vertex of this graph lies on some shortest path between two vertices from S. In this paper, minimum geodetic sets in median graphs are studied with respect to the operation of peripheral expansion. Along the way geodetic sets of median prisms are considered and median graphs that possess a geodetic set of size two are characterized.     

Circle orders,N-gon orders and the crossing number

Let ={P ₁,...,P _m } be a family of sets. A partial order P(, <) on is naturally defined by the condition P _i <P _j iff P _i is contained in P _j . When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977.     

Vertex-weightings for distance moments and thorny graphs

Valence-weightings are considered for shortest-path distance moments, as well as related weightings for the so-called “Wiener” polynomial. In the case of trees the valence-weighted quantities are found to be expressible as a combination of unweighted quantities. Further the weighted quantities for a so-called “thorny” graph are considered and shown to be related to the weighted and unweighted quantities for the underlying parent graph.     

The t#-property for integral domains

Generalizing work of Gilmer and Heinzer, we define a t#-domain to be a domain R in which for any two distinct subsets and of the set of maximal t-ideals of R. We provide characterizations of these domains, and we show that polynomial rings over t#-domains are again t#-domains. Finally, we study overrings of t#-domains.     

Dualisability versus residual character: A theorem and a counterexample

We show that a finite algebra must be inherently non-dualisable if the variety that it generates is both residually large and congruence meet-semidistributive. We also give the first example of a finite dualisable algebra that generates a variety that is residually large.     

Substitution and atomic extension on greedy posets

In this paper, we study the operations of substitution and atomic extension on greedy posets. For the substitution operation, if P=(P ₁ , x, P ₂ )is a greedy poset, then P ₁ and P ₂ are greedy posets, the converse being false. However, for the atomic extension, P=P ₁ (x, P ₂ )is a greedy poset if and only if P ₁ and P ₂ are greedy posets. We prove also that the class of greedy semi-partitive lattices is the smallest one containing M _n (n2), B ₃ and closed by atomic extension. The class C _n of greedy posets with jump number n is infinite. However, we show that C _n can be obtained, in a very simple way, from a subclass D _n of finite cardinal ity. We construct D _n for n=1, 2.     

The number of orders with thirteen elements

The number of non-isomorphic posets on 13 elements is P₁₃=33,823,827,452. This extends our previous result P₁₂ which constituted the greatest known value. A table enumerates the posets according to their number of relations.

---

     

A cofinal coloring theorem for partially ordered algebras

If P is a directed partially ordered algebra of an appropriate sort-e.g. an upper semilattice-and has no maximal element, then P has two disjoint subalgebras each cofinal in P. In fact, if P has cofinality then there exists a family of such disjoint subalgebras. A version of this result is also proved without the directedness assumption, in which the cofinality of P is replaced by an invariant which we call its global cofinality.This work was done while the first author was partly supported by NSF contract MCS 82-02632.     

On the Burkard-Hammer condition for hamiltonian split graphs

A graph G=(V,E) is called a split graph if there exists a partition V=I∪K such that the subgraphs of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary but not sufficient condition for hamiltonian split graphs with |I|<|K|. In this paper, we show that the Burkard-Hammer condition is also sufficient for the existence of a Hamilton cycle in a split graph G such that 5≠|I|<|K| and the minimum degree δ(G)?|I|-3. For the case 5=|I|<|K|, all split graphs satisfying the Burkard-Hammer condition but having no Hamilton cycles are also described.     

2–3 graphs which have Vizing's adjacency property

2–3 graphs in which each vertex is adjacent to at least two vertices of degree 3 are shown to be characterised by the number of vertices of degree 3 adjacent to vertices of degree 3 only.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

A remark on covering graphs

Every graph G may be transformed into a covering graph either by deletion of edges or by subdivision. Let _E (G) and _V (G) denote corresponding minimal numbers. We prove _E (G) = _V (G) for every graph G.