Currently displaying 1 – 9 of 9

Showing per page

Order by Relevance | Title | Year of publication

A Note on the Uniqueness of Stable Marriage Matching

Ewa Drgas-Burchardt — 2013

Discussiones Mathematicae Graph Theory

In this note we present some sufficient conditions for the uniqueness of a stable matching in the Gale-Shapley marriage classical model of even size. We also state the result on the existence of exactly two stable matchings in the marriage problem of odd size with the same conditions.

Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties

Ewa Drgas-Burchardt — 2009

Discussiones Mathematicae Graph Theory

An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let L a denote a class of all such properties. In the paper, we consider H-reducible over L a properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

A note on joins of additive hereditary graph properties

Ewa Drgas-Burchardt — 2006

Discussiones Mathematicae Graph Theory

Let L a denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set ( L a , ) is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in ( L a , ) has a finite or infinite family of minimal forbidden subgraphs.

Maximal hypergraphs with respect to the bounded cost hereditary property

Ewa Drgas-BurchardtAnna Fiedorowicz — 2005

Discussiones Mathematicae Graph Theory

The hereditary property of hypergraphs generated by the cost colouring notion is considered in the paper. First, we characterize all maximal graphs with respect to this property. Second, we give the generating function for the sequence describing the number of such graphs with the numbered order. Finally, we construct a maximal hypergraph for each admissible number of vertices showing some density property. All results can be applied to the problem of information storage.

Forbidden Structures for Planar Perfect Consecutively Colourable Graphs

Marta Borowiecka-OlszewskaEwa Drgas-Burchardt — 2017

Discussiones Mathematicae Graph Theory

A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced...

Page 1

Download Results (CSV)