Chromatic characterization of biclique covers

A biclique B of a simple graph G is the edge-set of a complete bipartite subgraph of G. A biclique cover of G is a collection of bicliques covering the edge-set of G. Given a graph G, we will study the following problem: find the minimum number of bicliques which cover the edge-set of G. This problem will be called the minimum biclique cover problem (MBC). First, we will define the families of independent and dependent sets of the edge-set E(G) of G: F⊆E(G) will be called independent if there exists a biclique B⊆E(G) such that F⊆B, and will be called dependent otherwise. From our study of minimal dependent sets we will derive a 0-1 linear programming formulation of the following problem: find the maximum weighted biclique in a graph. This formulation may have an exponential number of constraints with respect to the number of nodes of G but we will prove that the continuous relaxation of this integer program can be solved in polynomial time. Finally we will also study continuous relaxation methods for the problem (MBC). This research was motivated by an open problem of Fishburn and Hammer.     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010     

Enumeration aspects of maximal cliques and bicliques

We present a general framework to study enumeration algorithms for maximal cliques and maximal bicliques of a graph. Given a graph G, we introduce the notion of the transition graph T(G) whose vertices are maximal cliques of G and arcs are transitions between cliques. We show that T(G) is a strongly connected graph and characterize a rooted cover tree of T(G) which appears implicitly in [D.S. Johnson, M. Yannakakis, C.H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters 27 (1988) 119-123; S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM Journal on Computing 6 (1977) 505-517]. When G is a bipartite graph, we show that the Galois lattice of G is a partial graph of T(G) and we deduce that algorithms based on the Galois lattice are a particular search of T(G). Moreover, we show that algorithms in [G. Alexe, S. Alexe, Y. Crama, S. Foldes, P.L. Hammer, B. Simeone, Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics 145 (1) (2004) 11-21; L. Nourine, O. Raynaud, A fast algorithm for building lattices, Information Processing Letters 71 (1999) 199-204] generate maximal bicliques of a bipartite graph in O(n²) per maximal biclique, where n is the number of vertices in G. Finally, we show that under some specific numbering, the transition graph T(G) has a hamiltonian path for chordal and comparability graphs.     

The most vital nodes with respect to independent set and vertex cover

Given an undirected graph with weights on its vertices, the k most vital nodes independent set (k most vital nodes vertex cover) problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets (minimum weight of vertex covers, respectively). We also consider the complementary problems, minimum node blocker independent set (minimum node blocker vertex cover) that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets (minimum weight of vertex covers, respectively) in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on cographs and graphs of bounded treewidth. Results on the non-existence of ptas are presented, too.     

A continuous characterization of the maximum-edge biclique problem

The problem of finding large complete subgraphs in bipartite graphs (that is, bicliques) is a well-known combinatorial optimization problem referred to as the maximum-edge biclique problem (MBP), and has many applications, e.g., in web community discovery, biological data analysis and text mining. In this paper, we present a new continuous characterization for MBP. Given a bipartite graph $G$ , we are able to formulate a continuous optimization problem (namely, an approximate rank-one matrix factorization problem with nonnegativity constraints, R1N for short), and show that there is a one-to-one correspondence between (1) the maximum (i.e., the largest) bicliques of $G$ and the global minima of R1N, and (2) the maximal bicliques of $G$ (i.e., bicliques not contained in any larger biclique) and the local minima of R1N. We also show that any stationary points of R1N must be close to a biclique of $G$ . This allows us to design a new type of biclique finding algorithm based on the application of a block-coordinate descent scheme to R1N. We show that this algorithm, whose algorithmic complexity per iteration is proportional to the number of edges in the graph, is guaranteed to converge to a biclique and that it performs competitively with existing methods on random graphs and text mining datasets. Finally, we show how R1N is closely related to the Motzkin–Strauss formalism for cliques.     

Bi-cycle extendable through a given set in balanced bipartite graphs

Let G=(X,Y;E) be a balanced bipartite graph of order 2n. The path-cover numberpc(H) of a graph H is the minimum number of vertex-disjoint paths that use up all the vertices of H. S⊆V(G) is called a balanced set of G if |S∩X|=|S∩Y|. In this paper, we will give some sufficient conditions for a balanced bipartite graph G satisfying that for every balanced set S, there is a bi-cycle of every length from |S|+2pc(〈S〉) up to 2n through S.     

Perfect Matchings in Balanced Hypergraphs – A Combinatorial Approach

Our topic is an extension of the following classical result of Hall to hypergraphs: A bipartite graph G contains a perfect matching if and only if for each independent set X of vertices, at least |X| vertices of G are adjacent to some vertex of X. Berge generalized the concept of bipartite graphs to hypergraphs by defining a hypergraph G to be balanced if each odd cycle in G has an edge containing at least three vertices of the cycle. Based on this concept, Conforti, Cornuéjols, Kapoor, and Vušković extended Hall's result by proving that a balanced hypergraph G contains a perfect matching if and only if for any disjoint sets A and B of vertices with |A| > |B|, there is an edge in G containing more vertices in A than in B (for graphs, the latter condition is equivalent to the latter one in Hall's result). Their proof is non-combinatorial and highly based on the theory of linear programming. In the present paper, we give an elementary combinatorial proof. Received April 29, 1997     

Disjoint independent dominating sets in graphs

A set X of vertices of G is an independent dominating set if no two vertices of X are adjacent and each vertex not in X is adjacent to at least one vertex in X. Independent dominating sets of G are cliques of the complement $\text{G}$ of G and conversely.This work is concerned with the existence of disjoint independent dominating sets in a graph G. A new parameter, the maximum number of disjoint independent dominating sets in G, is studied and the class of graphs whose vertex sets partition into independent dominating sets is investigated.     

A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

Trees with extremal numbers of maximal independent sets including the set of leaves

A subset S of vertices of a graph G is independent if no two vertices in S are adjacent. In this paper we study maximal (with respect to set inclusion) independent sets in trees including the set of leaves. In particular the smallest and the largest number of these sets among n-vertex trees are determined characterizing corresponding trees. We define a local augmentation of trees that preserves the number of maximal independent sets including the set of leaves.     

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).Recognizing a polar graph is known to be NP-complete. These graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs. Besides, we give an algorithm in time O(n) for finding a largest induced polar subgraph in cographs; this also serves as a polar cograph recognition algorithm. We examine also the monopolar cographs which are the (s,k)-polar cographs where min(s,k)?1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.     

Bipartite Divisor Graphs for Integer Subsets

Inspired by connections described in a recent paper by Mark L. Lewis, between the common divisor graph Γ(X) and the prime vertex graph Δ(X), for a set X of positive integers, we define the bipartite divisor graph B(X), and show that many of these connections flow naturally from properties of B(X). In particular we establish links between parameters of these three graphs, such as number and diameter of components, and we characterise bipartite graphs that can arise as B(X) for some X. Also we obtain necessary and sufficient conditions, in terms of subconfigurations of B(X), for one of Γ(X) or Δ(X) to contain a complete subgraph of size 3 or 4.     

Maximal independent sets on a grid graph

An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics.     

Coverings of the complete (di-)graph with n vertices by complete bipartite (di-)graphs with n vertices I

Let n be an integer, n ? 2. A set $\text{M}$_n of complete bipartite (di-)graphs with n vertices is called a critical covering of the complete (di-)graph with n vertices if and only if the complete (di-)graph is covered by the (di-)graphs of $\text{M}$_n, but of no proper subset of $\text{M}$_n. All possible cardinalities of critical coverings $\text{M}$_n are determined for all integers n and for undirected as well as directed graphs.     

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.     

Chromatic Polynomials of Complements of Bipartite Graphs

We define a biclique to be the complement of a bipartite graph, consisting of two cliques joined by a number of edges. In this paper we study algebraic aspects of the chromatic polynomials of these graphs. We derive a formula for the chromatic polynomial of an arbitrary biclique, and use this to give certain conditions under which two of the graphs have chromatic polynomials with the same splitting field. Finally, we use a subfamily of bicliques to prove the cubic case of the α + n conjecture, by showing that for any cubic integer α, there is a natural number n such that α + n is a chromatic root.     

Products of non-σ-lower porous sets

In the present article we provide an example of two closed non-σ-lower porous sets A,B ? ? such that the product A × B is lower porous. On the other hand, we prove the following: Let X and Y be topologically complete metric spaces, let A ? X be a non-σ-lower porous Suslin set and let B ? Y be a non-σ-porous Suslin set. Then the product A × B is non-σ-lower porous. We also provide a brief summary of some basic properties of lower porosity, including a simple characterization of Suslin non-σ-lower porous sets in topologically complete metric spaces.     

Representation of proofs by colored graphs and the hadwiger conjecture

A tinted graph is a graph whose arcs are colored with certain colors. A colored graph is a graph whose vertices are colored with certain colors. If M is the set of tinted (or colored tinted) graphs of order k and G is a tinted (or colored tinted) graph, then we shall say that G is M-regular (or M-regularly colored) if all its subgraphs of order k belong to M. We shall show how, for any formula p of the first-order predicate calculus, to construct a finite set B_p of tinted graphs of order 3 and a finite set C_p of colored tinted graphs of order 2 such that ¦-p if and only if there exists a B_p-regular tinted graph not admitting a C_p-regular coloring. Hadwiger's conjecture (HC) is as follows: If no subgraph of a graph without loops G is contractible to a complete graph of order n, then the vertices of G can be colored in n–1 colors such that neighboring vertices are colored with different colors. We construct a formula X of the first-order predicate calculus such that HC is equivalent with X. Thus, HC reduces to HC₁: if all subgraphs of order 3 of the tinted graph G belong to B_X, then G is C_X-regularly colorable. Here B_X and C_X are specific finite sets of tinted graphs of order 3 and colored tinted graphs of order 2, respectively.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 209–216, 1979.     

On the diameter of the intersection graph of a finite simple group

Let G be a finite group. The intersection graph Δ_G of G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of G, and two distinct vertices X and Y are adjacent if X ∩ Y ≠ 1, where 1 denotes the trivial subgroup of order 1. A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters of intersection graphs of finite non-abelian simple groups have an upper bound 28. In particular, the intersection graph of a finite non-abelian simple group is connected.