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 γ 2 , 2 ( T ) 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 ) γ 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...

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 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...

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...

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 ) ( 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 ( Ū ) 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. ...

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 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...

Turán's problem and Ramsey numbers for trees

Zhi-Hong Sun, Lin-Lin Wang, Yi-Li Wu (2015)

Colloquium Mathematicae

Similarity:

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with V = v , v , . . . , v n - 1 , E = v v , . . . , v v n - 3 , v n - 4 v n - 2 , v n - 3 v n - 1 and E = v v , . . . , v v n - 3 , v n - 3 v n - 2 , v n - 3 v n - 1 . For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for r ( T , T i ) , where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

On a characterization of k -trees

De-Yan Zeng, Jian Hua Yin (2015)

Czechoslovak Mathematical Journal

Similarity:

A graph G is a k -tree if either G is the complete graph on k + 1 vertices, or G has a vertex v whose neighborhood is a clique of order k and the graph obtained by removing v from G is also a k -tree. Clearly, a k -tree has at least k + 1 vertices, and G is a 1-tree (usual tree) if and only if it is a 1 -connected graph and has no K 3 -minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of k -trees as follows: if G is a graph with at least k + 1 vertices, then G is...

The vertex detour hull number of a graph

A.P. Santhakumaran, S.V. Ullas Chandran (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), I D [ S ] = x , y S I D [ x , y ] . A set S of vertices is a detour convex set if I D [ S ] = S . The detour convex hull [ S ] D is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of...

Sharkovskiĭ's theorem holds for some discontinuous functions

Piotr Szuca (2003)

Fundamenta Mathematicae

Similarity:

We show that the Sharkovskiĭ ordering of periods of a continuous real function is also valid for every function with connected G δ graph. In particular, it is valid for every DB₁ function and therefore for every derivative. As a tool we apply an Itinerary Lemma for functions with connected G δ graph.