On the number of irreducible coverings by edges of complete bipartite graphs

In this paper it is proved that the exponential generating function of the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite graphs K_p,q equals exp(xe^y + ye^x − x − y − xy) − 1.     

Convex hull of the edges of a graph and near bipartite graphs

First we characterize the convex hull of the edges of a graph, edges viewed as the characteristic function of the hereditary closure of some subset of the 2-elements set of a finite set X. This characterization becomes more simple for a class of graphs that we call near bipartite, NBP in short. This class is then characterized as the class of graphs such that ?x?X, G_X\r(x), the induced subgraph of the complementary of the neighbourhood of x, is bipartite. We made a partial study of this class, whose interest is justified by the constatation that the following classes are strictly include: $\text{L(G)}$ the edge complementary of the line graph of G. NBP, $\text{K}{}_{13}$-free graphs.     

Indestructive deletions of edges from graphs

If G is a graph on p vertices with connectivity, or edge-connectivity, or minimum valency, at least k, we ask how many edges one can delete from G without reducing the appropriate quantity below k −1. When p and k are large, our answers are about , , and , respectively; we conjecture that the correct (best possible) answer is about in each case.     

Algebras arising from bipartite planar graphs

Let G be a bipartite planar graph and k[G] its associated monomial algebra. We find a linear system of parameters for k[G] and a maximal regular sequence in P(G), the presentation ideal of k[G]. This allows us to bound the coefficients of the Hubert series, and in some cases to compute it exactly. The techniques of the theory of Gröbner bases are used throughout.     

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.     

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.     

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.     

Coloring complete bipartite graphs from random lists

Let K_n,n be the complete bipartite graph with n vertices in each side. For each vertex draw uniformly at random a list of size k from a base set S of size s = s(n). In this paper we estimate the asymptotic probability of the existence of a proper coloring from the random lists for all fixed values of k and growing n. We show that this property exhibits a sharp threshold for k ≥ 2 and the location of the threshold is precisely s(n) = 2n for k = 2 and approximately for k ≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Edge orientations on cubic graphs with a maximum number of pairs of oppositely oriented edges

We consider the problem: Characterize the edge orientations of a finite graph with a maximum number of pairs of oppositely oriented edges. The problem is solved for finite cubic graphs.     

A generalized construction of chromatic index critical graphs from bipartite graphs

We prove that any graph with maximum degree n which can be obtained by removing exactly 2n - 1 edges from the join K¹ + K^{n, n} is n-critical. This generalizes special constructions of critical graphs by S. Fiorini and H. P. Yap, and suggests a possible extension of another general construction due to Yap.     

Embeddings of bipartite graphs

If G is a bipartite graph with bipartition A, B then let G_m,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a₁, …, a_m, each vertex b of B by an independent set b₁,…, b_n, and each edge ab of G by the complete bipartite graph with edges a_ib_j (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of G_m,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess-current graphs.” They include new genus embeddings for a large class of bipartite graphs.     

Bichromaticity of bipartite graphs

Let B be a bipartite graph with edge set E and vertex bipartition M, N. The bichromaticity β(B) is defined as the maximum number β such that a complete bipartite graph on β vertices is obtainable from B by a sequence of identifications of vertices of M or vertices of N. Let μ = max{∣M∣, ∣N∣}. Harary, Hsu, and Miller proved that β(B) ≥ μ + 1 and that β(T) = μ + 1 for T an arbitrary tree. We prove that β(B) ≤ μ + ∣E∣/μ yielding a simpler proof that β(T) = μ + 1. We also characterize graphs for which K_{μ, 2} is obtainable by such identifications. For Q_K. the graph of the K-dimensional cube, we obtain the inequality 2^K?1 + 2 ≤ β(Q_K) ≤ 2^K?1 + K, the upper bound attainable iff K is a power of 2.     

Distances in orientations of graphs

We prove that there is a function h(k) such that every undirected graph G admits an orientation H with the following property: If an edge uv belongs to a cycle of length k in G, then uv or vu belongs to a directed cycle of length at most h(k) in H. Next, we show that every undirected bridgeless graph of radius r admits an orientation of radius at most r² + r, and this bound is best possible. We consider the same problem with radius replaced by diameter. Finilly, we show that the problem of deciding whether an undirected graph admits an orientation of diameter (resp. radius) 2 belongs to a class of problems called NP-hard.     

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.