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.     

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).     

Vertex‐disjoint cycles containing specified vertices in a bipartite graph

A minimum degree condition is given for a bipartite graph to contain a 2‐factor each component of which contains a previously specified vertex. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 145–166, 2004     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

A search strategy for the elementary cycles of a directed graph

The most successful known algorithms enumerating the elementary cycles of a directed graph are based on a backtracking strategy. Such existing algorithms are discussed and a new backtracking algorithm is proposed which is bounded byO(N +M(C + 1)) time, for a directed graph withN vertices,M edges andC elementary cycles.Research supported by the Conselho National de Desenvolvimento Científico e Tecnológico — CNPq — Brasil.     

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...     

恰含两个圈的二部图的能量

设λ1,λ2,…,λn是n阶图G的特征值,图G的能量是E(G)=|λ1| |λ2| … |λn|,设G(n)是n个顶点n 1条边的恰有两个圈的连通二部图的集合,Z(n;4,4)是G(n)中的一个图,它的两个长为4的圈恰有一个公共点,其余n-7个点都是悬挂点且均与这个公共点相邻．文中证明了Z(n;4,4)是G(n)中具有最小能量的图。     

Partitioning a graph into two square-cycles

A square-cycle is the graph obtained from a cycle by joining every pair of vertices of distance two in the cycle. The length of a square-cycle is the number of vertices in it. Let G be a graph on n vertices with minimum degree at least 2/3n and let c be the maximum length of a square-cycle in G. Pósa and Seymour conjectured that c = n. In this paper, it is proved that either c = n or 1/2n ≤ c ≤ 2/3n. As an application of this result, it is shown that G has two vertex-disjoint square-cycles C₁, and C₂ such that V(G) = V(C₁) ∪ V(C₂). © 1996 John Wiley & Sons, Inc.     

Partition of a planar graph with girth 6 into two forests with chain length at most 4

We prove that the vertex set of every planar graph with girth at most 6 can be partitioned into two subsets each of which generates a forest in which the length of each chain does not exceed 4.     

Alternating hamiltonian cycles in two colored complete bipartite graphs

We give necessary and sufficient conditions for the existence of an alternating Hamiltonian cycle in a complete bipartite graph whose edge set is colored with two colors.     

Disjoint directed quadrilaterals in a directed graph

Let D be a directed graph of order 4k, where k is a positive integer. Suppose that the minimum degree of D is at least 6k ? 2. We show that D contains k disjoint directed quadrilaterals with only one exception. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Cutting a graph into two dissimilar halves

Given a graph G and a subset S of the vertex set of G, the discrepancy of S is defined as the difference between the actual and expected numbers of the edges in the subgraph induced on S. We show that for every graph with n vertices and e edges, n < e < n(n ? 1)/4, there is an n/2-element subset with the discrepancy of the order of magnitude of \documentclass{article}\pagestyle{empty}\begin{document}$\sqrt {ne}$\end{document} For graphs with fewer than n edges, we calculate the asymptotics for the maximum guaranteed discrepancy of an n/2-element subset. We also introduce a new notion called “bipartite discrepancy” and discuss related results and open problems.     

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.     

On digraphs with no two disjoint directed cycles

We obtain a result on configurations in 2-connected digraphs with no two disjoint dicycles. We derive various consequences, for example a short proof of the characterization of the minimal digraphs having no vertex meeting all dicycles and a polynomially bounded algorithm for finding a dicycle through any pair of prescribed arcs in a digraph with no two disjoint dicycles, a problem which is NP-complete for digraphs in general.     

The subconstituent algebra of a bipartite distance-regular graph; thin modules with endpoint two

We consider a bipartite distance-regular graph Γ with diameter D?4, valency k?3, intersection numbers b_i,c_i, distance matrices A_i, and eigenvalues θ₀>θ₁>?>θ_D. Let X denote the vertex set of Γ and fix x∈X. Let T=T(x) denote the subalgebra of Mat_X(C) generated by , where A=A₁ and denotes the projection onto the ith subconstituent of Γ with respect to x. T is called the subconstituent algebra (or Terwilliger algebra) of Γ with respect to x. An irreducible T-module W is said to be thin whenever for 0?i?D. By the endpoint of W we mean . Assume W is thin with endpoint 2. Observe is a one-dimensional eigenspace for ; let η denote the corresponding eigenvalue. It is known where , and d=⌊D/2⌋. To describe the structure of W we distinguish four cases: (i) ; (ii) D is odd and ; (iii) D is even and ; (iv) . We investigated cases (i), (ii) in MacLean and Terwilliger [Taut distance-regular graphs and the subconstituent algebra, Discrete Math. 306 (2006) 1694-1721]. Here we investigate cases (iii), (iv) and obtain the following results. We show the dimension of W is D-1-e where e=1 in case (iii) and e=0 in case (iv). Let v denote a nonzero vector in . We show W has a basis , where E_i denotes the primitive idempotent of A associated with θ_i and where the set S is {1,2,…,d-1}∪{d+1,d+2,…,D-1} in case (iii) and {1,2,…,D-1} in case (iv). We show this basis is orthogonal (with respect to the Hermitian dot product) and we compute the square-norm of each basis vector. We show W has a basis , and we find the matrix representing A with respect to this basis. We show this basis is orthogonal and we compute the square-norm of each basis vector. We find the transition matrix relating our two bases for W.