Displaying similar documents to “Perfect connected-dominant graphs”

The contractible subgraph of 5 -connected graphs

Chengfu Qin, Xiaofeng Guo, Weihua Yang (2013)

Czechoslovak Mathematical Journal

Similarity:

An edge e of a k -connected graph G is said to be k -removable if G - e is still k -connected. A subgraph H of a k -connected graph is said to be k -contractible if its contraction results still in a k -connected graph. A k -connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k -connected. In this paper, we show that there is a contractible subgraph in a 5 -connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex...

Contractible edges in some k -connected graphs

Yingqiu Yang, Liang Sun (2012)

Czechoslovak Mathematical Journal

Similarity:

An edge e of a k -connected graph G is said to be k -contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k -connected. In 2002, Kawarabayashi proved that for any odd integer k ≥ 5 , if G is a k -connected graph and G contains no subgraph D = K 1 + ( K 2 ∪ K 1 , 2 ) , then G has a k -contractible edge. In this paper, by generalizing this result, we prove that...

Connected resolvability of graphs

Varaporn Saenpholphat, Ping Zhang (2003)

Czechoslovak Mathematical Journal

Similarity:

For an ordered set W = { w 1 , w 2 , ⋯ , w k } of vertices and a vertex v in a connected graph G , the representation of v with respect to W is the k -vector r ( v | W ) = ( d ( v , w 1 ) , d ( v , w 2 ) , ⋯ , d ( v , w k ) ) , where d ( x , y ) represents the distance between the vertices x and y . The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W . A resolving set for G containing a minimum number of vertices is a basis for G . The dimension dim ( G ) is the number of vertices in a basis for G . A resolving set W of G is connected...

Total outer-connected domination in trees

Joanna Cyman (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)-D] is connected. The total outer-connected domination number of G, denoted by γ t c ( G ) , is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then γ t c ( T ) ≥ ⎡ 2 n / 3 ⎤ . Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.

Graph domination in distance two

Gábor Bacsó, Attila Tálos, Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that D o m D o m u = D o m ₂ u holds for u = all connected graphs without induced P u (u ≥ 2). (In particular,...

On connected resolving decompositions in graphs

Varaporn Saenpholphat, Ping Zhang (2004)

Czechoslovak Mathematical Journal

Similarity:

For an ordered k -decomposition 𝒟 = { G 1 , G 2 , ⋯ , G k } of a connected graph G and an edge e of G , the 𝒟 -code of e is the k -tuple c 𝒟 ( e ) = ( d ( e , G 1 ) , d ( e , G 2 ) , ... , d ( e , G k ) ) , where d ( e , G i ) is the distance from e to G i . A decomposition 𝒟 is resolving if every two distinct edges of G have distinct 𝒟 -codes. The minimum k for which G has a resolving k -decomposition is its decomposition dimension dim d ( G ) . A resolving decomposition 𝒟 of G is connected if each G i is connected for 1 ≤ i ≤ k . The minimum k for which G has a connected resolving k -decomposition is its connected decomposition...