共查询到20条相似文献,搜索用时 46 毫秒
1.
Gentner and Rautenbach conjectured that the size of a minimum zero forcing set in a connected graph on vertices with maximum degree is at most . We disprove this conjecture by constructing a collection of connected graphs with maximum degree 3 of arbitrarily large order having zero forcing number at least . 相似文献
2.
Let be a finite simple graph. For , the difference of , where is the neighborhood of and is called the critical difference of . is called a critical set if equals the critical difference and is the intersection of all critical sets. is the union of all critical independent sets. An independent set is an inclusion minimal set with if no proper subset of has positive difference.A graph is called a König–Egerváry graph if the sum of its independence number and matching number equals .In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set with is at least the critical difference of the graph.We also give a new short proof of the inequality .A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph , the critical difference equals , is proved.We also make an observation about using Edmonds–Gallai Structure Theorem as a concluding remark. 相似文献
3.
For a graph , let denote its number of vertices, its minimum degree and its cycle space. Call a graph Hamilton-generated if and only if every cycle in is a symmetric difference of some Hamilton circuits of . The main purpose of this paper is to prove: for every there exists such that for every graph with vertices,
- (1)if and is odd, then is Hamilton-generated,
- (2)if and is even, then the set of all Hamilton circuits of generates a codimension-one subspace of and the set of all circuits of having length either or generates all of ,
- (3)if and is balanced bipartite, then is Hamilton-generated.
4.
A graph has a perfect matching if and only if is not a root of its matching polynomial . Thus, Tutte’s famous theorem asserts that is not a root of if and only if for all , where denotes the number of odd components of . Tutte’s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte’s theorem in terms of avoiding any given real number as a root of . We also extend maximal non-matchable graphs to maximal -non-matchable graphs and determine the structure of such graphs. 相似文献
5.
John Bamberg S.P. Glasby Luke Morgan Alice C. Niemeyer 《Journal of Pure and Applied Algebra》2018,222(10):2931-2951
Let be a prime. For each maximal subgroup with , we construct a d-generator finite p-group G with the property that induces H on the Frattini quotient and . A significant feature of this construction is that is very small compared to , shedding new light upon a celebrated result of Bryant and Kovács. The groups G that we exhibit have exponent p, and of all such groups G with the desired action of H on , the construction yields groups with smallest nilpotency class, and in most cases, the smallest order. 相似文献
6.
7.
Vahan V. Mkrtchyan Samvel S. Petrosyan Gagik N. Vardanyan 《Discrete Mathematics》2010,310(10-11):1588-1613
For and a cubic graph let denote the maximum number of edges that can be covered by matchings. We show that and . Moreover, it turns out that . 相似文献
8.
9.
10.
The decycling number of a graph is the smallest number of vertices which can be removed from so that the resultant graph contains no cycle. A decycling set containing exactly vertices of is called a -set. For any decycling set of a -regular graph , we show that , where is the cycle rank of , is the margin number of , and are, respectively, the number of components of and the number of edges in . In particular, for any -set of a 3-regular graph , we prove that , where is the Betti deficiency of . This implies that the decycling number of a 3-regular graph is . Hence for a 3-regular upper-embeddable graph , which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute , the cardinality of a maximum nonseparating independent set in a -regular graph , which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph , we show that for any -set of , there exists a spanning tree of such that the elements of are simply the leaves of with at most two exceptions providing . On the other hand, if is a loopless graph on vertices with maximum degree at most , then The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006). 相似文献
11.
Nina Zubrilina 《Discrete Mathematics》2018,341(7):2083-2088
Given a connected graph , the edge dimension, denoted , is the least size of a set that distinguishes every pair of edges of , in the sense that the edges have pairwise different tuples of distances to the vertices of . The notation was introduced by Kelenc, Tratnik, and Yero, and in their paper they posed several questions about various properties of . In this article we answer two of these questions: we classify the graphs on vertices for which
and show that
is not bounded from above (here is the standard metric dimension of ). We also compute and . 相似文献
12.
13.
14.
15.
16.
17.
Consider a graph consisting of a vertex set and an edge set . Let and denote the maximum degree and the chromatic number of , respectively. We say that is equitably -colorable if there exists a proper -coloring of such that the sizes of any two color classes differ by at most one. Obviously, if is equitably -colorable, then . Conversely, even if satisfies , we cannot guarantee that must be equitably -colorable. In 1994, the Equitable -Coloring Conjecture asserts that a connected graph with is equitably -colorable if is different from for all . In this paper, we give necessary conditions for a graph (not necessarily connected) with to be equitably -colorable and prove that those necessary conditions are also sufficient conditions when is a bipartite graph, or satisfies , or satisfies . 相似文献
18.
19.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献