Search

Subgraph matching finds all embeddings from a data graph that are identical to a query graph. Recent algorithms work by generating a tree-structured index on the data graph based on the query graph, ordering the vertices root-to-leaf path-by-path in the tree, and enumerating the embeddings following the matching order. However, we find such path-based ordering and tree-structured index based enumeration inherently limit the performance due to the lack of consideration on the edges among the vertices across tree paths. To address this problem, we propose an approach that generates the matching order based on a cost model considering both the edges among query vertices and the number of candidates. Furthermore, we create a bigraph index for candidate vertices and their selected neighbors in the data graph, and use this index to perform enumeration along the matching order. Our experiments on both real-world and synthetic datasets show that our method outperforms the state of the art by orders of magnitude.

We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella class that contains both classes and maintains their essential properties. This is done ...

The biclique graph K B ( G ) is the intersection graph of all the bicliques of a graph G . The aim of our work is to recognize graphs that are biclique graphs of interval bigraphs ( IBG ). In this paper we prove that K B ( IBG ) ⊂ K 1 , 4 -free co-comparability graphs. We also study the class of biclique graphs of proper interval bigraphs ( PIB ). Recall that PIB is equal to the class of bipartite permutation graphs ( BPG ). We present a characterization of the class K B ( PIB ) and of the biclique graphs of a subclass of PIB that leads to a polynomial time recognition algorithm. We also present characterizations of biclique graphs of some classes such as complete graphs, trees and graphs with girth at least 5.

This paper is related to the problem of finding the maximal quasi-bicliques in a bipartite graph (bigraph). A quasi-biclique in the bigraph is its "almost" complete subgraph. The relaxation of completeness can be understood variously; here, we assume that the subgraph is a $\gamma$-quasi-biclique if it lacks a certain number of edges to form a biclique such that its density is at least $\gamma \in (0,1]$. For a bigraph and fixed $\gamma$, the problem of searching for the maximal quasi-biclique consists of finding a subset of vertices of the bigraph such that the induced subgraph is a quasi-biclique and its size is maximal for a given graph. Several models based on Mixed Integer Programming (MIP) to search for a quasi-biclique are proposed and tested for working efficiency. An alternative model inspired by biclustering is formulated and tested; this model simultaneously maximizes both the size of the quasi-biclique and its density, using the least-square criterion similar to the one exploited by triclustering \textsc{TriBox}.

A bipartite graph \(G=(U,V,E)\) is an interval bigraph if and only if there is a one to one correspondence between \(U \cup V\) and a family of intervals on the number line such that two vertices of opposing partite sets are neighbors precisely if their corresponding intervals intersect. Interval bigraphs, as well as many subclasses, have been extensively studied by multiple researchers along the years, and many results on their structural and computational properties have been discovered. A bipartite graph \(G=(U,V,E)\) is a circular arc bigraph if and only if there is a one to one correspondence between \(U \cup V\) and a family of arcs on a circle such that two vertices of opposing partite sets are neighbors precisely if their corresponding arcs intersect. While it is a generalization of interval bigraphs, it remains a relatively unexplored topic. Few studies about the class and its proper, unit and Helly subclasses have been presented. In this work, we study some subclasses of these classes. We provide forbidden structure characterizations for the Helly subclass of interval bigraphs, as well as the class of non-bichordal Helly circular arc bigraphs. We also prove that Helly interval bigraphs are a subclass of proper interval bigraphs, and that non-bichordal Helly circular arc bigraphs are a subclass of proper circular arc bigraphs.

A hypergraph $\mathcal H$ is super-pancyclic if for each $A \subseteq V(\mathcal H)$ with $|A| \geq 3$, $\mathcal H$ contains a Berge cycle with base vertex set $A$. We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient for this. In particular, they are sufficient for every hypergraph $\mathcal H$ with $ \delta(\mathcal H)\geq \max\{|V(\mathcal H)|, \frac{|E(\mathcal H)|+10}{4}\}$. We also consider super-cyclic bipartite graphs: those are $(X,Y)$-bigraphs $G$ such that for each $A \subseteq X$ with $|A| \geq 3$, $G$ has a cycle $C_A$ such that $V(C_A)\cap X=A$. Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs., Comment: 17 pages

The end-vertex problem for a search algorithm asks whether a vertex of the input graph is the last visited vertex of an execution of that search algorithm. We consider the end-vertex problem restricted to AT-free bigraphs for various search algorithms: Breadth-First Search (BFS), Lexicographic Breadth-First Search (LBFS), Depth-First Search (DFS), and Maximal Neighbourhood Search (MNS). Deciding whether a vertex of a graph is the end-vertex of any of these search algorithms is NP-complete in general. We show that we can decide whether a vertex is an end-vertex of BFS or MNS in polynomial time on AT-free bigraphs. Additionally, we show that we can decide whether a vertex is an end-vertex of DFS or LBFS in linear time on AT-free bigraphs; this improves the LBFS end-vertex complexity on this class of graphs.

The matrix completion problem is the following: Suppose a matrix X is unknown except for an upper bound r on its rank. By sampling various entries of X, is it possible to “complete” the remaining entries and recover X exactly? There are two popular approaches to choosing the entries to be sampled. The first approach is to select these entries at random (either with or without replacement). The second approach is to choose the entries to be sampled in a deterministic fashion; this is the approach studied here. We show that if the entries to be sampled correspond to the edges of a so-called Ramanujan graph (defined below), then the measured matrix is in some sense an “optimal” approximation of the unknown matrix. This naturally raises the question of constructing such Ramanujan graphs. It turns out that there are very few explicit constructions of Ramanujan graphs. In this paper, we review the known methods and analyze their suitability for solving the matrix completion problem. The preceding discussion applies to the completion of square matrices. If one is interested in completing rectangular matrices, then it becomes necessary to choose the sample set to correspond to the edges of a Ramanujan bigraph. Until now, there has not been a single explicit construction of a Ramanujan bigraph. Two such constructions are given here. When specialized to the case of square matrices, our construction generates a new family of Ramanujan graphs.

An interval k-graph is the intersection graph of a family of intervals of the real line partitioned into k classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we study the cocomparability interval k-graphs; that is, the interval k-graphs whose complements have a transitive orientation and are therefore the incomparability graphs of strict partial orders. For brevity we call these orders interval k-orders. We characterize the kind of interval representations a cocomparability interval k-graph must have, and identify the structure that guarantees an order is an interval k-order. The case k = 2 is peculiar: cocomparability interval 2-graphs (equivalently proper- or unit-interval bigraphs, bipartite permutation graphs, and complements of proper circular-arc graphs to name a few) have been characterized in many ways, but we show that analogous characterizations do not hold if k > 2. We characterize the cocomparability interval 3-graphs via one forbidden subgraph and hence interval 3-orders via one forbidden suborder.

Formal Concept Analysis (FCA) takes as input the bipartite context graph and produces a directed acyclic graph representing the lattice of formal concepts. Excepting possibly the supremum and infimum, the set of formal concepts corresponds to the set of proper maximal bicliques in the context bigraph. This paper proposes polynomial-time graph layouts which emphasise maximal bicliques in the context bigraph and facilitate “reading” directed paths in the lattice digraph. These layouts are applied to sub-contexts of the InfoVis 2004 data set which are indivisible by the Carve divide-and-conquer FCA algorithm. The paper also investigates the relationship between vertex proximity in the bigraph layout and co-membership of maximal bicliques, and demonstrates the significant reduction of edge crossings in the digraph layout.

In 1969, Alan Tucker characterized proper circular-arc graphs as those graphs whose augmented adjacency matrices have the circularly compatible ones property. Moreover, he also found a polynomial-time algorithm for deciding whether any given augmented adjacency matrix has the circularly compatible ones property. These results allowed him to devise the first polynomial-time recognition algorithm for proper circular-arc graphs. However, as Tucker himself remarks, he did not solve the problems of finding a structure theorem and an efficient recognition algorithm for the circularly compatible ones property in arbitrary matrices (i.e., not restricted to augmented adjacency matrices only). In this work, we solve these problems. More precisely, we give a minimal forbidden submatrix characterization for the circularly compatible ones property in arbitrary matrices and a linear-time recognition algorithm for the same property. We derive these results from analogous ones for the related $D$-circular property. Interestingly, these results lead to a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for proper circular-arc bigraphs, solving a problem first posed by Basu, Das, Ghosh, and Sen [J. Graph Theory, 73(4):361--376, 2013]. Our findings generalize some known results about $D$-interval hypergraphs and proper interval bigraphs., Comment: 28 pages, 5 figures

An interval matrix is the adjacency matrix of an interval digraph or equivalently the biadjacency matrix of an interval bigraph. In this paper we investigate the forbidden substructures of an interval bigraph. Our method finds hitherto existing forbidden substructures for interval matrices, and via a more concise statement, as well as a new example showing that these substructures are not exhaustive.

A proper interval bigraph is a bigraph where to each vertex we can assign a closed interval such that the intervals can be chosen to be inclusion free and vertices in the opposite partite sets are adjacent when the corresponding intervals intersect. In this paper, we introduce the notion of astral triple of edges and along the lines of characterization of interval graphs via the absence of asteroidal triple of vertices we characterize proper interval bigraphs via the absence of astral triple of edges. We also characterize proper interval bigraphs in terms of dominating pair of vertices as defined by Corneil et al. Tucker characterized proper circular arc graphs in terms of circularly compatible 1’s of adjacency matrices. Sen and Sanyal characterized adjacency matrices of proper interval bigraphs in terms of monotone consecutive arrangement. We have shown an interrelation between these two concepts.

In this paper, some necessary and sufficient conditions for the existence of an evenly partite directed bigraph (\(\overrightarrow{K}_{p,q\oplus q}\)) factorization in the product graphs \((C_m\circ \overline{K}_n)^*\) and \((K_m\circ \overline{K}_n)^*,\) for \(m\ge 3,\) \(n,p,q\ge 2\) are obtained.

A fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other part, together with the edges, must be added to the drawing. We assume that G is planar and study the problem of finding, for a given \(k \ge 0\), a planar poly-line drawing of G with at most k bends per edge. In the most general case, we show NP-hardness. For \(k=0\) and under additional constraints on the positions of the fixed or mobile vertices, we either prove that the problem is polynomial-time solvable or prove that it belongs to NP. Finally, we present a polynomial-time testing algorithm for a certain type of “layered” 1-bend drawings.

A bipartite graph with partite sets X and Y is a permutation bigraph if there are two linear orderings of its vertices such that xy is an edge for x@?X and y@?Y if and only if x appears later than y in the first ordering and earlier than y in the second ordering. We characterize permutation bigraphs in terms of representations using intervals. We determine which permutation bigraphs are interval bigraphs or indifference bigraphs in terms of the defining linear orderings. Finally, we show that interval containment posets are precisely those whose comparability bigraphs are permutation bigraphs, via a theorem showing that a directed version of interval containment provides no more generality than ordinary interval containment representation of posets.

A {0,1}- bigraph is a connected bigraph with the property that any two distinct vertices have exactly one common neighbour or none at all. If any two distinct vertices of a part P of G have exactly one common neighbour, the part P is called {1}-part. In this paper, basic properties of finite regular {0,1}- bigraphs with at least one {1}-part are studied and some characterization results are given.

In this paper we are going to define splitting on bigraphs. The purpose of this paper is that however investigation of created graph by splitting is bipartite graph (Bigraph) or not? We show that after of operation of splitting on the one of the vertices of bigraph, the graph is also bigraph. Another rule is proved in this paper, is that if the graph is connected then the resulting bi graph is also connected.

For standard algorithms verifying positive definiteness of a matrix A ∈ Mn(R) based on Sylvester’s criterion, the computationally pessimistic case is this when A is positive definite. We present an algorithm realizing the same task for A ∈ Mn(Z), for which the case when A is positive definite is the optimistic one. The algorithm relies on performing certain edge transformations, called inflations, on the signed graph (bigraph) Δ = Δ(A) associated with A. We provide few variants of the algorithm, including Las Vegas type randomized ones (with precisely described maximal number of steps). The algorithms work very well in practice, in many cases with a better speed than the standard tests. On the other hand, our results provide an interesting example of an application of symbolic computing methods originally developed for different purposes, with a big potential for further generalizations in matrix problems.

The minimum cost homomorphism problem is a natural optimization problem for homomorphisms to a fixed graph H. Given an input graph G, with a cost associated with mapping any vertex of G to any vertex of H, one seeks to minimize the sum of costs of the assignments over all homomorphisms of G to H. The complexity of this problem is well understood, as a function of the target graph H. For bipartite graphs H, the problem is polynomial time solvable if H is a proper interval bigraph, and is NP-complete otherwise. In many applications, the costs may be assumed to be the same for all vertices of the input graph. We study the complexity of this restricted version of the minimum cost homomorphism problem. Of course, the polynomial cases are still polynomial under this restriction. We expect the same will be true for the NP-complete cases, i.e., that the complexity classification will remain the same under the restriction. We verify this for the class of trees. For general graphs H, we prove a partial result: the problem is polynomial if H is a proper interval bigraph and is NP-complete when H is not chordal bipartite.

In this article, we obtain two new characterizations of circular-arc bigraphs. One of them is the representation of a circular-arc bigraph in terms of two two-clique circular-arc graphs while another one represents the same as a union of an interval bigraph and a Ferrers bigraph. Finally, we introduce the notions of proper and unit circular-arc bigraphs, characterize them and show that, as in the case of circular-arc graphs, unit circular-arc bigraphs form a proper subclass of the class of proper circular-arc bigraphs.

Let X be a compact metric space, and Homeo ( X ) be the group consisting of all homeomorphisms from X to X. A subgroup H of Homeo ( X ) is said to be transitive if there exists a point x ∈ X such that { k ( x ) : k ∈ H } is dense in X. In this paper we show that, if X = G is a connected graph, then the following five conditions are equivalent: (1) Homeo ( G ) has a transitive commutative subgroup; (2) G admits a transitive Z 2 -action; (3) G admits an edge-transitive commutative group action; (4) G admits an edge-transitive Z 2 -action; (5) G is a circle, or a k-fold loop with k ⩾ 2 , or a k-fold polygon with k ⩾ 2 , or a k-fold complete bigraph with k ⩾ 1 . As a corollary of this result, we show that a finite connected simple graph whose automorphism group contains an edge-transitive commutative subgroup is either a cycle or a complete bigraph.

This paper concerns the global stability of controlling a complex network with digraph topology to a homogeneous trajectory of the uncoupled system by the local pinning control algorithm. The derived stability condition indicates that the smallest real part of eigenvalues of the Laplacian sub-matrix corresponding to the unpinned vertices can be used to measure the stabilizability of a digraph with a given pinned vertex set. A pinned vertex set can stabilize a directed network to some unstable trajectories, for instance, to a chaotic trajectory of the uncoupled systems, if and only if the pinned vertex set can access all other vertices in the digraph. Furthermore, in the bigraph case, the analytical estimation of the stabilizability's lower bound suggests that an optimal pinning strategy should take not only the vertex degree, but also the shortest path between pairs of vertices into considerations.

We consider the following question: given an $(X,Y)$-bigraph $G$ and a set $S \subset X$, does $G$ contain two disjoint matchings $M_1$ and $M_2$ such that $M_1$ saturates $X$ and $M_2$ saturates $S$? When $|S|\geq |X|-1$, this question is solvable by finding an appropriate factor of the graph. In contrast, we show that when $S$ is allowed to be an arbitrary subset of $X$, the problem is NP-hard., 6 pages, 1 figure

We construct explicitly an infinite family of Ramanujan graphs which are bipartite and biregular. Our construction starts with the Bruhat–Tits building of an inner form of \(\mathrm{SU}_{3}(\mathbb{Q}_{p})\). To make the graphs finite, we take successive quotients by infinitely many discrete co-compact subgroups of decreasing size.

Lexicographic Breadth First Search (LBFS) is one of fundamental graph search algorithms that has numerous applications, including recognition of graph classes, computation of graph parameters, and detection of certain graph structures. The well-known result of Rose, Tarjan and Lueker on the end-vertices of LBFS of chordal graphs has tempted researchers to study the end-vertices of LBFS of various classes of graphs, including chordal graphs, split graphs, interval graphs, and asteroidal triple-free (AT-free) graphs. In this paper we study the end-vertices of LBFS of bipartite graphs. We show that deciding whether a vertex of a bipartite graph is the end-vertex of an LBFS is an NP-complete problem. In contrast we characterize the end-vertices of LBFS of AT-free bipartite graphs. Our characterization implies that the problem of deciding whether a vertex of an AT-free bipartite graph is the end-vertex of an LBFS is solvable in polynomial time. Key words: Lexicographic breadth first search, end-vertex, bipartite graphs, AT-free, proper interval bigraph, characterization, algorithm., Comment: 12 pages, 4 figures

An interval bigraph B is a proper interval bigraph if there is an interval representation of B such that no interval of the same partite set is properly contained in the other. Similarly a circular arc bigraph B is a proper circular arc bigraph if there is a circular arc representation of B such that no arc of the same partite set is properly contained in the other. In this paper, we characterize proper interval bigraphs and proper circular arc bigraphs using two linear orderings of their vertex set.

Three mutually separable edges of a graph form an asteroidal triple of edges (ATE), if for any two of them, there is a path from the vertex set of one to the vertex set of another that avoids the neighbours of the third edge. In this note, it is shown that a bigraph of Ferrers dimension at most 2 is bichordal and ATE-free, but the converse is not true.

Given are two graphs H"1=(V,E"1) and H"2=(V,E"2) on the same vertex set. The line bigraph is the bipartite graph with the disjoint union of E"1 and E"2 as vertex set, and an edge between e"[email protected]?E"1 and e"[email protected]?E"2 if the edges have some common vertex in V. We first show that the problem to determine whether a given bipartite graph is the line bigraph of two such graphs is NP-complete. We then present two special cases where the question can be solved in polynomial time. A C"4-free bipartite graph is a line bigraph if and only if each component of the graph obtained by removing all degree-2 vertices has at most one cycle. Using the intersection multigraph of the set of all large bicliques, we then show that there is an efficient recognition algorithm for recognizing line bigraphs of two graphs both having minimum degree at least 3.

There exist bigraphs that are deterministically separable, but in no less than n steps, for any n∈N. Further there exist bigraphs that are non-deterministically separable, but in no less than 3 steps.

A cubic bigraph G is minimally 1-factorable if every 1-factor lies in precisely one 1-factorization. We characterize 3-bridges of G and prove that the 3-cut reductions of G are still minimally 1-factorable; thus, the open classification problem is reduced to the study of 3-bridge-free minimally 1-factorable cubic bigraphs. Furthermore, we prove that if ab , cd are edges of G such that the graph obtained by twisting them in ad , bc is still minimally 1-factorable, then ab , cd lie in some 3-bridge of G .

A signed bipartite graph G with vertices 1′, 2′,…,m and 1′,2′,…n′, determines the family M(G) consisting of all m by n matrices whose (i,j)-entry is zero if i,j′ )is not and edge of G nonnegative if {i,j′} is an edge of G with label +1, and nonpositive if {i,f′}is an edge of G with label -1. we show that each matrix A in M(G) can be expressed as the sum of rank(A) rank on matrices in M(G) if and only if for every cycle γ of G of length l(γ)≥6. We also show that each matrix in M(G) has its rank equal to its term rank if and only if (1) holds for every cycle γ of G. Graphical characterizations of the signed bigraphs whose cycles satisfy (1) and of the signed bigraphs whose cycles of length 6 or more satisfy (1) are given.

This is an investigation into the limiting distribution of the sparse connected components in an n1 × n2 bipartite multigraph with approximately ½n edges, where n1, n2 ≈ ½n. We will show that the probability of finding no complex components in a random n1 × n2 bigraph, with approximately ½n edges, is asymptotically the same as for random graphs with n vertices and approximately ½n edges, namely √2/3. In addition, we will show that, for n1 × n2 multi-bigraphs, the probability distribution for finitely many bicyclic components, tricyclic components, etc., with no components having more than a given number of cycles, asymptotically equals the corresponding distribution for random multigraphs with n vertices and approximately half as many edges. As an application of this analysis we present a method for estimating the efficiency of memory access in a distributed, replicated data base.

Graph Theory, The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general.

We have been investigating an approach to parallel database processing based on treating Entity-Relationship (E-R) schema graphs as dataflow graphs. A prerequisite is to find appropriate embeddings of the schema graphs into a processor graph, in this case a hypercube. This paper studies a class of adjacency preserving embeddings that map a node in the schema graph into a subcube (relaxed squashed or RS embeddings) or into adjacent subcubes (relaxed extended squashed or RES embeddings) of a hypercube. The mapping algorithm is motivated by the technique used for state assignment in asynchronous sequential machines. In general, the dimension of the cube required for squashed embedding of a graph is called the weak cubical dimension or WCD of the graph. The RES embedding provides an RES-WCD of O(⌈log2n⌉) for a completely connected graph, Kn, and RS embedding provides an RS-WCD of O(⌈log2n⌉ + ⌈log2m⌉) for a completely connected bigraph, Km,n. Typical E-R graphs are incompletely connected bigraphs. An algorithm for embedding incomplete bigraphs is presented.

A (3,4)-biregular bigraph G is a bipartite graph where all vertices in one part have degree 3 and all vertices in the other part have degree 4. A path factor of G is a spanning subgraph whose components are nontrivial paths. We prove that a simple (3,4)-biregular bigraph always has a path factor such that the endpoints of each path have degree three. Moreover we suggest a polynomial algorithm for the construction of such a path factor., 7 pages

Publisher Summary This chapter describes metrically regular square of metrically regular bigraphs. There is only one table of parameters of an association scheme so that the corresponding metrically regular bipartite graph of diameter D = 4 (5 distinct eigenvalues) has a strongly regular square. The realization of this table is the 4-dimensional unit cube. There are only four tables of parameters of association schemes so that the corresponding metrically regular bipartite graphs of diameter D = 5 (6 distinct eigenvalues) have a metrically regular square. There is only one table of parameters of an association scheme with 6 classes so that the corresponding metrically regular bipartite graph of diameter D = 6 (7 distinct eigenvalues) has a metrically regular square. The realization of this table is the 6-dimensional unit cube. Some theorems and their proofs are also discussed in the chapter.

Compound matrices which list the entire set of matchings in a bigraph are used to prove the theorem of Hall.

We define the relative Tits form number W(G, V) of a valued bigraph G at a vertex v and derive some basic properties. We give a detailed analysis of the case when W (G,V) ≥½. The properties of these numbers were used without proof in the classification of Auslander algebras of finite representation type [IPTZ]

In the first paper of this title it was shown that the sum of the valences at three distinct vertices of a bigraph on 2 n points obeyed v p + v q + v r ⩽ 3n − 1, if n = 2m, 3n, if n = 2m − 1 A class of bigraphs (modified central star and central star) was defined which demonstrated that these bounds were the best possible by achieving equality in each case. In this note, it is shown that for n odd the central star bigraph and for n even the modified central star and three simple variations on the central star are the only bigraphs having sums of valences which achieve the bound and that for all other bigraphs strict inequality prevails. It is also noted that this result implies that the sum of valences at m distinct vertices of a bigraph is strictly less than mn for all m ≤ 4.

In this paper, we establish a laying-off algorithm for constructing a (simple) graph with prescribed degrees and with a Hamiltonian path starting at a specified vertex. This algorithm can be applied to construct a Hamiltonian graph with prescribed degrees. It is also shown that Hamiltonian bigraphs with prescribed degrees can be similarly constructed.

If G and H are graphs, then G ∨ H G \vee H is defined to be a graph obtained by identifying some edge of G with some edge of H. It is shown that for all m, n, p, and q the genus g ( K m , n ∨ K p , q ) g({K_{m,n}} \vee {K_{p,q}}) is either g ( K m , n ) + g ( K p , q ) g({K_{m,n}}) + g({K_{p,q}}) or else g ( K m , n ) + g ( K p , q ) − 1 g({K_{m,n}}) + g({K_{p,q}}) - 1 . The latter value is attained if and only if both K m , n {K_{m,n}} and K p , q {K_{p,q}} are critical in the sense that the deletion of any edge results in a graph whose genus is one less than the genus of the original graph.

Let bi denote the number of ways to select a subset of i independent edges in a given graph. It is shown that the sequence of bi's is unimodal, that is, there exists an r such that b0 < b1 < … < br ≥ br+1 > … > bm. Similarly, for any bigraph, the nonzero coefficients in the characteristic polynomial are shown to be unimodal in magnitude. Finally, it is suggested that the approach used here might be applied to verify the conjecture that the coefficients in the chromatic polynomial are unimodal in magnitude.

For small values of n it is easily seen that the components of a bigraph on 2n points are themselves bigraphs of their point set.Simmons had asked whether this was always the case and had shown that if a bigraph on 2n points existed which had a component that was not in itself a bigraph then 2n≧16. In this paper we answer his question affirmatively by using a result ofLovasz. We also show that any two components of a bigraph intersect.

Section 2 generalizes some concepts in directed graphs to configurations, called bigraph, which have directed as well as undirected lines. Several relations are defined in terms of a bigraph. Conditions are found under which it is possible to find weak, partial, and simple orders as well as preference relations. An application of this theory is found in following sections 3 and 4. These sections deal with the estimation of an order relation from paired comparisons in which ties may occur. (Author)

The possibilities for circuits of length 4 to appear together in a cubic bigraph are classified. That has consequences on the structure of minimally 1-factorable regular bigraphs, i.e. those in which each 1-factor lies in precisely one 1-factorization. We characterize minimally 1-factorable cubic bigraphs of girth 4.

We study the minimum number of complete bipartite subgraphs needed to cover and partition the edges of a k-regular bigraph on 2n vertices. Bounds are determined on the minima of these numbers for fixed n and k. Exact values of the minima are found for all n and k ≤ 4. The same results hold for directed graphs. Equivalently, we have determined bounds on the minimum value of the Boolean and nonnegative integer ranks of binary n × n matrices with constant row and column sum k for fixed n and k, obtaining the exact values of the minimum for k ≤ 4.