Total outer-connected domination in trees

Joanna Cyman

Displaying similar documents to “Total outer-connected domination in trees”

On the (2,2)-domination number of trees

You Lu, Xinmin Hou, Jun-Ming Xu (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let γ(G) and $γ_{2, 2} (G)$ denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that $(2 (γ (T) + 1)) / 3 \leq γ_{2, 2} (T) \leq 2 γ (T)$ . Moreover, we characterize all the trees achieving the equalities.

Domination numbers in graphs with removed edge or set of edges

Magdalena Lemańska (2005)

Discussiones Mathematicae Graph Theory

Similarity:

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) \leq γ_{w} (G - e) \leq γ_{w} (G) + 1$ and $γ_{c} (G) \leq γ_{c} (G - e) \leq γ_{c} (G) + 2$ if G and G-e are connected. Additionally we show that $γ_{w} (G) \leq γ_{w} (G - E ₚ) \leq γ_{w} (G) + p - 1$ and $γ_{c} (G) \leq γ_{c} (G - E ₚ) \leq γ_{c} (G) + 2 p - 2$ if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order...

On the connectivity of finite subset spaces

Jacob Mostovoy, Rustam Sadykov (2012)

Fundamenta Mathematicae

Similarity:

We prove that the space $e x p_{k} ⋁ S^{m + 1}$ of nonempty subsets of cardinality at most k in a bouquet of m+1-dimensional spheres is (m+k-2)-connected. This, as shown by Tuffley, implies that the space $e x p_{k} X$ is (m+k-2)-connected for any m-connected cell complex X.

On locating and differentiating-total domination in trees

Mustapha Chellali (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γ ₜ^{L} (G)$ and $γ ₜ^{D} (G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

Closure for spanning trees and distant area

Jun Fujisawa, Akira Saito, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $d e g_{G} u + d e g_{G} v \geq n - 1$ , G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $d e g_{G} u + d e g_{G} v$ and the structure of the distant area for u and v. We prove...

On D-connected sets in the space $V^{q}$

S. Topa (1976)

Annales Polonici Mathematici

Similarity:

Connected global offensive k-alliances in graphs

Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

We consider finite graphs G with vertex set V(G). For a subset S ⊆ V(G), we define by G[S] the subgraph induced by S. By n(G) = |V(G) | and δ(G) we denote the order and the minimum degree of G, respectively. Let k be a positive integer. A subset S ⊆ V(G) is a connected global offensive k-alliance of the connected graph G, if G[S] is connected and |N(v) ∩ S | ≥ |N(v) -S | + k for every vertex v ∈ V(G) -S, where N(v) is the neighborhood of v. The connected global offensive k-alliance number...

Connected components of sets of finite perimeter and applications to image processing

Luigi Ambrosio, Vicent Caselles, Simon Masnou, Jean-Michel Morel (2001)

Journal of the European Mathematical Society

Similarity:

This paper contains a systematic analysis of a natural measure theoretic notion of connectedness for sets of finite perimeter in $ℝ^{N}$ , introduced by H. Federer in the more general framework of the theory of currents. We provide a new and simpler proof of the existence and uniqueness of the decomposition into the so-called $M$ -connected components. Moreover, we study carefully the structure of the essential boundary of these components and give in particular a reconstruction formula of a set...

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

Similarity:

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$ , denoted by $pc (G)$ , is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $pc (G)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$ -coloring for a connected bipartite graph $G$ having $δ (G) \geq 2$ and a dominating...

A remark on the (2,2)-domination number

Torsten Korneffel, Dirk Meierling, Lutz Volkmann (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_{k, p} (G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_{k, p} (G) \leq (p / (p + k)) n (G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture...

On weakly Gibson $F_{σ}$ -measurable mappings

Olena Karlova, Volodymyr Mykhaylyuk (2013)

Colloquium Mathematicae

Similarity:

A function f: X → Y between topological spaces is said to be a weakly Gibson function if $f (Ū) \subseteq \bar{f (U)}$ for any open connected set U ⊆ X. We prove that if X is a locally connected hereditarily Baire space and Y is a T₁-space then an $F_{σ}$ -measurable mapping f: X → Y is weakly Gibson if and only if for any connected set C ⊆ X with dense connected interior the image f(C) is connected. Moreover, we show that each weakly Gibson $F_{σ}$ -measurable mapping f: ℝⁿ → Y, where Y is a T₁-space, has a connected graph. ...

Does the endomorphism poset $P^{P}$ determine whether a finite poset $P$ is connected? An issue Duffus raised in 1978

Jonathan David Farley (2023)

Mathematica Bohemica

Similarity:

Duffus wrote in his 1978 Ph.D. thesis, “It is not obvious that $P$ is connected and $P^{P} ≅ Q^{Q}$ imply that $Q$ is connected”, where $P$ and $Q$ are finite nonempty posets. We show that, indeed, under these hypotheses $Q$ is connected and $P ≅ Q$ .

A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs

Yaping Mao, Christopher Melekian, Eddie Cheng (2023)

Czechoslovak Mathematical Journal

Similarity:

For a connected graph $G = (V, E)$ and a set $S \subseteq V (G)$ with at least two vertices, an $S$ -Steiner tree is a subgraph $T = (V^{'}, E^{'})$ of $G$ that is a tree with $S \subseteq V^{'}$ . If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$ -Steiner tree. Two $S$ -Steiner trees are if they share no vertices other than $S$ and have no edges in common. For $S \subseteq V (G)$ and $| S | \geq 2$ , the pendant tree-connectivity $τ_{G} (S)$ is the maximum number of internally disjoint pendant $S$ -Steiner trees in $G$ , and for $k \geq 2$ , the $k$ -pendant tree-connectivity $τ_{k} (G)$ is the...

A note on the cubical dimension of new classes of binary trees

Kamal Kabyl, Abdelhafid Berrachedi, Éric Sopena (2015)

Czechoslovak Mathematical Journal

Similarity:

The cubical dimension of a graph $G$ is the smallest dimension of a hypercube into which $G$ is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with $2^{n}$ vertices, $n \geq 1$ , is $n$ . The 2-rooted complete binary tree of depth $n$ is obtained from two copies of the complete binary tree of depth $n$ by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice...

The extremal irregularity of connected graphs with given number of pendant vertices

Xiaoqian Liu, Xiaodan Chen, Junli Hu, Qiuyun Zhu (2022)

Czechoslovak Mathematical Journal

Similarity:

The irregularity of a graph $G = (V, E)$ is defined as the sum of imbalances $| d_{u} - d_{v} |$ over all edges $u v \in E$ , where $d_{u}$ denotes the degree of the vertex $u$ in $G$ . This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. In this paper, we completely determine the extremal values of the irregularity of connected graphs with $n$ vertices and $p$ pendant vertices ( $1 \leq p \leq n - 1$ ), and characterize the corresponding extremal graphs.

Quasi-tree graphs with the minimal Sombor indices

Yibo Li, Huiqing Liu, Ruiting Zhang (2022)

Czechoslovak Mathematical Journal

Similarity:

The Sombor index $S O (G)$ of a graph $G$ is the sum of the edge weights $\sqrt{d_{G}^{2} (u) + d_{G}^{2} (v)}$ of all edges $u v$ of $G$ , where $d_{G} (u)$ denotes the degree of the vertex $u$ in $G$ . A connected graph $G = (V, E)$ is called a quasi-tree if there exists $u \in V (G)$ such that $G - u$ is a tree. Denote $𝒬 (n, k) = {G : G$ is a quasi-tree graph of order $n$ with $G - u$ being a tree and $d_{G} (u) = k}$ . We determined the minimum and the second minimum Sombor indices of all quasi-trees in $𝒬 (n, k)$ . Furthermore, we characterized the corresponding extremal graphs, respectively.