Results 41 to 50 of about 7,398 (287)
On domination in connected cubic graphs
Discrete Mathematics, 2005 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Alexandr V. Kostochka, B. Y. Stodolsky
openaire +2 more sources
Progress on Roman and Weakly Connected Roman Graphs
Mathematics, 2021 A graph G for which γR(G)=2γ(G) is the Roman graph, and if γRwc(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar
Joanna Raczek, Rita Zuazua
doaj +1 more source
Steiner domination decomposition number of graphs
Ratio Mathematica, 2022 In this paper, we introduce a new concept Steiner domination decomposition number of graphs. Let be a connected graph with Steiner domination numberA decomposition of is said to be a Steiner Domination Decomposition if Steiner domination ...
M Mahiba, E Ebin Raja Merly
doaj +1 more source
Discussiones Mathematicae Graph Theory, 2021 In this paper, we study a new distance parameter triameter of a connected graph G, which is defined as max{d(u; v)+d(v;w)+d(u;w) : u; v;w ∈ V }and is denoted by tr(G).
Das Angsuman
doaj +1 more source
Traceability of connected domination critical graphs [PDF]
Applied Mathematics and Computation, 2020 A dominating set in a graph $G$ is a set $S$ of vertices of $G$ such that every vertex outside $S$ is adjacent to a vertex in $S$. A connected dominating set in $G$ is a dominating set $S$ such that the subgraph $G[S]$ induced by $S$ is connected. The connected domination number of $G$, $γ_c(G)$, is the minimum cardinality of a connected dominating set
Michael A. Henning +2 more
openaire +3 more sources
On domination multisubdivision number of unicyclic graphs [PDF]
Opuscula Mathematica, 2018 The paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram,
Joanna Raczek
doaj +1 more source
Dominating Sets and Connected Dominating Sets in Dynamic Graphs [PDF]
CoRR, 2019 In this paper we study the dynamic versions of two basic graph problems: Minimum Dominating Set and its variant Minimum Connected Dominating Set. For those two problems, we present algorithms that maintain a solution under edge insertions and edge deletions in time $O(Δ\cdot \text{polylog}~n)$ per update, where $Δ$ is the maximum vertex degree in the ...
Hjuler N. +3 more
openaire +6 more sources
Domination Parameters of a Graph and its Complement
Discussiones Mathematicae Graph Theory, 2018 A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G.
Desormeaux Wyatt J. +2 more
doaj +1 more source
Connected Domination Critical Graphs with Cut Vertices
Discussiones Mathematicae Graph Theory, 2020 A graph G is said to be k- γc-critical if the connected domination number of G, γc(G), is k and γc(G + uv) < k for any pair of non-adjacent vertices u and v of G. Let G be a k-γc-critical graph and ζ (G) the number of cut vertices of G. It was proved, in
Kaemawichanurat Pawaton +1 more
doaj +1 more source
Algorithmic Aspects of Secure Connected Domination in Graphs
Discussiones Mathematicae Graph Theory, 2021 Let G = (V, E) be a simple, undirected and connected graph. A connected dominating set S ⊆ V is a secure connected dominating set of G, if for each u ∈ V \ S, there exists v ∈ S such that (u, v) ∈ E and the set (S \ {v}) ∪ {u} is a connected dominating ...
Kumar Jakkepalli Pavan +1 more
doaj +1 more source