# Magdalena Lemańska - Publikacje - MOST Wiedzy

## dr inż. Magdalena Lemańska

### Publikacje

• wyników na stronę:
• rok:
tytuł:
cytowania:

wszystkich: 45

#### Katalog Publikacji

##### Rok 2024
• ###### Graphs with isolation number equal to one third of the order
Publikacja

- Rok 2024

A set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by \iota(G) , is the minimum cardinality of an isolating set of G. It is known that \iota(G) \leq n/3 , if G is a connected graph of order n, , distinct from C_5 . The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number...

Pełny tekst do pobrania w serwisie zewnętrznym

##### Rok 2023
• ###### Restrained differential of a graph
Publikacja

- Rok 2023

Given a graph $G=(V(G), E(G))$ and a vertex $v\in V(G)$, the {open neighbourhood} of $v$ is defined to be $N(v)=\{u\in V(G) :\, uv\in E(G)\}$. The {external neighbourhood} of a set $S\subseteq V(G)$ is defined as $S_e=\left(\cup_{v\in S}N(v)\right)\setminus S$, while the \emph{restrained external neighbourhood} of $S$ is defined as $S_r=\{v\in S_e : N(v)\cap S_e\neq \varnothing\}$. The restrained differential of a graph $G$ is...

Pełny tekst do pobrania w portalu

##### Rok 2022
• ###### On proper (1,2)‐dominating sets in graphs
Publikacja

In 2008, Hedetniemi et al. introduced the concept of (1,)-domination and obtained some interesting results for (1,2) -domination. Obviously every (1,1) -dominating set of a graph (known as 2-dominating set) is (1,2) -dominating; to distinguish these concepts, we define a proper (1,2) -dominating set of a graph as follows: a subset is a proper (1,2) -dominating set of a graph if is (1,2) -dominating and it is not a (1,1) -dominating...

Pełny tekst do pobrania w serwisie zewnętrznym

##### Rok 2021
• ###### Common Independence in Graphs
Publikacja

- Rok 2021

Abstract: The cardinality of a largest independent set of G, denoted by α(G), is called the independence number of G. The independent domination number i(G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by αc(G), as the greatest integer r such that every vertex of G belongs to some independent subset X of VG with |X|...

Pełny tekst do pobrania w portalu

• ###### Independent Domination Subdivision in Graphs
Publikacja

- Rok 2021

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in~$S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. The independent domination subdivision number $\sdi(G)$ is the minimum number of edges that must be subdivided (each...

Pełny tekst do pobrania w portalu

• ###### Isolation Number versus Domination Number of Trees
Publikacja
• M. Lemańska
• M. J. Souto-Salorio
• A. Dapena
• F. Vazquez-Araujo

- Rok 2021

If G=(VG,EG) is a graph of order n, we call S⊆VG an isolating set if the graph induced by VG−NG[S] contains no edges. The minimum cardinality of an isolating set of G is called the isolation number of G, and it is denoted by ι(G). It is known that ι(G)≤n3 and the bound is sharp. A subset S⊆VG is called dominating in G if NG[S]=VG. The minimum cardinality of a dominating set of G is the domination number, and it is denoted by γ(G)....

Pełny tekst do pobrania w portalu

• ###### Secure Italian domination in graphs
Publikacja

- Rok 2021

An Italian dominating function (IDF) on a graph G is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0, the total weight of f assigned to the neighbours of v is at least two, i.e., ∑u∈NG(v)f(u)≥2. For any function f:V(G)→{0,1,2} and any pair of adjacent vertices with f(v)=0 and u with f(u)&gt;0, the function fu→v is defined by fu→v(v)=1, fu→v(u)=f(u)−1 and fu→v(x)=f(x) whenever x∈V(G)∖{u,v}. A secure Italian dominating...

Pełny tekst do pobrania w portalu

• ###### Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number
Publikacja

- Rok 2021

Given two types of graph theoretical parameters ρ and σ, we say that a graph G is (σ, ρ)- perfect if σ(H) = ρ(H) for every non-trivial connected induced subgraph H of G. In this work we characterize (γw, τ )-perfect graphs, (γw, α′)-perfect graphs, and (α′, τ )-perfect graphs, where γw(G), τ (G) and α′(G) denote the weakly connected domination number, the vertex cover number and the matching number of G, respectively. Moreover,...

Pełny tekst do pobrania w serwisie zewnętrznym

##### Rok 2020
• ###### Certified domination
Publikacja

Imagine that we are given a set D of officials and a set W of civils. For each civil x ∈ W, there must be an official v ∈ D that can serve x, and whenever any such v is serving x, there must also be another civil w ∈ W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce...

Pełny tekst do pobrania w portalu

• ###### On the connected and weakly convex domination numbers
Publikacja

In this paper we study relations between connected and weakly convex domination numbers. We show that in general the difference between these numbers can be arbitrarily large and we focus on the graphs for which a weakly convex domination number equals a connected domination number. We also study the influence of the edge removing on the weakly convex domination number, in particular we show that a weakly convex domination number...

Pełny tekst do pobrania w portalu

• ###### Reconfiguring Minimum Dominating Sets in Trees
Publikacja

We provide tight bounds on the diameter of γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. In particular, we prove that for any tree T of order n ≥ 3, the diameter of its γ-graph is at most n/2 in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most 2(n − 1)/3. Our proof is constructive, leading to a simple linear-time algorithm for determining...

Pełny tekst do pobrania w portalu

##### Rok 2019
• ###### Graphs with equal domination and certified domination numbers
Publikacja

- Rok 2019

A setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...

Pełny tekst do pobrania w portalu

• ###### On the super domination number of lexicographic product graphs
Publikacja

- Rok 2019

The neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...

Pełny tekst do pobrania w portalu

##### Rok 2018
• ###### Coronas and Domination Subdivision Number of a Graph
Publikacja

In this paper, for a graph G and a family of partitions P of vertex neighborhoods of G, we deﬁne the general corona G ◦P of G. Among several properties of this new operation, we focus on application general coronas to a new kind of characterization of trees with the domination subdivision number equal to 3.

Pełny tekst do pobrania w portalu

• ###### Total domination in versus paired-domination in regular graphs
Publikacja

- Rok 2018

A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...

Pełny tekst do pobrania w portalu

• ###### Total Domination Versus Domination in Cubic Graphs
Publikacja

- Rok 2018

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...

Pełny tekst do pobrania w portalu

##### Rok 2017
• ###### Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
Publikacja
• M. Lemańska
• J. A. RODRíGUEZ-VELáZQUEZ
• R. Trujillo-Rasua

- Rok 2017

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 ve 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], Ew) weakly induced by D, is connected, where Ew 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...

Pełny tekst do pobrania w serwisie zewnętrznym

##### Rok 2016
• ###### Domination-Related Parameters in Rooted Product Graphs
Publikacja

Abstract A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those sets of vertices of a graph satisfying some domination property together with other conditions on the vertices of G. Here, we investigate several domination-related parameters in rooted product graphs.

Pełny tekst do pobrania w serwisie zewnętrznym

• ###### Some variations of perfect graphs
Publikacja

- Rok 2016

We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) =γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k -path vertex cover number and the distance (k−1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k≥2. Moreover, we provide a complete characterisation of (ψ2−γ1)-perfect graphs describing the set of its forbidden induced subgraphs and providing...

Pełny tekst do pobrania w portalu

• ###### The convex domination subdivision number of a graph
Publikacja

Let G = (V;E) be a simple graph. A set D\subset V is a dominating set of G if every vertex in V - D has at least one neighbor in D. The distance d_G(u, v) between two vertices u and v is the length of a shortest (u, v)-path in G. An (u, v)-path of length d_G(u; v) is called an (u, v)-geodesic. A set X\subset V is convex in G if vertices from all (a, b)-geodesics belong to X for any two vertices a, b \in X. A set X is a convex dominating...

Pełny tekst do pobrania w portalu

• ###### Weakly convex and convex domination numbers of some products of graphs
Publikacja

- Rok 2016

If $G=(V,E)$ is a simple connected graph and $a,b\in V$, then a shortest $(a-b)$ path is called a $(u-v)$-{\it geodesic}. A set $X\subseteq V$ is called {\it weakly convex} in $G$ if for every two vertices $a,b\in X$ exists $(a-b)$- geodesic whose all vertices belong to $X$. A set $X$ is {\it convex} in $G$ if for every $a,b\in X$ all vertices from every $(a-b)$-geodesic belong to $X$. The {\it weakly convex domination number}...

• ###### Weakly convex domination subdivision number of a graph
Publikacja

- Rok 2016

A set X is weakly convex in G if for any two vertices a; b \in X there exists an ab–geodesic such that all of its vertices belong to X. A set X \subset V is a weakly convex dominating set if X is weakly convex and dominating. The weakly convex domination number \gamma_wcon(G) of a graph G equals the minimum cardinality of a weakly convex dominating set in G. The weakly convex domination subdivision number sd_wcon (G) is the minimum...

Pełny tekst do pobrania w portalu

##### Rok 2015
• ###### INFLUENCE OF A VERTEX REMOVING ON THE CONNECTED DOMINATION NUMBER – APPLICATION TO AD-HOC WIRELESS NETWORKS
Publikacja

- Rok 2015

A minimum connected dominating set (MCDS) can be used as virtual backbone in ad-hoc wireless networks for efficient routing and broadcasting tasks. To find the MCDS is an NP- complete problem even in unit disk graphs. Many suboptimal algorithms are reported in the literature to find the MCDS using local information instead to use global network knowledge, achieving an important reduction in complexity. Since a wireless network...

Pełny tekst do pobrania w serwisie zewnętrznym

• ###### Super Dominating Sets in Graphs
Publikacja

In this paper some results on the super domination number are obtained. We prove that if T is a tree with at least three vertices, then n2≤γsp(T)≤n−s, where s is the number of support vertices in T and we characterize the extremal trees.

Pełny tekst do pobrania w serwisie zewnętrznym

• ###### TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH
Publikacja

- Rok 2015

The domination multisubdivision number of a nonempty graph G was defined in [3] as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. Similarly we define the total domination multisubdivision number msd_t (G) of a graph G and we show that for any connected graph G of order at least two, msd_t (G) ≤ 3. We show that for trees the total domination...

Pełny tekst do pobrania w portalu

##### Rok 2014
• ###### Bondage number of grid graphs
Publikacja

- Rok 2014

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.

Pełny tekst do pobrania w portalu

• ###### Geometrical versus analytical approach in problem solving- an exploatory study
Publikacja
• M. Lemańska
• I. Semanisinova
• C. S. Calvo
• M. J. S. Salorio
• A. D. T. Tobar

- Rok 2014

Abstract. In this study we analyse the geometrical visualization as a part of the process of solution. In total 263 students in the first year of study at three different universities in three different countries (Poland, Slovakia and Spain) were asked to solve four mathematical problems. The analysis of the results of all students showed that geometrical visualization for problems where there is a possibility to choose different ways...

Pełny tekst do pobrania w portalu

• ###### On the partition dimension of trees
Publikacja

- Rok 2014

Given an ordered partition Π={P1,P2,…,Pt} of the vertex set V of a connected graph G=(V,E), the partition representation of a vertex v∈V with respect to the partition Π is the vector r(v|Π)=(d(v,P1),d(v,P2),…,d(v,Pt)), where d(v,Pi) represents the distance between the vertex vv and the set Pi. A partition Π of V is a resolving partition of G if different vertices of G have different partition representations, i.e., for every...

Pełny tekst do pobrania w portalu

##### Rok 2012
• ###### Influence of edge subdivision on the convex domination number
Publikacja

- Rok 2012

We study the influence of edge subdivision on the convex domination number. We show that in general an edge subdivision can arbitrarily increase and arbitrarily decrease the convex domination number. We also find some bounds for unicyclic graphs and we investigate graphs G for which the convex domination number changes after subdivision of any edge in G.

Pełny tekst do pobrania w portalu

• ###### Nordhaus-Gaddum results for the convex domination number of a graph
Publikacja

- Rok 2012

Praca dotyczy nierówności typu Nordhausa-Gadduma dla dominowania wypukłego.

Pełny tekst do pobrania w serwisie zewnętrznym

• ###### The limit case of a domination property
Publikacja

- Rok 2012

Praca dotyczy dolnego ograniczenia liczby dominowania w grafach, ze względu na ilość wierzchołków oraz największą liczbę liści w drzewie spinającym.

Pełny tekst do pobrania w serwisie zewnętrznym

##### Rok 2011
• ###### Convex universal fixers
Publikacja

- Rok 2011

Praca dotyczy dominowania wypukłego w grafach pryzmowych.

Pełny tekst do pobrania w portalu

##### Rok 2010
• ###### A note on the weakly convex and convex domination numbers of a torus
Publikacja

- Rok 2010

W pracy określone są liczby liczby dominowania i dominowania wypukłego torusów, czyli iloczynów kartezjańskich dwóch cykli.

Pełny tekst do pobrania w portalu

• ###### Nordhaus-Gaddum results for the weakly convex domination number of a graph
Publikacja

- Rok 2010

Artykuł dotyczy ograniczenia z góry i z dołu (ze względu na ilość wierzchołków) sumy i iloczynu liczb dominowania wypukłego grafu i jego dopełnienia.

Pełny tekst do pobrania w portalu

• ###### Strong weakly connected domination subdivisible graphs
Publikacja

- Rok 2010

Artykuł dotyczy wpływu podziału krawędzi na liczbę dominowania słabo spójnego. Charakteryzujemy grafy dla których podział dowolnej krawędzi zmienia liczbę dominowania słabo spójnego oraz grafy dla których podział dowolnych dwóch krawędzi powoduje zmianę liczby dominowania słabo spójnego.

Pełny tekst do pobrania w portalu

##### Rok 2009
• ###### Weakly connected domination stable trees [online]
Publikacja

- Rok 2009

Praca dotyczy pełnej charakteryzacji drzew stabilnych ze względu na liczbę dominowania słabo spójnego.

Pełny tekst do pobrania w serwisie zewnętrznym

##### Rok 2008
• ###### Weakly connected domination critical graphs
Publikacja

- Rok 2008

Praca dotyczy niektórych klas grafów krytycznych ze względu na liczbę dominowania słabo spójnego.

Pełny tekst do pobrania w portalu

##### Rok 2007
• ###### Lower bound on the weakly connected domination number of a tree
Publikacja

- Rok 2007

Praca dotyczy dolnego ograniczenia liczby dominowania słabo spójnego w drzewach (ograniczenie ze względu na ilość wierzchołków i ilość wierzchołków końcowych w drzewie).

Pełny tekst do pobrania w portalu

##### Rok 2006
• ###### Domination numbers in graphs with removed edge or set of edges
Publikacja

- Rok 2006

W artykule przedstawiony jest wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania spójnego i słabo spójnego.

Pełny tekst do pobrania w portalu

• ###### Dominowanie w grafach
Publikacja

- Rok 2006

W pracy rozważanych jest pięć liczb dominowania: klasyczna liczba dominowania, liczba dominowania spójnego, liczba dominowania słabo spójnego, liczba dominowania słabo wypukłego i liczba dominowania wypukłego. Rozważane są pewne ograniczenia na liczby dominowania, równości między poszczególnymi liczbami, wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania i NP-zupełność problemów dominowania.

• ###### Graphs with convex domination number close to their order
Publikacja

- Rok 2006

W pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.

• ###### Lower bound on the distance k-domination number of a tree
Publikacja

- Rok 2006

W artykule przedstawiono dolne ograniczenie na liczbę k-dominowania w drzewach oraz scharakteryzowano wszystkie grafy ekstremalne.

Pełny tekst do pobrania w serwisie zewnętrznym

• ###### On the doubly connected domination number of a graph
Publikacja

- Rok 2006

W pracy została zdefiniowana liczba dominowania podwójnie spójnego i przedstawiono jej podstawowe własności.

Pełny tekst do pobrania w portalu

##### Rok 2004
• ###### Lower bound on the domination number of a tree.
Publikacja

- Rok 2004

W pracy przedstawiono dolne ograniczenie na liczbę dominowania w drzewach oraz przedstawiono pełną charakterystykę grafów ekstremalnych.

• ###### Weakly convex and convex domination numbers.
Publikacja

- Rok 2004

W artykule przedstawione są nowo zdefiniowane liczby dominowania wypukłego i słabo wypukłego oraz ich porównanie z innymi liczbami dominowania. W szczególności, rozważana jest równość liczby dominowania spójnego i wypukłego dla grafów kubicznych.

wyświetlono 2494 razy