Random dense bipartite graphs and directed graphs with specified degrees

Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t . In particular, we find precise formulae for the probabilities that a given bipartite graph is edge‐disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out‐degrees s and in‐degrees t . In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t . © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

A note on the strong chromatic index of bipartite graphs

The strong chromatic index s^′(G) is the minimum integer t such that there is an edge-coloring of G with t colors in which every color class is an induced matching. Brualdi and Quinn conjecture that for every bipartite graph G, s^′(G) is bounded by Δ₁Δ₂, where Δ₁ and Δ₂ are the maximum degrees among vertices in the two partite sets. We give the affirmative answer for Δ₁=2.     

Cycles in bipartite graphs

For k an integer, let G(a, b, k) denote a simple bipartite graph with bipartition (A, B) where |A| = a ≥ 2, |B| = b ≥ k ≥ 2, and each vertex of A has degree at least k. We prove two results concerning the existence of cycles in G(a, b, k).     

Domination in bipartite graphs

We prove that the domination number of a graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5, 7, 10 or 13 is at most . Furthermore, we derive upper bounds on the domination number of bipartite graphs of given minimum degree.     

Nested bipartite graphs

We investigate a class of bipartite graphs, whose structure is determined by a binary number. The work for this research was supported by the Max Kade Foundation.     

Graphoidal bipartite graphs

A graphoidal cover of a graph G is a collection ψ of (not necessarily open) paths inG such that every path in ψ has at least two vertices, every vertex ofG is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. Let Ω (ψ) denote the intersection graph of ψ. A graph G is said to be graphoidal if there exists a graphH and a graphoidal cover ψof H such that G is isomorphic to Ω(ψ). In this paper we study the properties of graphoidal graphs and obtain a forbidden subgraph characterisation of bipartite graphoidal graphs.     

Cohen-macaulay bipartite graphs

Let G be a graph on the vertex set V={x ₁, ..., x _n}. Let k be a field and let R be the polynomial ring k[x ₁, ..., x _n]. The graph ideal I(G), associated to G, is the ideal of R generated by the set of square-free monomials x _ix_j so that x _i, is adjacent to x _j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring. Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs. Partially supported by COFAA-IPN, CONACyT and SNI, México.     

Shellable graphs and sequentially Cohen-Macaulay bipartite graphs

Associated to a simple undirected graph G is a simplicial complex ΔG whose faces correspond to the independent sets of G. We call a graph G shellable if ΔG is a shellable simplicial complex in the non-pure sense of Björner-Wachs. We are then interested in determining what families of graphs have the property that G is shellable. We show that all chordal graphs are shellable. Furthermore, we classify all the shellable bipartite graphs; they are precisely the sequentially Cohen-Macaulay bipartite graphs. We also give a recursive procedure to verify if a bipartite graph is shellable. Because shellable implies that the associated Stanley-Reisner ring is sequentially Cohen-Macaulay, our results complement and extend recent work on the problem of determining when the edge ideal of a graph is (sequentially) Cohen-Macaulay. We also give a new proof for a result of Faridi on the sequentially Cohen-Macaulayness of simplicial forests.     

On the strong chromatic index and maximum induced matching of tree-cographs,permutation graphs and chordal bipartite graphs

We show that there exist linear-time algorithms that compute the strong chromatic index and a maximum induced matching of tree-cographs when the decomposition tree is a part of the input. We also show that there exist efficient algorithms for the strong chromatic index of (bipartite) permutation graphs and of chordal bipartite graphs.     

Unbalanced bipartite factorizations of complete bipartite graphs

We construct a new infinite family of factorizations of complete bipartite graphs by factors all of whose components are copies of a (fixed) complete bipartite graph K_p,q. There are simple necessary conditions for such factorizations to exist. The family constructed here demonstrates sufficiency in many new cases. In particular, the conditions are always sufficient when q=p+1.     

Long cycles in bipartite graphs

Let G be a 2-connected bipartite graph with bipartition (A, B), where |A| ≥ |B|. It is shown that if each vertex of A has degree at least k, and each vertex of B has degree at least l, then G contains a cycle of length at least 2min(|B|, k + l ? 1, 2k ? 2). Then this result is used to determine the minimum number of edges required in a bipartite graph to ensure a cycle of length at least 2m, for any integer m ≥ 2.     

Authentication codes and bipartite graphs

In this paper, a characterization of authentication codes in terms of bipartite graphs is given. By using such a characterization, two necessary and sufficient conditions for a minimal authentication code with perfect secrecy are derived. The probabilities of a successful impersonation and of a successful substitution attack are discussed. As a result, some (optimal) minimal authentication codes with perfect secrecy are constructed from association schemes, from finite groups or from known authentication codes no matter whether the known ones are with or without secrecy.     

Path colorings in bipartite graphs

The theorem of König on edge colorings in bipartite multigraphs can be seen as the integral version of the theorem of Birkhoff and von Neumann on bistochastic matrices.Here we consider the more general case where the matrix A=(a_ij) to be decomposed has real entries (instead of non negative entries). We shall concentrate on the integral case. Interpretation in terms of arc and path colorings are given with some properties of these decompositions and one shows that some balancing problems which are trivial in the classical case are now NP-complete. We also introduce requirements on the parity of the paths in the decompositions.