Search
Search Results
-
A short survey on stable polynomials, orientations and matchings
This is a short survey about the theory of stable polynomials and its applications. It gives self-contained proofs of two theorems of Schrijver. One...
-
One-factorisations of complete graphs arising from hyperbolae in the Desarguesian affine plane
In a recent paper Korchmáros et al. (J Combin Theory Ser A 160:62–83,
2018 ) the geometry of finite planes is exploited for the construction of... -
Perfect matchings in random intersection graphs
Let W 1 ,…, W n be independent random subsets of [ m ]={1,…, m }. Assuming that each W i is uniformly distributed in the class of d -subsets of [ m ] we study...
-
Foolproof eternal domination in the all-guards move model
The eternal domination problem requires a graph be protected against an infinitely long sequence of attacks at vertices, by guards located at...
-
Rates of convergence for partial mass problems
We consider a class of partial mass problems in which a fraction of the mass of a probability measure is allowed to be changed (trimmed) to maximize...
-
Small Edge Sets Meeting all Triangles of a Graph
It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a...
-
Applications of Perfect Matchings in Chemistry
Perfect matchings or one factors in mathematics correspond to Kekulé structures in chemistry. In this chapter, we present methods for determination...
-
Partitions of Graphs
Many difficult optimization problems on graphs become tractable when restricted to some classes of graphs, usually to hereditary classes. A large...
-
Decompositions and Factorizations of Complete Graphs
Graph decompositions into isomorphic copies of a given graph are a well-established topic studied in both graph theory and design theory. Although...
-
Domination in Graphs
A set of vertices S in a graph G dominates G if every vertex in G is either in S or adjacent to a vertex in S. The size of any smallest dominating...
-
Graph Polynomials and Their Applications II: Interrelations and Interpretations
We survey a variety of graph polynomials, giving a brief overview of techniques for defining a graph polynomial and then for decoding the...
-
The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability
In 1952 Lee and Yang proposed the program of analyzing phase transitions in terms of zeros of partition functions. Linear operators preserving...
-
Coverings of the Vertices of a Graph by Small Cycles
Given a graph G with n vertices, we call c k ( G ) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G . We...
-
On the Generalization of the Matroid Parity Problem
Let T 1, T 2, ..., T t be disjoint κ-element sets and let their union be denoted by S. Let A be a subset of...
-
Excessive Factorizations of Regular Graphs
An excessive factorization of a graph G is a minimum set F of 1-factors of G whose union is E(G). In this paper we study excessive factorizations of...
-
Structural Remarks on Bipartite Graphs with Unique f-Factors
In this note we will derive some structural results for a bipartite graph G with a unique f -factor. Two necessary conditions will be that G is...
-
Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs
Given a function f : ℕ→ℝ, call an n -vertex graph f -connected if separating off k vertices requires the deletion of at least f ( k ) vertices whenever k ≤(
-
Restricted 2-factor polytopes
The optimal k -restricted 2-factor problem consists of finding, in a complete undirected graph K n , a minimum cost 2-factor (subgraph having degree 2...
-
On the Absence of Phase Transition in the Monomer-Dimer Model
Suppose we cover the set of vertices of a graph G by non-overlap** monomers (singleton sets) and dimers (pairs of vertices corresponding to an...