Excluded checkerboard colourable ribbon graph minors

Motivated by the Eulerian ribbon graph minors, in this paper we introduce the notion of checkerboard colourable minors for ribbon graphs and its dual: bipartite minors for ribbon graphs. Motivated by the bipartite minors of abstract graphs, another bipartite minors for ribbon graphs, i.e. the bipartite ribbon graph join minors are also introduced. Using these minors then we give excluded minor characterizations of the classes of checkerboard colourable ribbon graphs, bipartite ribbon graphs, plane checkerboard colourable ribbon graphs and plane bipartite ribbon graphs.     

Weakly bipartite graphs and the Max-cut problem

A new class of graphs, called weakly bipartite graphs, is introduced. A graph is called weakly bipartite if its bipartite subgraph polytope coincides with a certain polyhedron related to odd cycle constraints. The class of weakly bipartite graphs contains for instance the class of bipartite graphs and the class of planar graphs. It is shown that the max-cut problem can be solved in polynomial time for weakly bipartite graphs. The polynomical algorithm presented is based on the ellipsoid method and an algorithm that computes a shortest path of even length.     

A conjecture on bipartite graphical regular representations

In this paper we are concerned with the classification of the finite groups admitting a bipartite DRR and a bipartite GRR.First, we find a natural obstruction that prevents a finite group from admitting a bipartite GRR. Then we give a complete classification of the finite groups satisfying this natural obstruction and hence not admitting a bipartite GRR. Based on these results and on some extensive computer computations, we state a conjecture aiming to give a complete classification of the finite groups admitting a bipartite GRR.Next, we prove the existence of bipartite DRRs for most of the finite groups not admitting a bipartite GRR found in this paper. Actually, we prove a much stronger result: we give an asymptotic enumeration of the bipartite DRRs over these groups. Again, based on these results and on some extensive computer computations, we state a conjecture aiming to give a complete classification of the finite groups admitting a bipartite DRR.     

Several results on chordal bipartite graphs

The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is shown that, to any vertex of a chordal bipartite graph an edge may be added such that the chordality is maintained.     

On matching numbers of tree and bipartite degree sequences

We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree degree sequences, we obtain closed formulas for the possible values. For bipartite degree sequences, we show the existence of realizations with a restricted structure, which allows to derive an analogue of the Gale–Ryser Theorem characterizing bipartite degree sequences. More precisely, we show that a bipartite degree sequence has a realization with a certain matching number if and only if a cubic number of inequalities similar to those in the Gale–Ryser Theorem are satisfied. For tree degree sequences as well as for bipartite degree sequences, the possible values of the matching number form intervals.     

On maximum bipartite subgraphs

In this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipartite subgraphs of cubic graphs are investigated. It is shown that cubic graphs can be built up from five building stones (called elementary paths). Finally the investigation of a special class of cubic graphs yields a theorem which characterizes the Petersen graph and the dodecahedron graph by means of their maximum bipartite subgraphs.     

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.     

On bipartite graphs of diameter 3 and defect 2

We consider bipartite graphs of degree Δ≥2, diameter D=3, and defect 2 (having 2 vertices less than the bipartite Moore bound). Such graphs are called bipartite (Δ, 3, ?2) ‐graphs. We prove the uniqueness of the known bipartite (3, 3, ?2) ‐graph and bipartite (4, 3, ?2)‐graph. We also prove several necessary conditions for the existence of bipartite (Δ, 3, ?2) ‐graphs. The most general of these conditions is that either Δ or Δ?2 must be a perfect square. Furthermore, in some cases for which the condition holds, in particular, when Δ=6 and Δ=9, we prove the non‐existence of the corresponding bipartite (Δ, 3, ?2)‐graphs, thus establishing that there are no bipartite (Δ, 3, ?2)‐graphs, for 5≤Δ≤10. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 271–288, 2009     

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.     

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.     

Bipartite Locating Array

As a special case of experimental design,locating array is useful for locating interaction faults in component-based systems.In this paper,bipartite locating array is proposed to locate interaction faults between two specific groups.Such arrays are especially suitable for antagonism tests.Based on the definition of bipartite locating array,the lower bound on run sizes are established to measure the optimality for specific parameters.When a single fault is to be located,optimal bipartite locating arrays are proved to be equivalent to certain specific combinatorial configurations.As a result,approaches to constructing optimal bipartite locating arrays are proposed and some infinite classes of optimal bipartite locating arrays are obtained using the corresponding construction met hod.     

The number of bipartite tournaments with a unique given factor

We give a recursive function in order to calculate the number of all non-isomorphic bipartite tournaments containing an unique hamiltonian cycle. Using this result we determine the number of all nonisomorphic bipartite tournaments that admit an unique factor isomorphic to a given 1-diregu-lar bipartite graph.     

Small Worlds Among Interlocking Directors: Network Structure and Distance in Bipartite Graphs

We describe a methodology to examine bipartite relational data structures as exemplified in networks of corporate interlocking. These structures can be represented as bipartite graphs of directors and companies, but direct comparison of empirical datasets is often problematic because graphs have different numbers of nodes and different densities. We compare empirical bipartite graphs to simulated random graph distributions conditional on constraints implicit in the observed datasets. We examine bipartite graphs directly, rather than simply converting them to two 1-mode graphs, allowing investigation of bipartite statistics important to connection redundancy and bipartite connectivity. We introduce a new bipartite clustering coefficient that measures tendencies for localized bipartite cycles. This coefficient can be interpreted as an indicator of inter-company and inter-director closeness; but high levels of bipartite clustering have a cost for long range connectivity. We also investigate degree distributions, path lengths, and counts of localized subgraphs. Using this new approach, we compare global structural properties of US and Australian interlocking company directors. By comparing observed statistics against those from the simulations, we assess how the observed graphs are structured, and make comparisons between them relative to the simulated graph distributions. We conclude that the two networks share many similarities and some differences. Notably, both structures tend to be influenced by the clustering of directors on boards, more than by the accumulation of board seats by individual directors; that shared multiple board memberships (multiple interlocks) are an important feature of both infrastructures, detracting from global connectivity (but more so in the Australian case); and that company structural power may be relatively more diffuse in the US structure than in Australia.     

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.     

On the structure of clique‐free graphs

Using a clever inductive counting argument Erd?s, Kleitman and Rothschild showed in 1976 that almost all triangle‐free graphs are bipartite, i.e., that the cardinality of the two graph classes is asymptotically equal. In this paper we investigate the structure of the “few” triangle‐free graphs which are not bipartite. As it turns out, with high probability, these graphs are bipartite up to a few vertices. More precisely, almost all of them can be made bipartite by removing just one vertex. Almost all others can be made bipartite by removing two vertices, and then three vertices and so on. We also show that similar results hold if we replace “triangle‐free” by K_??+1‐free and “bipartite” by ??‐partite. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 37–53, 2001     

Square-free perfect graphs

We prove that square-free perfect graphs are bipartite graphs or line graphs of bipartite graphs or have a 2-join or a star cutset.     

Chordal Bipartite Graphs with High Boxicity

The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity.     

Non-existence of bipartite graphs of diameter at least 4 and defect 2

The Moore bipartite bound represents an upper bound on the order of a bipartite graph of maximum degree Δ and diameter D. Bipartite graphs of maximum degree Δ, diameter D and order equal to the Moore bipartite bound are called Moore bipartite graphs. Such bipartite graphs exist only if D=2,3,4 and 6, and for D=3,4,6, they have been constructed only for those values of Δ such that Δ−1 is a prime power.     

Hamiltonian cycles in bipartite graphs

We give a sufficient condition for bipartite graphs to be Hamiltonian. The condition involves the edge-density and balanced independence number of a bipartite graph.