Alternating cycle-free matchings

The investigation of alternating cycle-free matchings is motivated by the Jump-number problem for partially ordered sets and the problem of counting maximum cardinality matchings in hexagonal systems.We show that the problem of deciding whether a given chordal bipartite graph has an alternating cycle-free matching of a given cardinality is NP-complete. A weaker result, for bipartite graphs only, has been known for some time. Also, the alternating cycle-free matching problem remains NP-complete for strongly chordal split graphs of diameter 2.In contrast, we give algorithms to solve the alternating cycle-free matching problem in polynomial time for bipartite distance hereditary graphs (time O(m ²) on graphs with m edges) and distance hereditary graphs (time O(m ⁵)).     

An implicit representation of chordal comparability graphs in linear time

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n²).     

A transitive closure algorithm

An algorithm is given for computing the transitive closure of a directed graph in a time no greater thana ₁ N ₁ n+a ₂ n ² for largen wherea ₁ anda ₂ are constants depending on the computer used to execute the algorithm,n is the number of nodes in the graph andN ₁ is the number of arcs (not counting those arcs which are part of a cycle and not counting those arcs which can be removed without changing the transitive closure). For graphs where each arc is selected at random with probabilityp, the average time to compute the transitive closure is no greater than min{a ₁ pn ³+a ₂ n ², 1/2a ₁ n ² p ^–2+a ₂ n ²} for largen. The algorithm will compute the transitive closure of an undirected graph in a time no greater thana ₂ n ² for largen. The method uses aboutn ²+n bits and 5n words of storage (where each word can holdn+2 values).     

The transitive closure of a random digraph

In a random n-vertex digraph, each arc is present with probability p, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, when n is large and np is equal to a constant c greater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about Θ₂n vertices, where Θ is the unique root in [0, 1] of the equation 1 ? x ? e^?ex = 0. Nearly all the vertices outside the large strong component line in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected time O(n). for all choices of n and p, the expected execution time of the algorithm is O(w(n) (n log n)^4/3), where w(n) is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be Ω(n²) the algorithm presents the transitive closure in the compact form (A × B)U C, where A and B are sets of vertices, and C is a set of arcs.     

On the Ramsey number of trees versus graphs with large clique number

Chvátal established that r(T_m, K_n) = (m – 1)(n – 1) + 1, where T_m is an arbitrary tree of order m and K_n is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K_n could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that K_n can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(T_m, K_n –tK₂) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where T_m is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].     

On the interval number of a chordal graph

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum clique size ω(G) = m, then i(G) ? [1 + o(1)]m/log₂ m and this result is best possible, even for split graphs (chordal graphs whose complement is also chordal).     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Chordal bipartite graphs and crowns

We prove that a bipartite graph is chordal if and only if it has an elimination scheme. This leads to a polynomial algorithm to recognize whether an ordered set is cycle-free.     

Transitive closure for restricted classes of partial orders

Most papers dealing with partial orders assume that the input is given either in transitively closed or transitively reduced form. In this paper, we show that it is possible to solve some problems on partial orders in less time than it takes to perform transitive closure or reduction for general graphs. In particular, we present efficient algorithms for recognizing two dimensional partial orders and N-free partial orders when no assumptions are made about the form of the input.This work was supported by National Science Foundation Grant DCR-8604577 and the Vanderbilt University Research Council.     

Transforming binary sequences using priority queues

A priority queue transforms an input sequence into an output sequence which is a re-ordering of the sequence . The setR of all such related pairs is studied in the case that is a binary sequence. It is proved thatR is a partial order and that ¦R¦=c _n+1, the (n+1)th Catalan number. An efficient (O(n ²)) algorithm is given for computing the number of outputs achievable from a given input.     

Approximation Algorithms for the Achromatic Number

The achromatic number for a graph G = V, E is the largest integer m such that there is a partition of V into disjoint independent sets {V₁, …, V_m} such that for each pair of distinct sets V_i, V_j, V_i V_j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math.38, 364–372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n^5/12) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees.     

Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

Containment for c, s, t operators on a binary relation

The operators c, s and t are complement, symmetric and transitive closure of a binary relation. If u and v denote finite sequences of these operators then we define u v iff for every binary relation . We find the distinct representative and containment between these sequences. The asymmetric operator is not one of these. There are 54 representatives for binary relations, 20 for transitive relations, and 10 for symmetric relations. There are 26 component types of a binary relation, 10 for transitive relations, and 6 for symmetric relations. There are 16 connected types of a binary relation, 8 for transitive relations, and 4 for symmetric relations. We study well founded relations. Total relations may not be contractible but well founded ones are. The complement of (a Hasse diagram of) a non-empty partial order of arbitrary cardinality is contractible. Ordered sets are naturally homotopy equivalent to partially ordered sets. There are 10 relations which can have arbitrary polyhedral homotopy type and 42 are either contractible or the homotopy type of a wedge of n-spheres. The homotopy type of two relations is not determined.     

An Optimal Algorithm to Solve the All-Pairs Shortest Paths Problem on Permutation Graphs

In this paper we present an optimal algorithm to solve the all-pairs shortest path problem on permutation graphs with n vertices and m edges which runs in O(n ²) time. Using this algorithm, the average distance of a permutation graph can also be computed in O(n ²) time.     

Sources in posets and comparability graphs

A vertex in a poset is a source if its indegree is zero. Further, a vertex in a comparability graph G is a source if there is a transitive orientation of G in which is a source. We characterize sources in comparability graphs in terms of forbidden subgraphs. Certain results follow, including a brief proof of a theorem by Olariu.     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

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.     

Maximum transversal in partial Latin squares and rainbow matchings

In a partial Latin square P a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal T, we mean the number of its entries. We define a duplex to be a partial Latin square of order n containing 2n entries such that exactly two entries lie in each row and column and each of n symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an NP-complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least ⌊n/2⌋-t for each fixed t, where n is the order of the graph. As an application we show that for any fixed t, there is a polynomial time algorithm which decides whether α(G)?n-t, for any graph G on 2n vertices containing a perfect matching. At the end we mention some other applications of rainbow matching.     

The capture time of a graph

We consider the game of Cops and Robbers played on finite and countably infinite connected graphs. The length of games is considered on cop-win graphs, leading to a new parameter, the capture time of a graph. While the capture time of a cop-win graph on n vertices is bounded above by n−3, half the number of vertices is sufficient for a large class of graphs including chordal graphs. Examples are given of cop-win graphs which have unique corners and have capture time within a small additive constant of the number of vertices. We consider the ratio of the capture time to the number of vertices, and extend this notion of capture time density to infinite graphs. For the infinite random graph, the capture time density can be any real number in [0,1]. We also consider the capture time when more than one cop is required to win. While the capture time can be calculated by a polynomial algorithm if the number k of cops is fixed, it is NP-complete to decide whether k cops can capture the robber in no more than t moves for every fixed t.