Ideals and graphs,Gröbner bases and decision procedures in graphs

The well known correspondence between even cycles of an undirected graph and polynomials in a binomial ideal associated to a graph is extended to odd cycles and polynomials in another binomial ideal. Other binomial ideals associated to an undirected graph are also introduced. The results about them with topics on monomial ideals are used in order to show decision procedures for bipartite graphs, minimal vertex covers, cliques, edge covers and matchings with algebraic tools. All such procedures are implemented in Maple 9.5.     

Chain hexagonal cacti: Matchings and independent sets

In this paper we consider three classes of chain hexagonal cacti and study their matching and independence related properties. Explicit recurrences are derived for their matching and independence polynomials, and explicit formulae are presented for the number of matchings and independents sets of certain types. Bivariate generating functions for the number of matchings and independent sets of certain types are also computed and then used to deduce the expected size of matchings and independent sets in chains of given length. It is shown that the extremal chain hexagonal cacti with respect to the number of matchings and of independent sets belong to one of the considered types. Possible directions of further research are discussed.     

Maximal tight sets and the edmonds—Gallai decomposition for matchings

The Edmonds—Gallai decomposition theorem for matchings of finite or locally finite graphs is generalized to matchings of the kernel of an arbitrary graph.     

Total matchings and total coverings of graphs

In graph theory, the related problems of deciding when a set of vertices or a set of edges constitutes a maximum matching or a minimum covering have been extensively studied. In this paper we generalize these ideas by defining total matchings and total coverings, and show that these sets, whose elements in general consist of both vertices and edges, provide a way to unify these concepts. Parameters denoting the maximum and the minimum cardinality of these sets are introduced and upper and lower bounds depending only on the order of the graph are obtained for the number of elements in arbitrary total matchings and total coverings. Precise values of all the parameters are found for several general classes of graphs, and these are used to establish the sharpness of most of the bounds. In addition, variations of some well known equalities due to Gallai relating covering and matching numbers are obtained.     

Disjoint cliques and disjoint maximal independent sets of vertices in graphs

In this paper, we find lower bounds for the maximum and minimum numbers of cliques in maximal sets of pairwise disjoint cliques in a graph. By complementation, these yield lower bounds for the maximum and minimum numbers of independent sets in maximal sets of pairwise disjoint maximal independent sets of vertices in a graph. In the latter context, we show by examples that one of our bounds is best possible.     

Matching preclusion and conditional matching preclusion for regular interconnection networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks.     

Detecting strong cliques

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs.     

最大匹配的路变换图

图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.     

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete.     

Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees

We derive closed formulas for the numbers of independent sets of size at most 4 and matchings of size at most 3 in graphs without small cycles that depend only on the degree sequence and the products of the degrees of adjacent vertices.

As a related problem we describe an algorithm that determines a tree of given degree sequence that maximizes the sum of the products of the degrees of adjacent vertices.     

Commuting difference operators, spinor bundles and the asymptotics of orthogonal polynomials with respect to varying complex weights

The paper has three parts. In the first part we apply the theory of commuting pairs of (pseudo) difference operators to the (formal) asymptotics of orthogonal polynomials: using purely geometrical arguments we show heuristically that the asymptotics, for large degrees, of orthogonal polynomial with respect to varying weights is intimately related to certain spinor bundles on a hyperelliptic algebraic curve reproducing formulae appearing in the works of Deift et al. on the subject.In the second part we show that given an arbitrary nodal hyperelliptic curve satisfying certain conditions of admissibility we can reconstruct a sequence of polynomials orthogonal with respect to semiclassical complex varying weights supported on several curves in the complex plane. The strong asymptotics of these polynomials will be shown to be given by the spinors introduced in the first part using a Riemann-Hilbert analysis.In the third part we use Strebel theory of quadratic differentials and the procedure of welding to reconstruct arbitrary admissible hyperelliptic curves. As a result we can obtain orthogonal polynomials whose zeroes may become dense on a collection of Jordan arcs forming an arbitrary forest of trivalent loop-free trees.     

On Infinite Cycles II

We adapt the cycle space of a finite or locally finite graph to graphs with vertices of infinite degree, using as cycles the homeomorphic images of the unit circle S¹ in the graph together with its ends. We characterize the spanning trees whose fundamental cycles generate this cycle space, and prove infinite analogues to the standard characterizations of finite cycle spaces in terms of edge-decomposition into single cycles and orthogonality to cuts.To the memory of C. St. J. A. Nash-Williams     

On Infinite Cycles I

We adapt the cycle space of a finite graph to locally finite infinite graphs, using as infinite cycles the homeomorphic images of the unit circle S¹ in the graph compactified by its ends. We prove that this cycle space consists of precisely the sets of edges that meet every finite cut evenly, and that the spanning trees whose fundamental cycles generate this cycle space are precisely the end-faithful spanning trees. We also generalize Eulers theorem by showing that a locally finite connected graph with ends contains a closed topological curve traversing every edge exactly once if and only if its entire edge set lies in this cycle space.To the memory of C. St. J. A. Nash-Williams     

Die chromatischen Polynome unterringfreier Graphen

Let G be a finite undirected graph without loops and multiple edges. A graph is called “unterringfrei”, if there is no induced subgraph being a cycle of length?4. This note shows that the chromatic polynomial of such a graph does only have positive integers as its roots. Conversely all polynomials with only positive integral roots are the chromatic polynomials of such graphs under the slight restriction that M(G;α)=0 implies that M(G;β)=0 for α>β?0.     

Matching polynomials for chains of cycles

Došli? and Måløy (2010) [2] obtained the extremal 6-cactus chains with respect to the number of matchings and of independent sets. Motivated by the prior paper, in this paper we give recurrences for matching polynomials of ortho-chains and meta-chains, and show that they are the h-cactus chains with the most matchings.     

Decomposing Various Graphs into Short Even-Length Cycles

We prove that a complete bipartite graph can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, the length of each cycle is at most the size of the smallest part, and the longest cycle is at most three times as long as the second longest. We then use this result to obtain results on incomplete even cycle systems with a hole and on decompositions of complete multipartite graphs into cycles of uniform even length.     

Covers,matching and odd cycles of a graph

We link some well-known theorems and prove some new ones, each on one or more of the items of the title, and together illustrating their close relationship. The main tools are well-known similar conditions on maximum stable sets and maximum matchings, by which we prove theorems on the existence of odd cycles, including a generalization of Konig's equality between the matching and covering numbers of a bipartite graph. We deal with the question “How nearly bipartite is a graph?” and conjecture an inequality involving the matching and covering numbers and the number of disjoint odd cycles.     

Linearization Coefficients of Bessel Polynomials and Properties of Student t-Distributions

We prove positivity results about linearization and connection coefficients for Bessel polynomials. The proof is based on a recursion formula and explicit formulas for the coefficients in special cases. The result implies that the distribution of a finite convex combination of independent Student t-variables with arbitrary odd degrees of freedom has a density which is a finite convex combination of certain Student t-densities with odd degrees of freedom.