Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

A matching M is uniquely restricted in a graph G if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself [M.C. Golumbic, T. Hirst, M. Lewenstein, Uniquely restricted matchings, Algorithmica 31 (2001) 139-154]. G is a König-Egerváry graph provided α(G)+μ(G)=|V(G)| [R.W. Deming, Independence numbers of graphs—an extension of the König-Egerváry theorem, Discrete Math. 27 (1979) 23-33; F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, J. Combin. Theory Ser. B 27 (1979) 228-229], where μ(G) is the size of a maximum matching and α(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G, and we write S∈Ψ(G), if S is a maximum stable set of the subgraph spanned by S∪N(S), where N(S) is the neighborhood of S. Nemhauser and Trotter [Vertex packings: structural properties and algorithms, Math. Programming 8 (1975) 232-248], proved that any S∈Ψ(G) is a subset of a maximum stable set of G. In [V.E. Levit, E. Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Appl. Math. 132 (2003) 163-174] we have proved that for a bipartite graph G,Ψ(G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. In this paper we demonstrate that if G is a triangle-free graph, then Ψ(G) is a greedoid if and only if all its maximum matchings are uniquely restricted and for any S∈Ψ(G), the subgraph spanned by S∪N(S) is a König-Egerváry graph.     

Improving an Upper Bound on the Stability Number of a Graph

In previous works an upper bound on the stability number of a graph based on quadratic programming was introduced and several of its properties were given. The graphs for which this bound is attained has been known as graphs with convex-QP stability number. This paper proposes a new upper bound on the stability number whose determination is also done by quadratic programming. It is proved that the new bound improves the above mentioned bound and several computational tests asserting its interest for large graphs are presented. In addition a necessary and sufficient condition for a graph to attain the new bound is proved. As a consequence a graph with convex-QP stability number also attains the new bound. On the other hand it is shown the existence of graphs attaining the new bound that do not belong to the class of graphs with convex-QP stability number. This allows to assert that the class of graphs with convex-QP stability number is strictly included in the class of graphs that attain the introduced bound. Some conclusions and lines for future work finalize the paper.     

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.     

图G中f-因子的一个结论

在简单图的顶点度和f-因子的关系方面,本文在Tutte定理的基础上给出了图G不存在f-因子时的一个结论.     

Hausdorff Dimension for Range and Graph of Multi-Parameter Operator Stable L\'{e}vy Processes

??The lower Hausdorff dimension results for the range and the graph of multi-parameter operator stable L\'{e}vy processes are established. The consequences are completely determined by the eigenvalues of its exponent matrix.     

Constraint Programming Based Lagrangian Relaxation for the Automatic Recording Problem

Whereas CP methods are strong with respect to the detection of local infeasibilities, OR approaches have powerful optimization abilities that ground on tight global bounds on the objective. An integration of propagation ideas from CP and Lagrangian relaxation techniques from OR combines the merits of both approaches. We introduce a general way of how linear optimization constraints can strengthen their propagation abilities via Lagrangian relaxation. The method is evaluated on a set of benchmark problems stemming from a multimedia application. The experiments show the superiority of the combined method compared with a pure OR approach and an algorithm based on two independent optimization constraints.     

Hausdorff Dimension for Range and Graph of Multi-Parameter Operator Stable L\'{e}vy Processes

The lower Hausdorff dimension results for the range and the graph of multi-parameter operator stable L\'{e}vy processes are established. The consequences are completely determined by the eigenvalues of its exponent matrix.     

Graphs that are not complete pluripolar

Let be domains in . Under very mild conditions on we show that there exist holomorphic functions , defined on with the property that is nowhere extendible across , while the graph of over is not complete pluripolar in . This refutes a conjecture of Levenberg, Martin and Poletsky (1992).

     

New Local Conditions for a Graph to be Hamiltonian

For a vertex w of a graph G the ball of radius 2 centered at w is the subgraph of G induced by the set M₂(w) of all vertices whose distance from w does not exceed 2. We prove the following theorem: Let G be a connected graph where every ball of radius 2 is 2-connected and d(u)+d(v)≥|M₂(w)|−1 for every induced path uwv. Then either G is hamiltonian or for some p≥2 where ∨ denotes join. As a corollary we obtain the following local analogue of a theorem of Nash-Williams: A connected r-regular graph G is hamiltonian if every ball of radius 2 is 2-connected and for each vertex w of G. Supported by the Swedish Research Council (VR)     

The aggregation operations for decision making in probabilistic fuzzy environment

This paper deals with some important classes of aggregation operations on various kinds of sets applied to decision making problems.These operations are mainly based on general concepts such as triangular norms (t- and s-norms). In this paper we focus particularly on operations on probabilistic sets and their distribution function representation. The considerations are illustrated by means of numerical examples.     

On the subset sum problem for finite fields

Let G be the additive group of a finite field. J. Li and D. Wan determined the exact number of solutions of the subset sum problem over G, by giving an explicit formula for the number of subsets of G of prescribed size whose elements sum up to a given element of G. They also determined a closed-form expression for the case where the subsets are required to contain only nonzero elements. In this paper we give an alternative proof of the two formulas. Our argument is purely combinatorial, as in the original proof by Li and Wan, but follows a different and somehow more “natural” approach. We also indicate some new connections with coding theory and combinatorial designs.     

关于随机紧凸集的更新定理

该文在讨论了多维更新定理的基础上,重点研究了随机紧凸集的Minkowski和的更新定理,得到了一系列重要结论.     

关于广义蝶图的平衡指标集

In this paper, we introduce the concept of the general butterfly graph B[m, n; d] for integers m,n ≥ 3, d ≥ 1, determine its balance index set, and give the necessary and sufficient condition for balanced graph B[m, n; d] to exist.     

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     

Graph algorithm for partially-linear problems obtained by absolute value functions

The increasing interest in partially-linear models is caused by their role in economics, technology and mathematics. Every continuous partially-linear function with a finite number of linear parts can be formulated by means of linear function and absolute value functions. If we presebt every absolote value function as vertex of a graph we obtain the graph interpretaion of this optimization problem. The Partially-linear problems are often not only nondifferentiable but nonconvex as well,which makes their solving by standard optimization methods difficult. In this work we give the necessary and sufficient conditions for local optimality. An algorithm for solving such problems, based on the constructive optimization methods is suggested.     

带线性坍塌项和竞争势的非线性波动方程柯西问题的稳定集和不稳定集(英文)

本文考虑带线性坍塌项和竞争势的非线性波动方程柯西问题,定义了新的稳定集和不稳定集,证明了如果初值进入不稳定集,则解在有限时间爆破;如果初值进入稳定集,则整体解存在.运用势井讨论,回答了当初值在多么小的时候,该柯西问题的整体解存在.     

收缩临界6连通图的6度顶点

利用断片的性质,改进了齐恩凤,齐登记等的研究结果,得到了收缩临界6-连通图中6度点的性质的新结果:设x是G中任意一点,设A是一个x-原子,记N_A=T_A,N(x)∩T_A≠Φ,则A∩T_A中有与x相邻的6度点或两点的距离为2.     

The distance-regular graphs such that all of its second largest local eigenvalues are at most one

In this paper, we classify distance regular graphs such that all of its second largest local eigenvalues are at most one. Also we discuss the consequences for the smallest eigenvalue of a distance-regular graph. These extend a result by the first author, who classified the distance-regular graphs with smallest eigenvalue .