Forcing matching numbers of fullerene graphs

The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.     

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.     

Reducing an arbitrary fullerene to the dodecahedron

Viewing fullerenes as plane graphs with facial cycles being pentagonal and hexagonal only, it is shown how to reduce an arbitrary fullerene to the (graph of the) dodecahedron. This can be achieved by a sequence of eight reduction steps, seven of which are local operations and the remaining reduction step acts globally. In any case, the resulting algorithm has polynomial running time.     

On the nullity of bipartite graphs

The nullity of a graph is defined to be the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. In this paper, we obtain the nullity set of bipartite graphs of order n, and characterize the bipartite graphs with nullity n-4 and the regular bipartite graphs with nullity n-6.     

Finding odd cycle transversals

We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k.     

On some structural properties of generalized fullerene graphs with 13 pentagonal faces

It is shown that every generalized fullerene graph G with 13 pentagons is 2-extendable, a brick, and cyclically 5-edge-connected, i.e., that G cannot be separated into two components, each containing a cycle, by deletion of fewer than five edges. New lower bound on the number of perfect matchings in such graphs are also established.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

Invariant Kekulé structures in fullerene graphs

Fullerene graphs are trivalent plane graphs with only hexagonal and pentagonal faces. They are often used to model large carbon molecules: each vertex represents a carbon atom and the edges represent chemical bonds. A totally symmetric Kekulé structure in a fullerene graph is a set of independent edges which is fixed by all symmetries of the fullerene and molecules with totally symmetric Kekulé structures could have special physical and chemical properties, as suggested in [Austin, S.J, and J. Baker, P. W. Fowler, D. E. Manolopoulos, Bond-stretch Isomerism and the Fullerenes, J. Chem. Soc. Perkin Trans. 2 (1994), 2319–2323] and [Rogers, K.M., and P. W. Fowler, Leapfrog fullerenes, Huckel bond order and Kekulé structures, J. Chem. Soc. Perkin Trans. 2 (2001), 18–22]. All fullerenes with at least ten symmetries were studied in [Graver, J.E. The Structure of Fullerene Signature, DIMACS Series of Discrete Mathematics and Theoretical Computer Science 64, AMS (2005), 137–166.] and a complete catalog was given in [Graver, J. E. Catalog of All Fullerene with Ten or More Symmetries DIMACS Series of Discrete Mathematics and Theoretical Computer Science 64 AMS (2005), 167–188]. Starting from this catalog in [Bogaerts, M., and G. Mazzuoccolo, G.Rinaldi, Totally symmetric Kekulé structures in fullerene graphs with ten or more symmetries, MATCH Communications in Mathematical and in Computer Chemistry 69 (2013), 677–705] we established exactly which of them have at least one totally symmetric Kekulé structure.     

二元图的最佳连通性

本文介绍二元图的最佳连通性问题，给出了有关最佳连通性的若干结果；并就一般情形，给出了二元图最佳连通性问题的解．     

Bipartite density of cubic graphs

We first obtain the exact value for bipartite density of a cubic line graph on n vertices. Then we give an upper bound for the bipartite density of cubic graphs in terms of the smallest eigenvalue of the adjacency matrix. In addition, we characterize, except in the case n=20, those graphs for which the upper bound is obtained.     

Toroidal fullerenes with the Cayley graph structures

We classify all possible structures of fullerene Cayley graphs. We give each one a geometric model and compute the spectra of its finite quotients. Moreover, we give a quick and simple estimation for a given toroidal fullerene. Finally, we provide a realization of those families in three-dimensional space.     

A combinatorial algorithm for weighted stable sets in bipartite graphs

Computing a maximum weighted stable set in a bipartite graph is considered well-solved and usually approached with preflow-push, Ford-Fulkerson or network simplex algorithms. We present a combinatorial algorithm for the problem that is not based on flows. Numerical tests suggest that this algorithm performs quite well in practice and is competitive with flow based algorithms especially in the case of dense graphs.     

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 shifted Turán sieve method on tournaments II

In a previous work [5], we developed the shifted Turán sieve method on a bipartite graph and applied it to problems on cycles in tournaments. More precisely, we obtained upper bounds for the number of tournaments which contain a small number of r-cycles. In this paper, we improve our sieve inequality and apply it to obtain an upper bound for the number of bipartite tournaments which contain a number of 2r-cycles far from the average. We also provide the exact bound for the number of tournaments which contain few 3-cycles, using other combinatorial arguments.     

On the Nullity of Bipartite Graphs

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. We obtain some lower bounds for the nullity of graphs and we then find the nullity of bipartite graphs with no cycle of length a multiple of 4 as a subgraph. Among bipartite graphs on n vertices, the star has the greatest nullity (equal to n − 2). We generalize this by showing that among bipartite graphs with n vertices, e edges and maximum degree Δ which do not have any cycle of length a multiple of 4 as a subgraph, the greatest nullity is . G. R. Omidi: This research was in part supported by a grant from IPM (No.87050016).     

On cyclic edge-connectivity of fullerenes

A graph is said to be cyclically k-edge-connected, if at least k edges must be removed to disconnect it into two components, each containing a cycle. Such a set of k edges is called a cyclic-k-edge cutset and it is called a trivial cyclic-k-edge cutset if at least one of the resulting two components induces a single k-cycle.It is known that fullerenes, that is, 3-connected cubic planar graphs all of whose faces are pentagons and hexagons, are cyclically 5-edge-connected. In this article it is shown that a fullerene F containing a nontrivial cyclic-5-edge cutset admits two antipodal pentacaps, that is, two antipodal pentagonal faces whose neighboring faces are also pentagonal. Moreover, it is shown that F has a Hamilton cycle, and as a consequence at least 15·2^n/20-1/2 perfect matchings, where n is the order of F.     

2-resonance of plane bipartite graphs and its applications to boron-nitrogen fullerenes

A set H of disjoint faces of a plane bipartite graph G is a resonant pattern if G has a perfect matching M such that the boundary of each face in H is an M-alternating cycle. An elementary result was obtained [Discrete Appl. Math. 105 (2000) 291-311]: a plane bipartite graph is 1-extendable if and only if every face forms a resonant pattern. In this paper we show that for a 2-extendable plane bipartite graph, any pair of disjoint faces form a resonant pattern, and the converse does not necessarily hold. As an application, we show that all boron-nitrogen (B-N) fullerene graphs are 2-resonant, and construct all the 3-resonant B-N fullerene graphs, which are all k-resonant for any positive integer k. Here a B-N fullerene graph is a plane cubic graph with only square and hexagonal faces, and a B-N fullerene graph is k-resonant if any disjoint faces form a resonant pattern. Finally, the cell polynomials of 3-resonant B-N fullerene graphs are computed.     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

二分图中度条件和k-因子的存在性

本文主要研究了二分图中任意一对距离为２的顶点的度数与ｋ－因子关系,给出了二分图有ｋ因子的若干充分条件,并说明这些条件是最好的可能,从而证明了Ｎｉｓｈｉｍｕｒａ提出的问题对二分图成立。     

A note on transformations of edge colorings of bipartite graphs

The author and A. Mirumian proved the following theorem: Let G be a bipartite graph with maximum degree Δ and let t,n be integers, tnΔ. Then it is possible to obtain, from one proper edge t-coloring of G, any proper edge n-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the intermediate colorings are also proper. In this note we show that if t>Δ then we can transform f to g using only transformations of 2-colored subgraphs. We also correct the algorithm suggested in [A.S. Asratian, Short solution of Kotzig's problem for bipartite graphs, J. Combin. Theory Ser. B 74 (1998) 160–168] for transformation of f to g in the case when t=n=Δ and G is regular.