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     

On distance-transitive graphs and involutions

We present a new result on distance-transitive graphs and show how it can be used in the case where the vertex stabilizer is the centralizer of some involution.Report PM-R8808, Centre for Mathematics and Computer Science, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands     

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.     

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.     

On bipartite graphs with minimal energy

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. In a paper [G. Caporossi, D. Cvetkovi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996] Caporossi et al. conjectured that among all connected graphs G with n≥6 vertices and n−1≤m≤2(n−2) edges, the graphs with minimum energy are the star S_n with m−n+1 additional edges all connected to the same vertices for m≤n+⌊(n−7)/2⌋, and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. The conjecture is proved to be true for m=n−1,2(n−2) in the same paper by Caporossi et al. themselves, and for m=n by Hou in [Y. Hou, Unicyclic graphs with minimal energy, J. Math. Chem. 29 (2001) 163-168]. In this paper, we give a complete solution for the second part of the conjecture on bipartite graphs. Moreover, we determine the graph with the second-minimal energy in all connected bipartite graphs with n vertices and edges.     

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.     

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.     

Path colorings in bipartite graphs

The theorem of König on edge colorings in bipartite multigraphs can be seen as the integral version of the theorem of Birkhoff and von Neumann on bistochastic matrices.Here we consider the more general case where the matrix A=(a_ij) to be decomposed has real entries (instead of non negative entries). We shall concentrate on the integral case. Interpretation in terms of arc and path colorings are given with some properties of these decompositions and one shows that some balancing problems which are trivial in the classical case are now NP-complete. We also introduce requirements on the parity of the paths in the decompositions.     

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.     

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.     

Random dense bipartite graphs and directed graphs with specified degrees

Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t . In particular, we find precise formulae for the probabilities that a given bipartite graph is edge‐disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out‐degrees s and in‐degrees t . In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t . © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Left loops, bipartite graphs with parallelism and bipartite involution sets

We describe a representation of any semiregularleft loop by means of asemiregular bipartite involution set or, equivalently, a 1-factorization (i.e., a parallelism) of a bipartite graph, with at least one transitive vertex. In these correspondences,Bol loops are associated on one hand toinvariant regular bipartite involution sets and, on the other hand, totrapezium complete bipartite graphs with parallelism; K-loops (or Bruck loops) are further characterized by a sort of local Pascal configuration in the related graph. Research partially supported by the Research Project of M.I.U.R. (Italian Ministry of Education, University and Research) “Strutture geometriche, combinatoria e loro applicazioni” and by the Research group G.N.S.A.G.A. of INDAM.