Resolvable balanced bipartite designs

A block B denotes a set of k = k₁ + k₂ elements which are divided into two subsets, B¹ and B², where ∣Bⁱ∣ = k_i, i = 1 or 2. Two elements are said to be linked in B if and only if they belong to different subsets of B. A balanced bipartite design, BBD(v, k₁, k₂, λ), is an arrangement of v elements into b blocks, each containing k elements such that each element occurs in exactly r blocks and any two distinct elements are linked in exactly λ blocks. A resolvable balanced bipartite design, RBBD(v, k₁, k₂, λ), is a BBD(v, k₁, k₂, λ), the b blocks of which can be divided into r sets which are called complete replications, such that each complete replication contains all the v elements of the design.Necessary conditions for the existence of RBBD(v, 1, k₂, λ) and RBBD(v, n, n, λ) are obtained and it is shown that some of the conditions are also sufficient. In particular, necessary and sufficient conditions for the existence of RBBD(v, 1, k₂, λ), where k₂ is odd or equal to two, and of RBBD(v, n, n, λ), where n is even and 2n ? 1 is a prime power, are given.     

Covering a graph by complete bipartite graphs

We prove the following theorem: the edge set of every graph G on n vertices can be partitioned into the disjoint union of complete bipartite graphs such that each vertex is contained by at most c(n/log n) of the bipartite graphs.     

Packing two forests into a bipartite graph

For two integers a and b, we say that a bipartite graph G admits an (a, b)-bipartition if G has a bipartition (X, Y) such that |X| = a and |Y| = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this note, we prove that any two compatible trees of order n can be packed into a complete bipartite graph of order at most n + 1. We also provide a family of infinitely many pairs of compatible trees which cannot be packed into a complete bipartite graph of the same order. A theorem about packing two forests into a complete bipartite graph is derived from this result. © 1996 John Wiley & Sons, Inc.     

Zeta functions and complexities of a semiregular bipartite graph and its line graph

We treat zeta functions and complexities of semiregular bipartite graphs. Furthermore, we give formulas for zeta function and the complexity of a line graph of a semiregular bipartite graph. As a corollary, we present the complexity of a line graph of a complete bipartite graph.     

On long cycles in a 2-connected bipartite graph

Letk be an integer withk 2. LetG = (A, B; E) be a 2-connected bipartite graph. Supposed(x) + d(y) k + 1 for every pair of non-adjacent verticesx andy. ThenG contains a cycle of length at leastmin(2a, 2k) wherea = min(|A|,|B|), unlessG is one of some known exceptions. We conjecture that if|A| = |B| andd(x) + d(y) k + 1 for every pair of non-adjacent verticesx andy withx A andy B, thenG contains a cycle of length at leastmin(2a, 2k).     

Existence of perfect matchings in a plane bipartite graph

We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper of F. Zhang, R. Chen and X. Guo (1985).     

Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph

The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with x∈V ₁ and y∈V ₂, then, for any k independent edges e ₁,…,e _k of G, G contains k vertex-disjoint quadrilaterals C ₁,…,C _k such that e _i ∈E(C _i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V ₁|=|V ₂|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C ₁,…,C _k containing specified edges of G.     

Excluding a bipartite circle graph from line graphs

We prove that, for a fixed bipartite circle graph H, all line graphs with sufficiently large rank‐width (or clique‐width) must have a pivot‐minor isomorphic to H. To prove this, we introduce graphic delta‐matroids. Graphic delta‐matroids are minors of delta‐matroids of line graphs and they generalize graphic and cographic matroids. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 183–203, 2009     

Bi-cycle extendable through a given set in balanced bipartite graphs

Let G=(X,Y;E) be a balanced bipartite graph of order 2n. The path-cover numberpc(H) of a graph H is the minimum number of vertex-disjoint paths that use up all the vertices of H. S⊆V(G) is called a balanced set of G if |S∩X|=|S∩Y|. In this paper, we will give some sufficient conditions for a balanced bipartite graph G satisfying that for every balanced set S, there is a bi-cycle of every length from |S|+2pc(〈S〉) up to 2n through S.     

The girth of a 4-homogeneous bipartite graph

In this paper, it is proved that the girth of a 4-homogeneous bipartite graph with valency greater than 2 is at most 12.     

The local eigenvalues of a bipartite distance-regular graph

We consider a bipartite distance-regular graph $\Gamma$ with vertex set $X$, diameter $D\ge 4$, and valency $k\ge 3$. For $0\le i\le D$, let ${\Gamma }_i\left(x\right)$ denote the set of vertices in $X$ that are distance $i$ from vertex $x$. We assume there exist scalars $r,s,t\in \mathbb{R}$, not all zero, such that $r|{\Gamma }_1\left(x\right)\cap {\Gamma }_1\left(y\right)\cap {\Gamma }_2\left(z\right)|+s|{\Gamma }_2\left(x\right)\cap {\Gamma }_2\left(y\right)\cap {\Gamma }_1\left(z\right)|+t=0$ for all $x,y,z\in X$ with path-length distances $\partial (x,y)=2,\partial (x,z)=3,\partial (y,z)=3$. Fix $x\in X$, and let ${\Gamma }_2^2$ denote the graph with vertex set $\tilde{X}=\{y\in X\mid \partial (x,y)=2\}$ and edge set $\tilde{R}=\{yz\mid y,z\in \tilde{X},\partial (y,z)=2\}$. We show that the adjacency matrix of the local graph ${\Gamma }_2^2$ has at most four distinct eigenvalues. We are motivated by the fact that our assumption above holds if $\Gamma$ is $Q$-polynomial.     

Universality among graphs omitting a complete bipartite graph

For cardinals λ,κ,θ we consider the class of graphs of cardinality λ which has no subgraph which is (κ,θ)-complete bipartite graph. The question is whether in such a class there is a universal one under (weak) embedding. We solve this problem completely under GCH. Under various assumptions mostly related to cardinal arithmetic we prove non-existence of universals for this problem. We also look at combinatorial properties useful for those problems concerning κ-dense families.     

Two sufficient conditions for a 2-factor in a bipartite graph

In this paper we prove that every 1-tough bipartite graph which is not isomorphic to K_1,1 has a 2-factor. We also obtain a sufficient condition for the existence of a 2-factor in a bipartite graph, in the spirit of Hall's theorem.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

A proof on cycles and matching in balanced bipartite graphs

证明了对于二部图G=(V1,V2; E),|V1|=|V2|=n,如果满足δ(G)≥([1/2n])+1,则图G有一个生成子图,该子图包含指定长度的圈C和对集M,其中V(C)∩ V(M)=(空集).     

The number of edges in a bipartite graph of given radius

Vizing established an upper bound on the size of a graph of given order and radius. We find a sharp upper bound on the size of a bipartite graph of given order and radius.     

Packing four copies of a tree into a complete bipartite graph

Czechoslovak Mathematical Journal - In considering packing three copies of a tree into a complete bipartite graph, H. Wang (2009) gives a conjecture: For each tree T of order n and each integer k...     

Online balanced graph avoidance games

We introduce and study online balanced coloring games on the random graph process. The game is played by a player we call Painter. Edges of the complete graph with n vertices are introduced two at a time, in a random order. For each pair of edges, Painter immediately and irrevocably chooses one of the two possibilities to color one of them red and the other one blue. His goal is to avoid creating a monochromatic copy of a small fixed graph F for as long as possible.We show that the duration of the game is determined by a threshold function m_H=m_H(n) for certain graph-theoretic structures, e.g., cycles. That is, for every graph H in this family, Painter will asymptotically almost surely (a.a.s.) lose the game after m=ω(m_H) edge pairs in the process. On the other hand, there exists an essentially optimal strategy: if the game lasts for m=o(m_H) moves, Painter can a.a.s. successfully avoid monochromatic copies of H. Our attempt is to determine the threshold function for several classes of graphs.     

On the number of maximal bipartite subgraphs of a graph

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105^n/10 ≈ 1.5926ⁿ; such subgraphs show an upper bound of O(12^n/4) = O(1.8613ⁿ) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005