An exact algorithm for the maximum stable set problem

We describe a new branch-and-bound algorithm for the exact solution of the maximum cardinality stable set problem. The bounding phase is based on a variation of the standard greedy algorithm for finding a colouring of a graph. Two different node-fixing heuristics are also described. Computational tests on random and structured graphs and very large graphs corresponding to real-life problems show that the algorithm is competitive with the fastest algorithms known so far.This work has been supported by Agenzia Spaziale Italiana.     

On the maximum number of minimum dominating sets in forests

Fricke, Hedetniemi, Hedetniemi, and Hutson asked whether every tree with domination number $\gamma$ has at most $2^{\gamma }$ minimum dominating sets. Bień gave a counterexample, which allows us to construct forests with domination number $\gamma$ and $2.0598^{\gamma }$ minimum dominating sets. We show that every forest with domination number $\gamma$ has at most $2.4606^{\gamma }$ minimum dominating sets, and that every tree with independence number $\alpha$ has at most $2^{\alpha -1}+1$ maximum independent sets.     

Hitting all maximum cliques with a stable set using lopsided independent transversals

Rabern recently proved that any graph with contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with . This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding an independent transversal in a graph partitioned into vertex sets of unequal size. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:300‐305, 2011     

Virtually stable maps and their fixed point sets

We introduce the concept of virtually stable selfmaps of Hausdorff spaces, which generalizes virtually nonexpansive selfmaps of metric spaces introduced in the previous work by the first author, and explore various properties of their convergence sets and fixed point sets. We also prove that the fixed point set of a virtually stable selfmap satisfying a certain kind of homogeneity is always star-convex.     

The 0–1 inverse maximum stable set problem

In this paper we study the 0–1 inverse maximum stable set problem, denoted by IS_{0,1}. Given a graph and a fixed stable set, it is to delete the minimum number of vertices to make this stable set maximum in the new graph. We also consider IS_{0,1} against a specific algorithm such as Greedy and 2opt, aiming to delete the minimum number of vertices so that the algorithm selects the given stable set in the new graph; we denote them by IS_{0,1},greedy and IS_{0,1},2opt, respectively. Firstly, we show that they are NP-hard, even if the fixed stable set contains only one vertex. Secondly, we achieve an approximation ratio of for IS_{0,1},2opt. Thirdly, we study the tractability of IS_{0,1} for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of IS_{0,1} and IS_{0,1},2opt for some other classes of graphs.     

Some observations on maximum weight stable sets in certain P5-free graphs

The maximum weight stable set problem (MWS) is the weighted version of the maximum stable set problem (MS), which is NP-hard. The class of P₅-free graphs – i.e., graphs with no induced path of five vertices – is the unique minimal class, defined by forbidding a single connected subgraph, for which the computational complexity of MS is an open question. At the same time, it is known that MS can be efficiently solved for (_P5,F)$(P_5\text{,}F)$-free graphs, where F is any graph of five vertices different to a C₅. In this paper we introduce some observations on P₅-free graphs, and apply them to introduce certain subclasses of such graphs for which one can efficiently solve MWS. That extends or improves some known results, and implies – together with other known results – that MWS can be efficiently solved for (_P5,F)$(P_5\text{,}F)$-free graphs where F is any graph of five vertices different to a C₅.     

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664ⁿ) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).     

Constant tolerance intersection graphs of subtrees of a tree

A chordal graph is the intersection graph of a family of subtrees of a host tree. In this paper we generalize this. A graph G=(V,E) has an (h,s,t)-representation if there exists a host tree T of maximum degree at most h, and a family of subtrees {S_v}_v∈V of T, all of maximum degree at most s, such that uv∈E if and only if |S_u∩S_v|?t. For given h,s, and t, there exist infinitely many forbidden induced subgraphs for the class of (h,s,t)-graphs. On the other hand, for fixed h?s?3, every graph is an (h,s,t)-graph provided that we take t large enough. Under certain conditions representations of larger graphs can be obtained from those of smaller ones by amalgamation procedures. Other representability and non-representability results are presented as well.     

最大度为5的图的Alcuin数

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.     

Computing the maximum clique in the visibility graph of a simple polygon

In this paper, we present an algorithm for computing the maximum clique in the visibility graph G of a simple polygon P in O(n²e) time, where n and e are number of vertices and edges of G respectively. We also present an O(ne) time algorithm for computing the maximum hidden vertex set in the visibility graph G of a convex fan P. We assume in both algorithms that the Hamiltonian cycle in G that corresponds to the boundary of P is given as an input along with G.     

Vertices contained in all minimum paired-dominating sets of a tree

A set S of vertices in a graph G is called a paired-dominating set if it dominates V and 〈S〉 contains at least one perfect matching. We characterize the set of vertices of a tree that are contained in all minimum paired-dominating sets of the tree.     

Toric rings generated by special stable sets of monomials

In this paper we consider some subalgebras of the d-th Veronese subring of a polynomial ring, generated by stable subsets of monomials. We prove that these algebras are Koszul, showing that the presentation ideals have Gröbner bases of quadrics with respect to suitable term orders. Since the initial monomials of the elements of these Gröbner bases are square- free, it follows by a result of STURMFELS [S, 13.15], that the algebras under consideration are normal, and thus Cohen-Macaulay.     

Vertices contained in all or in no minimum total dominating set of a tree

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. We characterize the set of vertices of a tree that are contained in all, or in no, minimum total dominating sets of the tree.