Computing the bipartite edge frustration of fullerene graphs

Bipartite edge frustration of a graph is defined as the smallest number of edges that have to be deleted from the graph to obtain a bipartite spanning subgraph. We show that for fullerene graphs this quantity can be computed in polynomial time and obtain explicit formulas for the icosahedral fullerenes. We also report some computational results and discuss a potential application of this invariant in the context of fullerene stability.     

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.     

Extremal bipartite subgraphs of cubic triangle-free graphs

A cubic triangle-free graph has a bipartite subgraph with at least 4/5 of the original edges. Examples show that this is a best possible result.     

Extremal graphs of diameter at most 6 after deleting any vertex

Suppose G is a graph of n vertices and diameter at most d having the property that, after deleting any vertex, the resulting subgraph has diameter at most 6. Then G contains at least max{n, (4n - 8)/3} edges if 4 ≤ d ≤ 6.     

Sequentially Cohen–Macaulay bipartite graphs: vertex decomposability and regularity

Let G be a bipartite graph with edge ideal I(G) whose quotient ring R/I(G) is sequentially Cohen–Macaulay. We prove: (1) the independence complex of G must be vertex decomposable, and (2) the Castelnuovo–Mumford regularity of R/I(G) can be determined from the invariants of G.     

One edge union of shell graphs and one vertex union of complete bipartite graphs are cordial

In this paper we prove that one edge union of k-copies of shell graphs H(n,n−3) is cordial, for all n⩾4 and k⩾1 and one vertex union of t copies of complete bipartite graph K_m,n is cordial.     

Algebraic characterizations of regularity properties in bipartite graphs

Regular and distance-regular characterizations of general graphs are well-known. In particular, the spectral excess theorem states that a connected graph Γ$\Gamma$ is distance-regular if and only if its spectral excess (a number that can be computed from the spectrum) equals the average excess (the mean of the numbers of vertices at extremal distance from every vertex). The aim of this paper is to derive new characterizations of regularity and distance-regularity for the more restricted family of bipartite graphs. In this case, some characterizations of (bi)regular bipartite graphs are given in terms of the mean degrees in every partite set and the Hoffman polynomial. Moreover, it is shown that the conditions for having distance-regularity in such graphs can be relaxed when compared with general graphs. Finally, a new version of the spectral excess theorem for bipartite graphs is presented.     

Extremal interval graphs

An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for the numbers of such graphs. © 1993 John Wiley & Sons, Inc.     

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.     

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.     

Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales

The Alon–Roichman theorem states that for every ε> 0 there is a constant c(ε), such that the Cayley graph of a finite group G with respect to c(ε)log ∣G∣ elements of G, chosen independently and uniformly at random, has expected second largest eigenvalue less than ε. In particular, such a graph is an expander with high probability. Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a new proof of the result, improving the bounds even further. When considered for a general group G, our bounds are in a sense best possible. We also give a generalization of the Alon–Roichman theorem to random coset graphs. Our proof uses a Hoeffding‐type result for operator valued random variables, which we believe can be of independent interest. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Embeddings of bipartite graphs

If G is a bipartite graph with bipartition A, B then let G_m,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a₁, …, a_m, each vertex b of B by an independent set b₁,…, b_n, and each edge ab of G by the complete bipartite graph with edges a_ib_j (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of G_m,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess-current graphs.” They include new genus embeddings for a large class of bipartite graphs.     

Bichromaticity of bipartite graphs

Let B be a bipartite graph with edge set E and vertex bipartition M, N. The bichromaticity β(B) is defined as the maximum number β such that a complete bipartite graph on β vertices is obtainable from B by a sequence of identifications of vertices of M or vertices of N. Let μ = max{∣M∣, ∣N∣}. Harary, Hsu, and Miller proved that β(B) ≥ μ + 1 and that β(T) = μ + 1 for T an arbitrary tree. We prove that β(B) ≤ μ + ∣E∣/μ yielding a simpler proof that β(T) = μ + 1. We also characterize graphs for which K_{μ, 2} is obtainable by such identifications. For Q_K. the graph of the K-dimensional cube, we obtain the inequality 2^K?1 + 2 ≤ β(Q_K) ≤ 2^K?1 + K, the upper bound attainable iff K is a power of 2.