Search results for: WEAKLY CONNECTED ROMAN DOMINATION NUMBER
-
Graphs with convex domination number close to their order
PublicationW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
Combinatorial scheme of finding minimal number of periodic points for smooth self-maps of simply connected manifolds
PublicationLet M be a closed smooth connected and simply connected manifold of dimension m at least 3, and let r be a fixed natural number. The topological invariant D^m_r [f], defined by the authors in [Forum Math. 21 (2009), 491-509], is equal to the minimal number of r-periodic points in the smooth homotopy class of f, a given self-map of M. In this paper, we present a general combinatorial scheme of computing D^m_r [f] for arbitrary dimension...
-
An algorithmic approach to estimating the minimal number of periodic points for smooth self-maps of simply-connected manifolds
PublicationFor a given self-map f of M, a closed smooth connected and simply-connected manifold of dimension m 4, we provide an algorithm for estimating the values of the topological invariant D^m_r [f], which equals the minimal number of r-periodic points in the smooth homotopy class of f. Our results are based on the combinatorial scheme for computing D^m_r [f] introduced by G. Graff and J. Jezierski [J. Fixed Point Theory Appl. 13 (2013),...
-
Lower bound on the distance k-domination number of a tree
PublicationW artykule przedstawiono dolne ograniczenie na liczbę k-dominowania w drzewach oraz scharakteryzowano wszystkie grafy ekstremalne.
-
Nordhaus-Gaddum results for the convex domination number of a graph
PublicationPraca dotyczy nierówności typu Nordhausa-Gadduma dla dominowania wypukłego.
-
Induction Generator with Direct Control and a Limited Number of Measurements on the Side of the Converter Connected to the Power Grid
PublicationThe article presents an induction generator connected to the power grid using the AC/DC/AC converter and LCL coupling filter. Three-level inverters were used in the converter, both from the generator side and the power grid side. The algorithm realizing Pulse Width Modulation (PWM) in inverters has been simplified to the maximum. Control of the induction generator was based on the Direct Field-Oriented Control (DFOC) method. At...
-
Reducing the number of periodic points in the smooth homotopy class of a self-map of a simply-connected manifold with periodic sequence of Lefschetz numbers
PublicationLet f be a smooth self-map of an m-dimensional (m >3) closed connected and simply-connected manifold such that the sequence of the Lefschetz num- bers of its iterations is periodic. For a fixed natural r we wish to minimize, in the smooth homotopy class, the number of periodic points with periods less than or equal to r. The resulting number is given by a topological invariant J[f] which is defned in combinatorial terms and is...
-
Algebraic periods and minimal number of periodic points for smooth self-maps of 1-connected 4-manifolds with definite intersection forms
PublicationLet M be a closed 1-connected smooth 4-manifolds, and let r be a non-negative integer. We study the problem of finding minimal number of r-periodic points in the smooth homotopy class of a given map f: M-->M. This task is related to determining a topological invariant D^4_r[f], defined in Graff and Jezierski (Forum Math 21(3):491–509, 2009), expressed in terms of Lefschetz numbers of iterations and local fixed point indices of...
-
All graphs with restrained domination number three less than their order
PublicationW pracy opisana jest rodzina wszystkich grafów, dla których liczbadominowania zewnętrznego jest o trzy mniejsza od ich rzędu.
-
Minimizing the number of periodic points for smooth maps. Non-simply connected case
PublicationNiech f będzie gładkim odwzorowaniem zamkniętej rozmaitości o wymiarze wiekszym niż 2, a r ustaloną liczbą naturalną. W artykule zdefiniowany został niezmiennik topologiczny równy minimalnej liczbie punktów r-periodycznych w gładkiej klasie homotopii f.
-
Minimal number of periodic points for smooth self-maps of simply-connected manifolds
Open Research DataThe problem of finding the minimal number of periodic points in a given class of self-maps of a space is one of the central questions in periodic point theory. We consider a closed smooth connected and simply-connected manifold of dimension at least 4 and its self-map f. The topological invariant D_r[f] is equal to the minimal number of r-periodic points...
-
Minimal number of periodic points for C^1 self-maps of compact simply-connected manifolds
PublicationNiech f będzie odwzorowaniem gładkiej zwartej i jednospójnej rozmaitości o wymiarze większym lub równym 3. W pracy zdefiniowany został topologiczny niezmiennik będący najlepszym dolnym oszacowaniem liczby punktów periodycznych w klasie gładkich odwzorowań homotopijnych z f.
-
An algorithmic approach to estimating the minimal number of periodic points for smooth self-maps of simply-connected manifolds
Publication -
Estimates for minimal number of periodic points for smooth self-maps of simply-connected manifolds
Open Research DataWe consider a closed smooth connected and simply-connected manifold of dimension at least 4 and its self-map f. The topological invariant Dr[f] is equal to the minimal number of r-periodic points in the smooth homotopy class of f. We assume that r is odd and all coefficients b(k) of so-called periodic expansion of Lefschetz numbers of iterations are...
-
Minimal number of periodic points with the periods less or equal to r in the smooth homotopy class of simply-connected manifolds of dimension 4 and homology groups with the sum of ranks less or equal to10
Open Research DataAn important problem in periodic point theory is minimization of the number of periodic points with periods <= r in a given class of self-maps of a space. A closed smooth and simply-connected manifolds of dimension 4 and its self-maps f with periodic sequence of Lefschetz numbers are considered. The topological invariant Jr[f] is equal to the minimal...
-
Minimal number of periodic points with the periods less or equal to r in the smooth homotopy class of simply-connected manifolds of dimension 6 and homology groups with the sum of ranks less or equal to10
Open Research DataAn important problem in periodic point theory is minimization of the number of periodic points with periods <= r in a given class of self-maps of a space. A closed smooth and simply-connected manifolds of dimension 6 and its self-maps f with periodic sequence of Lefschetz numbers are considered. The topological invariant Jr[f] is equal to the minimal...
-
Minimal number of periodic points with the periods less or equal to r in the smooth homotopy class of simply-connected manifolds of dimension 5 and homology groups with the sum of ranks less or equal to10
Open Research DataAn important problem in periodic point theory is minimization of the number of periodic points with periods <= r in a given class of self-maps of a space. A closed smooth and simply-connected manifolds of dimension 5 and its self-maps f with periodic sequence of Lefschetz numbers are considered. The topological invariant Jr[f] is equal to the minimal...
-
Minimal number of periodic points with the periods less or equal to r in the smooth homotopy class of simply-connected manifolds of dimension 8 and homology groups with the sum of ranks less or equal to 10
Open Research DataAn important problem in periodic point theory is minimization of the number of periodic points with periods <= r in a given class of self-maps of a space. A closed smooth and simply-connected manifolds of dimension 8 and its self-maps f with periodic sequence of Lefschetz numbers are considered. The topological invariant Jr[f] is equal to the minimal...
-
Minimal number of periodic points with the periods less or equal to r in the smooth homotopy class of simply-connected manifolds of dimension 7 and homology groups with the sum of ranks less or equal to10
Open Research DataAn important problem in periodic point theory is minimization of the number of periodic points with periods <= r in a given class of self-maps of a space. A closed smooth and simply-connected manifolds of dimension 7 and its self-maps f with periodic sequence of Lefschetz numbers are considered. The topological invariant Jr[f] is equal to the minimal...
-
Wojciech Litwin dr hab. inż.
People1992÷1996 - study on Mechanical Department at Gdansk University of Technology1996 – employed in the Faculty of Ocean Engineering and Ship Technology at the Gdansk University of Technology2004 – PhD2014 – habilitation2016 - vice dean for science at Faculty of Ocean Engineering2020 - dean of the Faculty of Ocean Engineering2021 - head of Institute of Naval Architecture He participated in a number of designing and research programs...
-
Total Domination Versus Domination in Cubic Graphs
PublicationA 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...
-
Independent Domination Subdivision in Graphs
PublicationA 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...
-
Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs
PublicationGiven a graph G= (V, E), the subdivision of an edge e=uv∈E(G) means the substitution of the edge e by a vertex x and the new edges ux and xv. The domination subdivision number of a graph G is the minimum number of edges of G which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. Also, the domination multisubdivision number of G is the minimum number of subdivisions...
-
Domination subdivision and domination multisubdivision numbers of graphs
PublicationThe domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...
-
Paired domination subdivision and multisubdivision numbers of graphs
PublicationThe paired domination subdivision number sdpr(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph...
-
Total domination in versus paired-domination in regular graphs
PublicationA 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...
-
The paired-domination and the upper paired-domination numbers of graphs
PublicationIn this paper we obtain the upper bound for the upper paired-domination number and we determine the extremal graphs achieving this bound. Moreover we determine the upper paired- domination number for cycles.
-
Certified domination
PublicationImagine 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...
-
2-outer-independent domination in graphs
PublicationWe initiate the study of 2-outer-independent domination in graphs. A 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D, and the set V(G)\D is independent. The 2-outer-independent domination number of a graph G is the minimum cardinality of a 2-outer-independent dominating set of G. We show that if a graph has minimum degree at least two,...
-
Bondage number of grid graphs
PublicationThe 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.
-
Graphs with equal domination and certified domination numbers
PublicationA 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...
-
On trees with equal 2-domination and 2-outer-independent domination numbers
PublicationFor a graph G = (V,E), a subset D \subseteq V(G) is a 2-dominating set if every vertex of V(G)\D$ has at least two neighbors in D, while it is a 2-outer-independent dominating set if additionally the set V(G)\D is independent. The 2-domination (2-outer-independent domination, respectively) number of G, is the minimum cardinality of a 2-dominating (2-outer-independent dominating, respectively) set of G. We characterize all trees...
-
On trees with equal domination and total outer-independent domination numbers
PublicationFor a graph G=(V,E), a subset D subseteq V(G) is a dominating set if every vertex of V(G)D has a neighbor in D, while it is a total outer-independent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outer-independent domination, respectively) number of G is the minimum cardinality of a dominating (total outer-independent dominating, respectively) set of G. We characterize...
-
On the ratio between 2-domination and total outer-independent domination numbers of trees
PublicationA 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D. A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The 2-domination (total outer-independent domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (total...
-
Interpolation properties of domination parameters of a graph
PublicationAn integer-valued graph function π is an interpolating function if a set π(T(G))={π(T): T∈TT(G)} consists of consecutive integers, where TT(G) is the set of all spanning trees of a connected graph G. We consider the interpolation properties of domination related parameters.
-
Super Dominating Sets in Graphs
PublicationIn 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.
-
Restrained differential of a graph
PublicationGiven 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...
-
Cops, a fast robber and defensive domination on interval graphs
PublicationThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
The reliability of tree and star networks
PublicationThis paper investigated the reliability of tree and star networks. Following measures of network reliability are assumed: the expected number of nodes, that can communicate with the central node; the expected number of node pairs, that are connected by a path through the central node; the expected number of node pairs communicating.
-
Some variations of perfect graphs
PublicationWe 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...
-
Estimation of the minimal number of periodic points for smooth self-maps of odd dimensional real projective spaces
PublicationLet f be a smooth self-map of a closed connected manifold of dimension m⩾3. The authors introduced in [G. Graff, J. Jezierski, Minimizing the number of periodic points for smooth maps. Non-simply connected case, Topology Appl. 158 (3) (2011) 276-290] the topological invariant NJD_r[f], where r is a fixed natural number, which is equal to the minimal number of r-periodic points in the smooth homotopy class of f. In this paper smooth...
-
Bipartite theory of graphs: outer-independent domination
PublicationLet $G = (V,E)$ be a bipartite graph with partite sets $X$ and $Y$. Two vertices of $X$ are $X$-adjacent if they have a common neighbor in $Y$, and they are $X$-independent otherwise. A subset $D \subseteq X$ is an $X$-outer-independent dominating set of $G$ if every vertex of $X \setminus D$ has an $X$-neighbor in $D$, and all vertices of $X \setminus D$ are pairwise $X$-independent. The $X$-outer-independent domination number...
-
The Backbone Coloring Problem for Small Graphs
PublicationIn this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified...
-
Secure Italian domination in graphs
PublicationAn 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)>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...
-
2-bondage in graphs
PublicationA 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The 2-bondage number of G, denoted by b_2(G), is the minimum cardinality among all sets of edges E' subseteq E such that gamma_2(G-E') > gamma_2(G). If for every E' subseteq E we have...
-
Common Independence in Graphs
PublicationAbstract: 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|...
-
Graphs with isolation number equal to one third of the order
PublicationA 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...
-
Double bondage in graphs
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G, denoted by gamma_d(G), is the minimum cardinality of a double dominating set of G. The double bondage number of G, denoted by b_d(G), is the minimum cardinality among all sets...
-
Minimum order of graphs with given coloring parameters
PublicationA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
Non-isolating bondage in graphs
PublicationA dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The non-isolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(G-E') \ge 1$ and $\gamma(G-E')...