共查询到20条相似文献,搜索用时 0 毫秒
1.
Ajit A. Diwan 《Discrete Mathematics》2019,342(4):1060-1062
Let be a perfect matching in a graph. A subset of is said to be a forcing set of , if is the only perfect matching in the graph that contains . The minimum size of a forcing set of is called the forcing number of . Pachter and Kim (1998) conjectured that the forcing number of every perfect matching in the -dimensional hypercube is , for all . This was revised by Riddle (2002), who conjectured that it is at least , and proved it for all even . We show that the revised conjecture holds for all . The proof is based on simple linear algebra. 相似文献
2.
3.
The rainbow number for the graph in is defined to be the minimum integer such that any -edge-coloring of contains a rainbow . 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 in the plane triangulations, where the gap between the lower and upper bounds is . In this paper, we show that the rainbow number of the matching in maximal outerplanar graphs of order is . Using this technique, we show that the rainbow number of the matching in some subfamilies of plane triangulations of order is . The gaps between our lower and upper bounds are only . 相似文献
4.
A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
下载免费PDF全文
![点击此处可从《数学学报(英文版)》网站下载免费的PDF全文](/ch/ext_images/free.gif)
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). 相似文献
5.
We show that it is consistent for the almost-disjointness number to have countable cofinality. For example, it may be equal to .
6.
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. 相似文献
7.
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 n2. 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. 相似文献
8.
Xiaoyan Jiang Heping Zhang 《Discrete Applied Mathematics》2011,159(15):1581-1593
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. 相似文献
9.
Zemin Jin 《Discrete Mathematics》2008,308(23):5864-5870
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. 相似文献
10.
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. 相似文献
11.
12.
For each integer k≥3, we find all maximal intervals Ik 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 Ik, then P contains k pairwise disjoint maximal antichains. All such Ik are of the form
13.
14.
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).
15.
16.
17.
Vadim V. Lozin 《Discrete Mathematics》2006,306(22):2901-2908
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. 相似文献
18.
Jesper Makholm Byskov 《Operations Research Letters》2004,32(6):547-556
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. 相似文献
19.
Marcin Kysiak Andrzej Nowik Tomasz Weiss 《Proceedings of the American Mathematical Society》2007,135(9):2975-2982
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.
20.
《Discrete Mathematics》2023,346(4):113304
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 ? In this note, we improve upon a recent result of Frankl and resolve this problem for and . 相似文献