Exceptional set of Goldbach number

Let E(x) denote the number of even numbers not exceeding x which cannot be written as a sum of two primes. In this paper we obtain

E(x)?x^0.879.     

A scale-free graph model based on bipartite graphs

Most biological networks have some common properties, on which models have to fit. The main one is that those networks are scale-free, that is that the distribution of the vertex degrees follows a power-law. Among the existing models, the ones which fit those characteristics best are based on a time evolution which makes impossible the analytic calculation of the number of motifs in the network. Focusing on applications, this calculation is very important to decompose networks in a modular manner, as proposed by Milo et al.. On the contrary, models whose construction does not depend on time, miss one or several properties of real networks or are not computationally tractable. In this paper, we propose a new random graph model that satisfies the global features of biological networks and the non-time-dependency condition. It is based on a bipartite graph structure, which has a biological interpretation in metabolic networks.     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

Signed and minus domination in bipartite graphs

The paper studies the signed domination number and the minus domination number of the complete bipartite graph K _{p, q} .     

Connected matchings in chordal bipartite graphs

A connected matching in a graph is a collection of edges that are pairwise disjoint but joined by another edge of the graph. Motivated by applications to Hadwiger’s conjecture, Plummer, Stiebitz, and Toft (2003) introduced connected matchings and proved that, given a positive integer $k$, determining whether a graph has a connected matching of size at least $k$ is NP-complete. Cameron (2003) proved that this problem remains NP-complete on bipartite graphs, but can be solved in polynomial-time on chordal graphs. We present a polynomial-time algorithm that finds a maximum connected matching in a chordal bipartite graph. This includes a novel edge-without-vertex-elimination ordering of independent interest. We give several applications of the algorithm, including computing the Hadwiger number of a chordal bipartite graph, solving the unit-time bipartite margin-shop scheduling problem in the case in which the bipartite complement of the precedence graph is chordal bipartite, and determining–in a totally balanced binary matrix–the largest size of a square sub-matrix that is permutation equivalent to a matrix with all zero entries above the main diagonal.     

The bipartite edge frustration of composite graphs

The smallest number of edges that have to be deleted from a graph to obtain a bipartite spanning subgraph is called the bipartite edge frustration of G and denoted by φ(G). In this paper we determine the bipartite edge frustration of some classes of composite 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.     

A characterization of cycle-forced bipartite graphs

A forced cycle$C$ of a graph $G$ is a cycle in $G$ such that $G?V\left(C\right)$ has a unique perfect matching. A graph $G$ is a cycle-forced graph if every cycle in $G$ is a forced cycle. In this paper, we give a characterization of cycle-forced hamiltonian bipartite graphs.     

A panconnectivity theorem for bipartite graphs

Let $G$ be a simple $m\times n$ bipartite graph with $m\ge n$. We prove that if the minimum degree of $G$ satisfies $\delta \left(G\right)\ge m∕2+1$, then $G$ is bipanconnected: for every pair of vertices $x,y$, and for every appropriate integer $2\le ?\le 2n$, there is an $x,y$-path of length $?$ in $G$.     

Verifying the Goldbach conjecture up to

Using a carefully optimized segmented sieve and an efficient checking algorithm, the Goldbach conjecture has been verified and is now known to be true up to . The program was distributed to various workstations. It kept track of maximal values of the smaller prime in the minimal partition of the even numbers, where a minimal partition is a representation with being composite for all . The maximal prime needed in the considered interval was found to be 5569 and is needed for the partition 389965026819938 = 5569 + 389965026814369.

     

The rainbow number of matchings in regular bipartite graphs

Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK₂ a matching of size m and as B_n,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GB_n,k, rb(G,mK₂)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.     

Size bipartite Ramsey numbers

Let B, B₁ and B₂ be bipartite graphs, and let B→(B₁,B₂) signify that any red-blue edge-coloring of B contains either a red B₁ or a blue B₂. The size bipartite Ramsey number is defined as the minimum number of edges of a bipartite graph B such that B→(B₁,B₂). It is shown that is linear on n with m fixed, and is between c₁n²2ⁿ and c₂n³2ⁿ for some positive constants c₁ and c₂.     

Large bipartite Cayley graphs of given degree and diameter

Let BC_d,k be the largest possible number of vertices in a bipartite Cayley graph of degree d and diameter k. We show that BC_d,k≥2(k−1)((d−4)/3)^k−1 for any d≥6 and any even k≥4, and BC_d,k≥(k−1)((d−2)/3)^k−1 for d≥6 and k≥7 such that k≡3 (mod 4).     

Regular bipartite graphs are antimagic

A labeling of a graph G is a bijection from E(G) to the set {1, 2,… |E(G)|}. A labeling is antimagic if for any distinct vertices u and v, the sum of the labels on edges incident to u is different from the sum of the labels on edges incident to v. We say a graph is antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every connected graph other than K₂ is antimagic. In this article, we show that every regular bipartite graph (with degree at least 2) is antimagic. Our technique relies heavily on the Marriage Theorem. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 173–182, 2009     

Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs

Robert E. Jamison characterized chordal graphs by the edge set of every k-cycle being the symmetric difference of k−2 triangles. Strongly chordal (and chordal bipartite) graphs can be similarly characterized in terms of the distribution of triangles (respectively, quadrilaterals). These results motivate a definition of ‘strongly chordal bipartite graphs’, forming a class intermediate between bipartite interval graphs and chordal bipartite graphs.     

Topological minors in bipartite graphs

For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K _(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem.     

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.     

Line graphs of bipartite graphs with Hamiltonian paths

It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path P_t as a star complement for the eigenvalue ?2. The maximal graph is the line graph of K_m,m if t = 2m?1, and of K_m,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement P_r ∪ P_s or P_r ∪ C_s for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003