Magdalena Lemanska

dblp:83/8435 · DBLP profile ↗
← Back
10ranked-venue papers
3as first author
3since 2021 · last 2025
0000-0002-0924-9924ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 10 · 3 first-author · 3 since 2021
YearPublicationVenuePosition
2025 Common matching number of a graph
abstract
The cardinality of the largest matching in a graph G , denoted by α ′ ( G ) , is referred to as the upper matching number of G . The lower matching number i ′ ( G ) is defined as the cardinality of the smallest maximal matching in G . We introduce the concept of the common matching number of a graph G , denoted by α c ′ ( G ) , which is the largest integer k such that every edge in G belongs to a matching that contains at least k edges. In this paper, we explore the relationships between the parameters i ′ ( G ) , α c ′ ( G ) , and α ′ ( G ) . In particular, we demonstrate that the difference between α c ′ ( G ) and i ′ ( G ) can be arbitrarily large, while the difference between α ′ ( G ) and α c ′ ( G ) can at most be one. Additionally, we characterize the trees T for which i ′ ( T ) = α c ′ ( T ) , as well as the trees T for which α c ′ ( T ) = α ′ ( T ) .
Magda Dettlaff, Magdalena Lemanska, Jerzy Topp
Discret. Appl. Math.2
2023 Common edge independence number of a tree (Brief Announcement)
abstract
The cardinality of a largest matching of G, denoted by α'(G), is called the upper matching number of G. The lower matching number i'(G) of a graph G is the cardinality of a smallest maximal matching of G. We introduce the concept of the common edge independence number of a graph G, denoted by α'c(G), is the largest integer k such that every edge of G belongs to a matching that has at least k edges. For any graph G, the relations between above parameters are given by the chain of inequalities i'(G) ≤ α'c(G) ≤ α'(G). We study relations between this three parameters, in particular we show that the difference between α'c(G) and i'(G) can be arbitrarily large while α'(G) and α'c(G) may differ by at most one. We also characterize the trees T for which i'(T) = α'c(T), and the trees T for which α'c(T) = α'(T).
Magda Dettlaff, Magdalena Lemanska, Jerzy Topp
LAGOS2
2021 Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number
Sergio Bermudo, Magda Dettlaff, Magdalena Lemanska
Discret. Appl. Math.3
2019 On the super domination number of lexicographic product graphs
Magda Dettlaff, Magdalena Lemanska, Juan A. Rodríguez-Velázquez, Rita Zuazua
Discret. Appl. Math.2
2019 Convex dominating sets in maximal outerplanar graphs
Magdalena Lemanska, Eduardo Rivera-Campo, Radoslaw Ziemann, Rita Zuazua, Pawel Zylinski
Discret. Appl. Math.1
2019 Relations between edge removing and edge subdivision concerning domination number of a graph
Magdalena Lemanska, Joaquín Tey, Rita Zuazua
Discret. Appl. Math.1
2017 Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
abstract
A vertex cover of a graph G = ( V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The vertex cover number τ( G) is the minimum cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[ D] w = ( N[ D], E w ) weakly induced by D, is connected, where E w is the set of all edges having at least one vertex in D. The weakly connected domination number γ w ( G) of G is the minimum cardinality among all weakly connected dominating sets of G. In this article we characterize the graphs where γ w ( G) = τ( G). In particular, we focus our attention on bipartite graphs, regular graphs, unicyclic graphs, block graphs and corona graphs.
Magdalena Lemanska, Juan A. Rodríguez-Velázquez, Rolando Trujillo-Rasua
Fundam. Informaticae1
2014 Bondage number of grid graphs
Magda Dettlaff, Magdalena Lemanska, Ismael González Yero
Discret. Appl. Math.2
2014 On the partition dimension of trees
Juan A. Rodríguez-Velázquez, Ismael González Yero, Magdalena Lemanska
Discret. Appl. Math.3
2010 A note on the weakly convex and convex domination numbers of a torus
Joanna Raczek, Magdalena Lemanska
Discret. Appl. Math.2