The minimum forcing number of perfect matchings in the hypercube

Let $M$ be a perfect matching in a graph. A subset $S$ of $M$ is said to be a forcing set of $M$, if $M$ is the only perfect matching in the graph that contains $S$. The minimum size of a forcing set of $M$ is called the forcing number of $M$. Pachter and Kim (1998) conjectured that the forcing number of every perfect matching in the $n$-dimensional hypercube is $2^{n?2}$, for all $n\ge 2$. This was revised by Riddle (2002), who conjectured that it is at least $2^{n?2}$, and proved it for all even $n$. We show that the revised conjecture holds for all $n\ge 2$. The proof is based on simple linear algebra.     

Rainbow number of matchings in planar graphs

The rainbow number$rb(G,H)$ for the graph $H$ in $G$ is defined to be the minimum integer $c$ such that any $c$-edge-coloring of $G$ contains a rainbow $H$. As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching $k{K}_2$ in the plane triangulations, where the gap between the lower and upper bounds is $O\left(k^3\right)$. In this paper, we show that the rainbow number of the matching $k{K}_2$ in maximal outerplanar graphs of order $n$ is $n+O\left(k\right)$. Using this technique, we show that the rainbow number of the matching $k{K}_2$ in some subfamilies of plane triangulations of order $n$ is $2n+O\left(k\right)$. The gaps between our lower and upper bounds are only $O\left(k\right)$.     

A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs

The metric dimension dim(G)of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices.The zero forcing number Z(G)of a graph G is the minimum cardinality of a set S of black vertices(whereas vertices in V(G)\S are colored white)such that V(G)is turned black after finitely many applications of"the color-change rule":a white vertex is converted black if it is the only white neighbor of a black vertex.We show that dim(T)≤Z(T)for a tree T,and that dim(G)≤Z(G)+1 if G is a unicyclic graph;along the way,we characterize trees T attaining dim(T)=Z(T).For a general graph G,we introduce the"cycle rank conjecture".We conclude with a proof of dim(T)-2≤dim(T+e)≤dim(T)+1 for e∈E(T).     

The almost-disjointness number may have countable cofinality

We show that it is consistent for the almost-disjointness number to have countable cofinality. For example, it may be equal to .

     

Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph G (the coloring may not be proper), a rainbow path in G is a path without two edges colored the same; G is rainbow connected if for any two vertices of G, there is a rainbow path connecting them. Rainbow connection number, rc(G), of G is the minimum number of colors needed to color its edges such that G is rainbow connected. Chakraborty et al. (2011) [5] proved that computing rc(G) is NP-hard and deciding if rc(G)=2 is NP-complete. When edges of G are colored with fixed number k of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether G is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is k rainbow connected for suitably large k and can be given a rainbow coloring in polynomial time.     

Forcing matchings on square grids

Let G be a graph that admits a perfect matching. The forcing number of a perfect matching M of G is defined as the smallest number of edges in a subset S M, such that S is in no other perfect matching. We show that for the 2n × 2n square grid, the forcing number of any perfect matching is bounded below by n and above by n². Both bounds are sharp. We also establish a connection between the forcing problem and the minimum feedback set problem. Finally, we present some conjectures about forcing numbers in other graphs.     

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.     

Graphs with the second largest number of maximal independent sets

Let G be a simple undirected graph. Denote by (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of among all graphs of order n and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.     

Trees with the second largest number of maximal independent sets

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all trees and forests of order n≥4. We also characterize those extremal graphs achieving these values.     

On the size of maximal chains and the number of pairwise disjoint maximal antichains

For each integer k≥3, we find all maximal intervals I_k of natural numbers with the following property: whenever the number of elements in every maximal chain in a finite partially ordered set P lies in I_k, then P contains k pairwise disjoint maximal antichains. All such I_k are of the form

     

Small subsets of the reals and tree forcing notions

We discuss the question of which properties of smallness in the sense of measure and category (e.g. being a universally null, perfectly meager or strongly null set) imply the properties of smallness related to some tree forcing notions (e.g. the properties of being Laver-null or Miller-null).

     

Polar graphs and maximal independent sets

We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1,2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1,1)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (α,β)-polar graphs and study the computational complexity of the problems on polar graphs of special types.     

Enumerating maximal independent sets with applications to graph colouring

We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph.     

Special subsets of the reals and tree forcing notions

We study relationships between classes of special subsets of the reals (e.g. meager-additive sets, -sets, -sets, -sets) and the ideals related to the forcing notions of Laver, Mathias, Miller and Silver.

     

Erdős matching conjecture for almost perfect matchings

In 1965 Erd?s asked, what is the largest size of a family of k-element subsets of an n-element set that does not contain a matching of size $s+1$? In this note, we improve upon a recent result of Frankl and resolve this problem for $s>101k^3$ and $(s+1)k?n<(s+1)(k+\frac{1}{100k})$.