Currently displaying 1 – 10 of 10

Showing per page

Order by Relevance | Title | Year of publication

Domination numbers in graphs with removed edge or set of edges

Magdalena Lemańska — 2005

Discussiones Mathematicae Graph Theory

It is known that the removal of an edge from a graph G cannot decrease a domination number γ(G) and can increase it by at most one. Thus we can write that γ(G) ≤ γ(G-e) ≤ γ(G)+1 when an arbitrary edge e is removed. Here we present similar inequalities for the weakly connected domination number γ w and the connected domination number γ c , i.e., we show that γ w ( G ) γ w ( G - e ) γ w ( G ) + 1 and γ c ( G ) γ c ( G - e ) γ c ( G ) + 2 if G and G-e are connected. Additionally we show that γ w ( G ) γ w ( G - E ) γ w ( G ) + p - 1 and γ c ( G ) γ c ( G - E ) γ c ( G ) + 2 p - 2 if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected...

Convex universal fixers

Magdalena LemańskaRita Zuazua — 2012

Discussiones Mathematicae Graph Theory

In [1] Burger and Mynhardt introduced the idea of universal fixers. Let G = (V, E) be a graph with n vertices and G’ a copy of G. For a bijective function π: V(G) → V(G’), define the prism πG of G as follows: V(πG) = V(G) ∪ V(G’) and E ( π G ) = E ( G ) E ( G ' ) M π , where M π = u π ( u ) | u V ( G ) . Let γ(G) be the domination number of G. If γ(πG) = γ(G) for any bijective function π, then G is called a universal fixer. In [9] it is conjectured that the only universal fixers are the edgeless graphs K̅ₙ. In this work we generalize the concept of universal...

Weakly connected domination stable trees

Magdalena LemańskaJoanna Raczek — 2009

Czechoslovak Mathematical Journal

A dominating set D V ( G ) is a in G if the subgraph G [ D ] w = ( N G [ 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 . γ w ( G ) of a graph G is the minimum cardinality among all weakly connected dominating sets in G . A graph G is said to be or just γ w - if γ w ( G ) = γ w ( G + e ) for every edge e belonging to the complement G ¯ of G . We provide a constructive characterization of weakly connected domination stable trees.

On the doubly connected domination number of a graph

Joanna CymanMagdalena LemańskaJoanna Raczek — 2006

Open Mathematics

For a given connected graph G = (V, E), a set D V ( G ) is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.

Graphs with convex domination number close to their order

Joanna CymanMagdalena LemańskaJoanna Raczek — 2006

Discussiones Mathematicae Graph Theory

For a connected graph G = (V,E), a set D ⊆ V(G) is a dominating set of G if every vertex in V(G)-D has at least one neighbour 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 ⊆ V(G) is convex in G if vertices from all (a-b)-geodesics belong to X for any two vertices a,b ∈ X. A set X is a convex dominating set if it is convex and dominating. The convex domination number γ c o n ( G ) of a graph G is the...

Total Domination Multisubdivision Number of a Graph

Diana Avella-AlaminosMagda DettlaffMagdalena LemańskaRita Zuazua — 2015

Discussiones Mathematicae Graph Theory

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 multisubdi- vision number is equal to the known total domination subdivision...

Some Variations of Perfect Graphs

Magda DettlaffMagdalena LemańskaGabriel SemanišinRita Zuazua — 2016

Discussiones Mathematicae Graph Theory

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 the explicit characterisation of the structure of graphs belonging...

Page 1

Download Results (CSV)