共查询到20条相似文献,搜索用时 15 毫秒
2.
3.
Annegret K. Wagler 《Mathematical Methods of Operations Research》2002,56(1):127-149
An edge e of a perfect graph G is critical if G−e is imperfect. We would like to decide whether G−e is still “almost perfect” or already “very imperfect”. Via relaxations of the stable set polytope of a graph, we define two
superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how
far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph
of a bipartite graph or from the complement of such a graph. 相似文献
4.
5.
6.
Perfect graphs constitute a well-studied graph class with a rich structure, which is reflected by many characterizations with
respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) equals the fractional stable set polytope QSTAB(G). The dilation ratio of the two polytopes yields the imperfection ratio of G. It is NP-hard to compute and, for most graph classes, it is even unknown whether it is bounded. For graphs G such that all facets of STAB(G) are rank constraints associated with antiwebs, we characterize the imperfection ratio and bound it by 3/2. Outgoing from
this result, we characterize and bound the imperfection ratio for several graph classes, including near-bipartite graphs and
their complements, namely quasi-line graphs, by means of induced antiwebs and webs, respectively.
相似文献
7.
8.
10.
11.
In this paper we present a lower bound of the disjunctive rank of the facets describing the stable set polytope of joined a-perfect graphs. This class contains near-bipartite, t-perfect, h-perfect and complement of fuzzy interval graphs, among others. The stable set polytope of joined a-perfect graphs is described by means of full rank constraints of its node induced prime antiwebs. As a first step, we completely determine the disjunctive rank of all these constraints. Using this result we obtain a lower bound of the disjunctive index of joined a-perfect graphs and prove that this bound can be achieved. In addition, we completely determine the disjunctive index of every antiweb and observe that it does not always coincide with the disjunctive rank of its full rank constraint. 相似文献
12.
Jo Ann W. Staples 《Journal of Graph Theory》1979,3(2):197-204
A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well-covered graphs are classified by the Wn property: For a positive integer n, a graph G belongs to class Wn if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of Wn graphs containing arbitrarily large independent sets. A characterization of Wn graphs in terms of well-covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in Wn graphs. 相似文献
13.
Francisco Barahona 《Mathematical Programming》1993,60(1-3):53-68
We study the max cut problem in graphs not contractible toK
5, and optimum perfect matchings in planar graphs. We prove that both problems can be formulated as polynomial size linear programs.Supported by the joint project Combinatorial Optimization of the Natural Sciences and Engineering Research Council of Canada and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303). 相似文献
14.
15.
Alberto Alexandre Assis Miranda Cláudio Leonardo Lucchesi 《Discrete Applied Mathematics》2010,158(12):1275-1278
A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e1 and e2 such that G−e1−e2 is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class. 相似文献
16.
Sebastián Ceria 《Mathematical Programming》2003,98(1-3):309-317
We analyze the application of lift-and-project to the clique relaxation of the stable set polytope. We characterize all the inequalities that can be generated through the application of the lift-and-project procedure, introduce the concept of 1-perfection and prove its equivalence to minimal imperfection. This characterization of inequalities and minimal imperfection leads to a generalization of the Perfect Graph Theorem of Lovász, as proved by Aguilera, Escalante and Nasini [1].Mathematics Subject Classification:05C17, 90C57 相似文献
17.
Anna Galluccio Claudio Gentile Paolo Ventura 《Discrete Applied Mathematics》2013,161(13-14):1988-2000
18.
For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two. 相似文献
19.
We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of when G is claw-free. 相似文献
20.
David Galvin 《Discrete Mathematics》2011,311(20):2105
Let it(G) denote the number of independent sets of size t in a graph G. Levit and Mandrescu have conjectured that for all bipartite G the sequence (it(G))t≥0 (the independent set sequence of G) is unimodal. We provide evidence for this conjecture by showing that this is true for almost all equibipartite graphs. Specifically, we consider the random equibipartite graph G(n,n,p), and show that for any fixed p∈(0,1] its independent set sequence is almost surely unimodal, and moreover almost surely log-concave except perhaps for a vanishingly small initial segment of the sequence. We obtain similar results for .We also consider the problem of estimating i(G)=∑t≥0it(G) for G in various families. We give a sharp upper bound on the number of independent sets in an n-vertex graph with minimum degree δ, for all fixed δ and sufficiently large n. Specifically, we show that the maximum is achieved uniquely by Kδ,n−δ, the complete bipartite graph with δ vertices in one partition class and n−δ in the other.We also present a weighted generalization: for all fixed x>0 and δ>0, as long as n=n(x,δ) is large enough, if G is a graph on n vertices with minimum degree δ then ∑t≥0it(G)xt≤∑t≥0it(Kδ,n−δ)xt with equality if and only if G=Kδ,n−δ. 相似文献